# 2017q1 Homework1(compute-pi)
contributed by <`rayleigh0407`>

>進度落後，請加快腳步跟上，加油!
>[name=課程助教][color=red]
>好的, 謝謝助教關心
>[name=子祐][color=red]

### Reviewed by `twzjwang`
- 可探討計算時間的方法，比較不同時間函式

## 開發環境

$lscpu
Architecture:          x86_64
CPU op-mode(s):        32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                8
On-line CPU(s) list:   0-7
Thread(s) per core:    2
Core(s) per socket:    4
Socket(s):             1
NUMA node(s):          1
Vendor ID:             GenuineIntel
CPU family:            6
Model:                 94
Model name:            Intel(R) Core(TM) i7-6700K CPU @ 4.00GHz
Stepping:              3
CPU MHz:               800.000
CPU max MHz:           4200.0000
CPU min MHz:           800.0000
BogoMIPS:              8016.72
Virtualization:        VT-x
L1d cache:             32K
L1i cache:             32K
L2 cache:              256K
L3 cache:              8192K
NUMA node0 CPU(s):     0-7

## Leibniz formula proof

$$
{π \over 4} = \arctan(1)
\\= \int_0^1 \left({\sum_{k=0}^n (-1)^kx^{2k}} + {{(-1)^{n+1}x^{2n+2}} \over {1+x^2}}\right)dx
\\ = \left({\sum_{k=0}^n (-1)^k \over{2x+1}}\right)+(-1)^{n+1}\left({\int_0^1 {x^{2n+2} \over 1+x^2}}dx\right)
\\Considering\ only\ the\ integral\ in\ the\ last\ line,\ we\ have:
\\ 0\ <\ {\int_0^1 {x^{2n+2} \over 1+x^2}}dx\ <\ {\int_0^1 {x^{2n+2}}}dx\ =\
{1 \over {2n+3}}\ \rightarrow\ 0\ as\ n\ \rightarrow\ \infty
\\By\ the\ squeeze\ theorem,\ as\ n\ →\ ∞\ we\ are\ left\ with\ the\ Leibniz\ series:\\{π \over 4} = {\sum_{k=0}^∞ (-1)^k \over {2n+1}}
$$

## 開發過程
先將檔案clone下來
稍微了解一下程式

make gencsv => 執行程式, 從N = 100開始測, 每測一次N+5000, 直到N超過25000, 並將結果輸入至 result_clock_gettime.csv
result_clock_gettime.csv 為表格模式, 需用其他軟體來作圖

先來畫畫看原始測資
繪圖工具
- 1.LibreOffice
- 2.gnuplot

### 1.LibreOffice

> 資料出現了相當大的偏差
> 看能不能試著去校正

調整N範圍:100~50Millions ,間隔1M

資料還是有偏差
而且看過別人共筆才發現
OPENMP(4 thread)版本是最快的
有些人會是 AVX+unrolling
初步猜測是 CPU 性能不同導致

再來調整 benchmark_clock_gettime.c 內的 loop
先提昇至100

> 除了OpenMP(4 thread)以外的都算平穩

把程式以外的應用關閉：
> OMP(4 thread)仍舊有偏差值

**暫時不考慮pi精準度 先求資料穩定度**
降低N範圍：從100～100,000
間隔調整為1000
loop 設為1000

> 最不穩的還是omp

loop = 10000
> 稍微好一點了
> 在調大一點

loop = 50000
> 結果沒什麼幫助
後來想想應該是**多次測試, 並盡量去除資料極值**
才能將資料平滑化

<font size="5">信賴區間</font>

: *In statistics, a confidence interval (CI) is a type of interval estimate of a population parameter. It is an observed interval (i.e., it is calculated from the observations), in principle different from sample to sample, that potentially includes the unobservable true parameter of interest. How frequently the observed interval contains the true parameter if the experiment is repeated is called the confidence level.*

這意思是, 假設某總統經過++民調後的支持率++為55%, 而95%信賴區間在支持率50%~60%之間, 則這位總統++真實的支持率++落在50%~60%的機率為95%.

而以前高中教的那些理論, 像是`在距離平均值正負一個標準差的範圍內, 會有95%的母體群`等等, 都要建立在母體群屬於<font color="red">常態分佈(Normal distribution)</font>的前提.

不過為了平滑化資料, 也只好捨棄一些極值.

### 2.gnuplot
> 接下來使用 gnuplot 來繪圖
> 看了一堆資料還是畫得不怎麼好

先把 loop 調回1000
接著把測試部份以一個迴圈包住( test_time 變數來計數)
讓每個N值都測好幾次
test_time=100

而計算的部份
我會先把落在正負一個標準差之外的資料去除
再取其平均值

標準差公式；

$$
σ = \sqrt{{\sum_{i=0}^N X_i^2 \over N} - µ^2}
$$

使用math.h
須在編譯時加入-lm

結果：


參考資料
- [LaTeX數學表達式](http://meta.math.stackexchange.com/questions/5020/mathjax-basic-tutorial-and-quick-reference)
- [Leibniz formula for pi](https://en.wikipedia.org/wiki/Leibniz_formula_for_%CF%80)
- [gnuplot語法解說和示範](https://hackmd.io/s/Skwp-alOg)
- [gnuplot語法解說和示範(2)](http://gtchen.pixnet.net/blog/post/5873441-gnuplot-(part-i))
- [Normal Distribution](https://en.wikipedia.org/wiki/Normal_distribution)
- [信賴區間語信心水平的解讀](http://web.cc.ntnu.edu.tw/~494402345/CI/CI.pdf)
- [信賴區間的迷思](http://yenchic-blog.logdown.com/posts/177267-confidence-interval-of-myth)
- [Confidence interval](https://en.wikipedia.org/wiki/Confidence_interval)
- [HackMD Command](https://hackmd.io/s/S1vAcMjFe#)
- [get PI(stackoverflow)](http://stackoverflow.com/questions/1727881/how-to-use-the-pi-constant-in-c)