[C++]Algorytm Kahana

[alchem]

Próbuje napisać kawałek kodu, który obliczy sumę szeregu \(\displaystyle{ \sum_{k=1}^{\infty}= \frac{1}{k^2}}\) za pomocą algorytmu Kahana.
Na wikipedii znalazłem taki kod:

Kod: Zaznacz cały

function KahanSum(input)
    var sum = 0.0
    var c = 0.0                  
    for i = 1 to input.length do
        var y = input[i] - c         
        var t = sum + y              
        c = (t - sum) - y        
        sum = t                
    next i                     
    return sum

Z tego co wywnioskowałem input to ilość liczb jakie chce użyć do przybliżenia tego szeregu,
nie wiem jednak co znaczy :

Kod: Zaznacz cały

input[i]

Może ktoś pomóc?
Dodam że piszę to w C++, i input kojarzy mi się z tablicami ale to raczej nie tablice.

[Afish]

input oznacza liczby do zsumowania.

[alchem]

Ja miałem takie coś :

Kod: Zaznacz cały

float suma_kahana    (int n)
{
    float suma = 0;
    float c = 0; //jakas poprawka???
    for(int i = 1; i <= n; i++)
    {
        float y = i - c;
        float t = suma + y;
        float c = (t - suma) - y;
        suma = t;
    }

  return suma;
}

czyli \(\displaystyle{ i}\) to liczby do zsumowania, przynajmniej tak mi się wydaje, ale algorytm pokazuje kosmiczne liczby dla większych \(\displaystyle{ k}\).

[Afish]

Pokazuje kosmos, bo nie rozumiesz algorytmu.
Algorytm Kahana służy do minimalizowania błędów precyzji przy obliczaniu sumy liczb. Możesz go użyć do dowolnych ciągów, nie tylko do odwrotności kwadratów kolejnych liczb. Wklejony przez Ciebie kod oblicza sumę liczb \(\displaystyle{ 1 \ldots n}\), ale skoro oblicza na zmiennych pojedynczej precyzji, to dla większych wartości niedokładność będzie dotkliwa.

[alchem]

Czyli z tego wychodzi że zamiast \(\displaystyle{ i}\) powinno być \(\displaystyle{ \frac{1}{ i^{2} }}\)

Kod: Zaznacz cały

float suma_kahana    (int n)
{
    float suma=0;
    for(float i = 1; i <= n; i=i+1)
    {
        float suma = 0;
        float c = 0;
        float y = (1/(i*i)) - c;
        float t = suma + y;
        c = (t - suma) - y;
        suma = t;
    }

  return suma;
}

Jest tak, ale dla każdej liczby wyrazów w ciągu pokazuje mi że suma równa się zero.

[Afish]

To spójrz na linie 3 i 6, wyjaśnij czym się różnią i które są potrzebne.

[alchem]

Dobra, nie zauważyłem że w pętli wrzuciłem

Kod: Zaznacz cały

float suma = 0;

i w każdej zerowałem sumę.
Dzięki za pomoc!