GPU610 Team Tsubame

TBD...

Team Member

1. Mark Anthony Villaflor (Leader)
2. Huachen Li
3. Yanhao Lei

eMail All

Assignment 1

Pi

This is a comparison between two programs that calculate Pi.

Leibniz formula implementation:

#include <iostream>
#include <iomanip>

#include <chrono>

// Function duplicated from Workshop 2 - BLAS
void reportTime(const char* msg, std::chrono::steady_clock::duration span) {
    auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(span);
    std::cout << msg << " - took - " 
    << ms.count() << " millisecs" << std::endl;
}

// Arctangent of 1; execute for ~n iterations to refine the result
long double arctan1( unsigned long long int it ) { 
    long double r = 0.0;

    // v0.25; due to performing the operations in a different order, there are rounding issues...
    for ( long double d = 0.0; d < it; d++ ) { 
        long double de = d * 4.0 + 1.0;
        r += (1.0 / de) - (1.0 / (de + 2.0));
    }   

    return r;
}

int main( int argc, char* argv[] ) { 
    unsigned long long int n = std::stoull(argv[1], 0); 

    std::chrono::steady_clock::time_point ts, te; 
    ts = std::chrono::steady_clock::now();
    long double pi = 4.0 * arctan1( n );
    te = std::chrono::steady_clock::now();
    reportTime("Arctangent(1) ", te - ts);

    // Maximum length of a long double is 64 digits; minus "3." gives 62 digits.
    std::cout.precision(62);
    std::cout << "Pi: " << std::fixed << pi << std::endl;
}

4 digits are correct at 10K iterations:

> time ./leibniz 10000
Arctangent(1)  - took - 0 millisecs
Pi: 3.14154265358982449354505184224706226814305409789085388183593750

real 	0m0.016s
user	0m0.004s
sys	0m0.008s

7 digits are correct at 10M iterations:

> time ./leibniz 10000000
Arctangent(1)  - took - 171 millisecs
Pi: 3.14159260358979321929411010483335076060029678046703338623046875

real	0m0.187s
user	0m0.172s
sys	0m0.012s

No difference at 100M iterations:

> time ./leibniz 100000000
Arctangent(1)  - took - 1708 millisecs
Pi: 3.14159264858979533105269588144636827564681880176067352294921875

real	0m1.725s
user	0m1.704s
sys	0m0.008s

Monte-Carlo algorithm implementation:

#include <iostream>
#include <random>

#include <chrono>

// Function duplicated from Workshop 2 - BLAS
void reportTime(const char* msg, std::chrono::steady_clock::duration span) {
    auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(span);
    std::cout << msg << " - took - " <<
    ms.count() << " millisecs" << std::endl;
}

int main(int argc, char* argv[]) {
    std::chrono::steady_clock::time_point ts, te;

    ts = std::chrono::steady_clock::now();
    unsigned long long int n = std::stoull(argv[1], 0),
                           totalCircle = 0;

    int stride = 1000,
        circleSize = n / stride;

    unsigned int* circle = new unsigned int[circleSize];

    for (int i = 0; i < circleSize; i++)
        circle[i] = 0;

    std::random_device rd;
    std::mt19937 mt(rd());
    std::uniform_real_distribution<long double> dist(0.0, 1.0);
    te = std::chrono::steady_clock::now();
    reportTime("Init. ", te - ts);

    ts = std::chrono::steady_clock::now();
    for (unsigned long long int i = 0; i < circleSize; i++) {
        for (int j = 0; j < stride; j++) {
            long double x = dist(mt),
                        y = dist(mt);
            // if position is inside the circle...
            if (x * x + y * y < 1.0) {
                circle[i]++;
            }
        }
    }

    for (int i = 0; i < circleSize; i++)
        totalCircle += circle[i];

    long double pi = 4.0 * ((long double) totalCircle) / ((long double) n);
    te = std::chrono::steady_clock::now();
    reportTime("Drop points ", te - ts);

    std::cout.precision(62);
    std::cout << "Pi: " << std::fixed << pi << std::endl;

    delete [] circle;
}

At around 10K iterations, the first decimal is stable.

> time ./monte-carlo 10000
Init.  - took - 0 millisecs
Drop points  - took - 1 millisecs
Pi: 3.11679999999999999995940747066214271399076096713542938232421875

real	0m0.019s
user	0m0.004s
sys	0m0.008s
> time ./monte-carlo 10000
Init.  - took - 0 millisecs
Drop points  - took - 1 millisecs
Pi: 3.16480000000000000009124645483638005316606722772121429443359375

real	0m0.018s
user	0m0.008s
sys	0m0.004s
> time ./monte-carlo 10000
Init.  - took - 0 millisecs
Drop points  - took - 1 millisecs
Pi: 3.16639999999999999995108079797745403993758372962474822998046875

real	0m0.018s
user	0m0.004s
sys	0m0.008s

The next digit is stable at around 10M iterations

> time ./monte-carlo 10000000
Init.  - took - 0 millisecs
Drop points  - took - 1096 millisecs
Pi: 3.14150879999999999990685506379151092914980836212635040283203125

real	0m1.114s
user	0m1.092s
sys	0m0.008s
> time ./monte-carlo 10000000
Init.  - took - 0 millisecs
Drop points  - took - 1097 millisecs
Pi: 3.14219679999999999993332000514101309818215668201446533203125000

real	0m1.114s
user	0m1.092s
sys	0m0.016s
> time ./monte-carlo 10000000
Init.  - took - 0 millisecs
Drop points  - took - 1097 millisecs
Pi: 3.14158840000000000010696443730751070688711479306221008300781250

real	0m1.115s
user	0m1.088s
sys	0m0.012s

By 100M, the third digit appears to be stable.

> time ./monte-carlo 100000000
Init.  - took - 1 millisecs
Drop points  - took - 10910 millisecs
Pi: 3.14138611999999999989559296142971334120375104248523712158203125

real	0m10.930s
user	0m10.881s
sys	0m0.012s
> time ./monte-carlo 100000000
Init.  - took - 1 millisecs
Drop points  - took - 10847 millisecs
Pi: 3.14185203999999999998835042980260823242133483290672302246093750

real	0m10.868s
user	0m10.833s
sys	0m0.016s
> time ./monte-carlo 100000000
Init.  - took - 1 millisecs
Drop points  - took - 10883 millisecs
Pi: 3.14160056000000000009896028441147564080893062055110931396484375

real	0m10.903s
user	0m10.865s
sys	0m0.016s