# 2019q3 Homework4 (compute-pi)
contributed by < `Ting199708` >

## 開發環境

* Operating System : Ubuntu 18.04.3 LTS
* CPU : Intel^®^ Core^TM^ i7-8700 @ 3.20GHz
* GPU : Intel^®^ UHD Graphics 630
* RAM : 8.0 GB

## 重現實驗

* BASELINE


* LEIBNIZ


* EULER


### 初步分析

根據上面的實驗解果可以得知， LEIBNIZ 在計算時平均下來速度是最快的， EULER 次之， BASELINE 最慢，另外，我認為比較有趣的地方在於不同架構下，各演算法的優勢皆不相同。

## 時間計算

在 linux 中我們主要有 4 種不同的計算時間的方式，彼此之間各有所差別，下面分別探討

* clock 函數

clock 定義如下

    clock_t clock(void)

其回傳的類型為 clock_t ，將其除以 CLOCKS_PER_SEC 可得到實際經過秒數，在 linux 系統中，數值為 1000000 ，因此其精確度為微秒。

* clock_gettime 函數

clock_gettime 定義如下：

    int clock_gettime(clockid_t clk_id, struct timespec *tp);

其中， timspec 的定義如下：

    struct timespec {
        time_t   tv_sec;        /* seconds */
        long     tv_nsec;       /* nanoseconds */
    };

由此可知，其計算時間的精確度為 nanosecond ，另外 clk_id 為時鐘類型的定義，有以下幾種選項
* CLOCK_REALTIME
System-wide realtime clock.
* CLOCK_MONOTONIC
Clock that cannot be set and represents monotonic time since some unspecified starting point.
* CLOCK_PROCESS_CPUTIME_ID
High-resolution per-process timer from the CPU.
* CLOCK_THREAD_CPUTIME_ID
Thread-specific CPU-time clock.

* time 函數

time 定義如下：

    time_t time(time_t *t)

其返回的時間為從 紀元 (00:00:00 UTC 1970年1月1日) 開始的`秒數`，其中的 time_t 若不為 `NULL` ，則其返回值會儲存在變量 t 當中

* gettimeofday 函數

gettimeofday 定義如下：

    int gettimeofday(struct timeval *tv, struct timezone *tz);

其中的 timeval 及 timezone 定義如下：

    struct timeval {
        time_t      tv_sec;     /* seconds */
        suseconds_t tv_usec;    /* microseconds */
    };

    struct timezone {
        int tz_minuteswest;     /* 和格林威治時間差了幾分鐘 */
        int tz_dsttime;         /* 日光節約時間狀態 */
    };

gettimeofday 可以回傳系統目前的時間，精確度至`微秒`，其中時間回傳到變量 tv 中，時區的訊息則回傳至變量 tz 中，此二變量皆可設為 `NULL` ，不影響其使用。

## 萊布尼茨公式法求 $\pi$

首先來看一下在數學上的定義

$$
\sum_{n=0}^{\infty} \dfrac{(-1)^n}{2n+1}= 1 - \dfrac{1}{3} + \dfrac{1}{5} - \dfrac{1}{7} +\ ... \ = \dfrac{\pi}{4}
$$

上述的無窮級數即為 `萊布尼茨級數` ，可以簡單證明如下：

考慮下方數列

$$
\dfrac{1}{1+x^2} = 1-x^2+x^4-x^6 +\ ...\ +(-1)^nx^{2n} + \dfrac{(-1)^{n+1}x^{2n+2}}{1+x^2}
$$

對等式兩邊從 0 到 1 積分可得

$$
\int_{0}^{1}\dfrac{1}{1+x^2}dx= \dfrac{\pi}{4} = 1-\dfrac{1}{3}+\dfrac{1}{5}-\ ...\ +\dfrac{(-1)^n}{2n+1}+(-1)^{n+1}\int_{0}^{1}\dfrac{x^{2n+2}}{1+x^2}dx
$$

當 $n\rightarrow\infty$ 時，除了最末項其他皆收斂至 0

$$
0\leq\int_{0}^{1}\dfrac{x^{2n+2}}{1+x^2}dx\leq\int_{0}^{1}x^{2n+2}dx=\dfrac{1}{2n+3}\rightarrow 0 \ ，當\ n\rightarrow\infty
$$

得證
$$
1 - \dfrac{1}{3} + \dfrac{1}{5} - \dfrac{1}{7} +\ ... \ = \dfrac{\pi}{4}
$$

## 高斯-勒讓德演算法

高斯-勒讓德演算法以其迅速收斂的效果著稱，只要迭代 25 次，即可計算出 $\pi$ 的 4500 萬位數，不過其缺點是記憶體使用過於密集，根據 [維基百科中文版(英文版資料未更新)](https://zh.wikipedia.org/wiki/%E9%AB%98%E6%96%AF-%E5%8B%92%E8%AE%A9%E5%BE%B7%E7%AE%97%E6%B3%95) ，日本筑波大學於 2009 年 8月 17 日宣布利用此演算法計算出 $\pi$ 的小數點後2,576,980,370,000位數字

### 演算法

1. 設定初始值
$a_0=1$ $b_0=\dfrac{1}{\sqrt2}$ $t_0=\dfrac{1}{4}$ $p_0=1$
2. 反覆執行以下步驟值到所需之精確度
$a_{n+1}=\dfrac{a_n+b_n}{2}$

$b_{n+1}=\sqrt{a_nb_n}$

$t_{n+1}=t_n-p_n(a_n-a_{n+1})^2$

$p_{n+1}=2p_n$

3. 可得出 $\pi$ 的近似值為
$\pi\approx\dfrac{(a_{n+1}+b_{n+1})^2}{4t_{n+1}}$

利用此演算法，執行前三次迭代的結果(精確至第一個錯誤的位數)：

3.140...
3.14159264...
3.1415926545897932382...

## Reference
* [clock()](http://man7.org/linux/man-pages/man3/clock.3.html)
* [clock_gettime()](https://linux.die.net/man/3/clock_gettime)
* [time()](https://linux.die.net/man/2/time)
* [gettimeofday()](https://linux.die.net/man/2/gettimeofday)
* [Leibniz formula for π](https://en.wikipedia.org/wiki/Leibniz_formula_for_%CF%80#Proof)
* [Gauss–Legendre algorithm](https://en.wikipedia.org/wiki/Gauss%E2%80%93Legendre_algorithm)