#include <iostream>
#include <ctime>
#include <cstdlib>

using namespace std;

inline void swap(long & a, long & b)
{
    long t = a;
    a = b;
    b = t;
    return;
}

// strictly positive values, please!
long gcd_euclid(long m, long n)
{
    while (m > 0)
    {
        if (n > m)
        {
            swap(m,n);
        }
        m -= n;
    }
    return n;
}

inline long min(long a, long b)
{
    return a>b ? b : a;
}

// strictly positive values, please!
long gcd_divmod(long m, long n)
{
    long g = min(m,n);
    while (m%g != 0 || n%g != 0)
    {
        g--;
    }
    return g;
}

inline long max(long a, long b)
{
    return a>b ? a : b;
}

// strictly positive values, please!
long gcd_combin(long m, long n)
{
    long g = min(m,n), m_left = m%g, n_left = n%g;
    while (m_left != 0 || n_left != 0)
    {
        g -= max(m_left,n_left);
        m_left = m%g;
        n_left = n%g;
    }
    return g;
}

inline long rand_range(long low, long high)
{
    return rand()%(high-low+1) + low;
}

int main(void)
{
    const unsigned long LOTS = 5000000;
    time_t start, end, setup_st, setup_end;
    time_t diff, setup_df;
    long x, y, t;
    srand(static_cast<unsigned>(time(nullptr)));

    cout << "\nBad for Euclid:\n\n";
    setup_st = time(nullptr);
    for (unsigned long i = 0; i != LOTS; i++)
    {
        x = rand_range(1,10);
        y = 100000*x;   // 100 thousand times [1..10]
        if ((t=gcd_divmod(x,y)) != t)
        {
            cout << "Nope, didn't work!\n";
        }
    }
    setup_end = time(nullptr);
    setup_df = setup_end - setup_st;
    cout << "It took " << setup_df << " seconds (" << (setup_df/(double)LOTS)
         << " sec/rand&mult) to setup for the bad-for-Euclid\nalgorithm tests."
         << endl;

    start = time(nullptr);
    for (unsigned long i = 0; i != LOTS; i++)
    {
        x = rand_range(1,10);
        y = 100000*x;   // 100 thousand times [1..10]
        t = gcd_divmod(x,y);
        if (t != gcd_divmod(x,y))
        {
            cout << "Nope, didn't work!\n";
        }
    }
    end = time(nullptr);

    diff = end - start - setup_df;
    cout << "It took " << diff << " seconds (" << (diff/(double)LOTS)
         << " sec/gcd) to get the gcds by the modulo\nalgorithm." << endl;

    start = time(nullptr);
    for (unsigned long i = 0; i != LOTS; i++)
    {
        x = rand_range(1,10);
        y = 100000*x;   // 100 thousand times [1..10]
        t = gcd_euclid(x,y);
        if (t != gcd_divmod(x,y))
        {
            cout << "Nope, didn't work!\n";
        }
    }
    end = time(nullptr);

    diff = end - start - setup_df;
    cout << "It took " << diff << " seconds (" << (diff/(double)LOTS)
         << " sec/gcd) to get the gcds by Euclid's\nalgorithm." << endl;

    start = time(nullptr);
    for (unsigned long i = 0; i != LOTS; i++)
    {
        x = rand_range(1,10);
        y = 100000*x;   // 100 thousand times [1..10]
        t = gcd_combin(x,y);
        if (t != gcd_divmod(x,y))
        {
            cout << "Nope, didn't work!\n";
        }
    }
    end = time(nullptr);

    diff = end - start - setup_df;
    cout << "It took " << diff << " seconds (" << (diff/(double)LOTS)
         << " sec/gcd) to get the gcds by the combination\nalgorithm." << endl;

    cout << "\nBad for modulo:\n\n";
    setup_st = time(nullptr);
    for (unsigned long i = 0; i != LOTS; i++)
    {
        x = rand_range(150000,200000);
        y = rand_range(150000,200000);
        if ((t=gcd_euclid(x,y)) != t)
        {
            cout << "Nope, didn't work!\n";
        }
    }
    setup_end = time(nullptr);
    setup_df = setup_end - setup_st;
    cout << "It took " << setup_df << " seconds (" << (setup_df/(double)LOTS)
         << " sec/rand&rand) to setup for the bad-for-modulo\nalgorithm tests."
         << endl;

    start = time(nullptr);
    for (unsigned long i = 0; i != LOTS; i++)
    {
        x = rand_range(150000,200000);
        y = rand_range(150000,200000);
        t = gcd_divmod(x,y);
        if (gcd_euclid(x,y) != t)
        {
            cout << "Nope, didn't work!\n";
        }
    }
    end = time(nullptr);

    diff = end - start - setup_df;
    cout << "It took " << diff << " seconds (" << (diff/(double)LOTS)
         << " sec/gcd) to get the gcds by the modulo\nalgorithm." << endl;

    start = time(nullptr);
    for (unsigned long i = 0; i != LOTS; i++)
    {
        x = rand_range(150000,200000);
        y = rand_range(150000,200000);
        t = gcd_euclid(x,y);
        if (gcd_euclid(x,y) != t)
        {
            cout << "Nope, didn't work!\n";
        }
    }
    end = time(nullptr);

    diff = end - start - setup_df;
    cout << "It took " << diff << " seconds (" << (diff/(double)LOTS)
         << " sec/gcd) to get the gcds by Euclid's\nalgorithm." << endl;

    start = time(nullptr);
    for (unsigned long i = 0; i != LOTS; i++)
    {
        x = rand_range(150000,200000);
        y = rand_range(150000,200000);
        t = gcd_combin(x,y);
        if (gcd_euclid(x,y) != t)
        {
            cout << "Nope, didn't work!\n";
        }
    }
    end = time(nullptr);

    diff = end - start - setup_df;
    cout << "It took " << diff << " seconds (" << (diff/(double)LOTS)
         << " sec/gcd) to get the gcds by the combination\nalgorithm." << endl;

    return 0;
}