I have written follwoing kahan algorithm; it reasonably work for n to be from 1 million up to 10 million, but it produces very large error when n is 100 million. I tested it multiple times but I cannot figure out why this is happening.
#include <iostream>
#include <vector>
#include <random>
#include <cfloat>
#include <iomanip>
using namespace std;
float KahanAlgorithm(const vector<float> &myarray){
float sum{0.0f};
float ac{0.0f};
for(unsigned int i=0; i<myarray.size();i++){
float temp{sum+myarray[i]};
if(sum>=myarray[i]){
ac=ac+(sum-temp)+myarray[i];
}
else{
ac=ac+(myarray[i]-temp)+sum;
}
sum=temp;
}
return sum+ac;
}
int main() {
int n=100000000;
random_device r;
default_random_engine g(r());
uniform_real_distribution<float> d(0.f, nextafter(1.f, DBL_MAX));
vector<float> a(n);
vector<double> b(n);
for(auto i=0;i<n;i++){
a[i]=d(g);
b[i]=static_cast<double> (a[i]);
}
double exact_sum;
float kahan_sum;
exact_sum=accumulate(b.begin(),b.end(),0.0);
cout<<"exact "<<exact_sum<<endl;
kahan_sum=KahanAlgorithm(a);
cout<<" Kahan sum "<<kahan_sum<<endl;
return 0;
}
sum is :
exact 5.00045e+07
Kahan sum 3.35544e+07
Aucun commentaire:
Enregistrer un commentaire