#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <cmath>
#include <sys/timeb.h>

using namespace std;

timeb startTime;

void start() {
    ftime(&startTime);
}

void stop() {
    timeb now;

    ftime(&now);

    double elapsed = now.time - startTime.time + (now.millitm - startTime.millitm)/1000.0;

    cout << "time = " << elapsed << " secs";
}

float shewchuk(const float *data, int num) {
    static float p[1000];

    int size = 0;

    for (int i = 0; i < num; ++i) {
        float x = data[i];
        int k = 0;

        for (int j = 0; j < size; ++j) {
            float y = p[j];

            if (fabs(x) < fabs(y)) {
                float t = x;

                x = y;
                y = t;
            }

            float hi = x + y;
            float lo = y - (hi - x);

            if (lo != 0) {
                p[k++] = lo;
            }

            x = hi;
        }

        p[k] = x;
        size = ++k;
    }

    float sum = 0;

    for (int i = 0; i < size; ++i) {
        sum += p[i];
    }

    return sum;
}

#define NUM 1000000

static float data[NUM];

int main() {
    cout << "Generating pseudorandom numbers" << endl;

    for (int i = 0; i < NUM; i += 2) {
        float x = rand()/(RAND_MAX + 1.0);

        if (x == 1) {
            x = nextafterf(1, 0);
        }

        data[i] = tan(x*0.5*M_PI);
        data[i + 1] = -data[i];
    }

    cout << "Shuffle" << endl;

    for (int i = 0; i < NUM; ++i) {
        int j = rand() % NUM;
        float t = data[i];

        data[i] = data[j];
        data[j] = t;
    }

	start();
    float sum = shewchuk(data, NUM);
    stop();
    cout << ", sum = " << setprecision(30) << sum << endl;
	
    return EXIT_SUCCESS;
}