Avoiding large arrays rounding error

See more:

C++

mathematics

I have the following mathematical problem:

If making reduction operations over large arrays creates rounding errors.
As example adding more than 100k samples using floats begin to generate errors of 1%

I solved partially using a reduction by using a tree adding by pairs (as it is said in this web for opencl apps: link)

My code at function "reduction()" works well to add the array elements.

unfortunately the function "reduction_media()" that add pairs and divide by 2 does not works. What is the error?

MODIFIED the code by add array filling again before usage , now it works.

What I have tried:

#include <iostream>
#include <time.h> //clock()
#pragma warning(disable:4996) //disable deprecateds
using namespace std;
typedef unsigned char uchar;

time_t start,stop;
//Timing function. Add this command to the beginning of the function to be measured: start=clock();
void timer(char *title,int size=0)
{
	stop=clock();
	cout<<title<< " time ="<<(double) (stop-start)/(double) CLOCKS_PER_SEC<< " secs";
	if (size)
		cout << " = " << 1e-6*size/( (double)(stop-start)/(double)CLOCKS_PER_SEC ) <<  " Mops/seg"   <<endl; 
	else
		cout<<endl;
	start=clock();//it must be done better in the beginning of the function to be measured
}

#define SIZE 100000000 //100Meg

//tree reduction:
float reduction(float *data,int max)
{
	while(max>1)
	{
		data[max]=0.0;max=(max+1)/2;
		for (int i=0;i<max;i++)
			data[i]+=data[i+max];      //operation to be performed
	}
	return data[0];
}

//calculates media NOW WORKING!
float reduction_media(float *data,int max)
{
	while(max>1)
	{
		data[max]=data[max/2];max=(max+1)/2;
		for (int i=0;i<max;i++)
			data[i]=(data[i]+data[i+max])/2.0f;      //operation to be performed
	}
	return data[0];
}

void main()
{
	cout<<"WARNING: run this program in RELEASE mode. Timing is non correct in DEBUG mode"<<endl;
	float *data=new float[SIZE+1];
	//Fills the array in a very fast way:
	std::fill(data, data+SIZE, 3.14f);
	timer("\n fill(data, data+SIZE, 3.14f)      ",SIZE);

	//Calculates media in standard way but FAILS due rounding errors:
	start=clock();
	float sum=0.0f;
	for (int i=0;i<SIZE;i++)
		sum+=data[i];
	sum=sum/(float) SIZE;
	timer("\n Standard for() reduction          ",SIZE);
	cout << "This should be 3.14="<<sum<<endl;

	//calculates media by using the tree reduction function, is OK and runs 20% faster in release mode:
	start=clock();
	sum=reduction(data,SIZE)/(float) SIZE;
	timer("\n Using reduction() function        ",SIZE);
	cout << "This should be 3.14="<<sum<<endl;

	//calculates media by using reduction_media:
       	std::fill(data, data+SIZE, 3.14f);
	start=clock();
	sum=reduction_media(data,SIZE);
	timer("\n Using reduction() function        ",SIZE);
	cout << "This should be 3.14="<<sum<<endl;

	delete data;
	cout<<"===END==="<<endl;getchar();
}