2016q3 - Homework (compute-pi)
===
contributed by <`kaizsv`>

`benchmark_clock_gettime.c`的loop提高到100，下面分別是時間及誤差，由圖可見`avxunroll`執行較短的時間，但N要超過80,000才會精確到小數點下5位，但這個時間是loop=100，正常來說還要更快才對。

:::warning
10/1更新

圖表晝出來卻沒有分析，上圖的error為什麼`avx` `avxunroll`會有誤差，看了[王紹華](https://hackmd.io/s/BJdYsOPa)同學的筆記，才聯想到`avxunroll`執行1次等於`avx`執行4次，`baseline`的16次，而我的`Makefile`的迴圈為`seq 100 2000 800000`，因為100不是16的倍數，跟`baseline`比差了4次沒執行，因此`avxunroll`的錯誤比其它人來得高。

acos的值域為 [0,$\pi$]，而acos(-1)就落在180度的位置，其弧度為$\pi$
:::

### polygon
在網路上找到，用幾何來逼近pi，原理是圓的內接多邊形邊長`CD`。而圓周`2piR`就可以求出近似pi值。

$$
\overline{AB}^2 + \overline{BC}^2 = 1 $$$$
\overline{AB} = \sqrt{1-\overline{BC}}
$$
假設 d~n~ 為 n 多邊形的邊長且$\overline{BC}=\frac{d_{n}}{2}$

$$
\overline{AB} = \sqrt{1-\left(\frac{d_{n}}{2}\right)^2} $$$$
\overline{BD} = 1-\sqrt{1-\frac{d^2_{n}}{4}}
$$

$$
\begin{align}
\overline{CD}^2 &= \overline{BC}^2 + \overline{BD}^2 \\
&= \left(\frac{d_n}{2}\right)^2 + \left(1-\sqrt{1-\left(\frac{d_n}{2}\right)^2}\right)^2 \\
&= \frac{d_n^2}{4} + \left(1-2\sqrt{1-\frac{d_n^2}{4}}+\left(1-\frac{d_n^2}{4}\right)\right) \\
&= 2-2\sqrt{1-\frac{d_n^2}{4}}
\end{align}
$$

$$
\Rightarrow \overline{CD} = \sqrt{2 - 2\sqrt{1-\frac{d_n^2}{4}}}
$$

如此可以求出多邊形的邊長$\overline{CD}$，就可以求出近似的圓周。
$$
\pi = \frac{n\times\overline{CD}}{2\times1}
$$

double polygon(size_t N)
{
	double polygon_edge_length_squared = 2.0;
	unsigned int polygon_sides = 4;
	for (int i = 0; i < N; i++) {
		polygon_edge_length_squared = 2 - 2 * sqrt(1 - polygon_edge_length_squared / 4);
		polygon_sides *= 2;
	}
	return polygon_sides * sqrt(polygon_edge_length_squared) / 2;
}

這個方法不能用任意的多邊形，只能是4 8 16 32...，若要使用任意多邊形，就要算弧度，但弧度跟$\pi$有關，因此就用這個計算邊長的方法。

在我的實驗中，N到100多的時候就會因為平方根太小變成0，算出來是錯的，但就算N小於100，誤差會比其它版本來得小，但超過100就大幅增加。

###### tags: `assigment_3` `compute-pi`