2016q3 - Homework (compute-pi)

contributed by <kaizsv>

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

10/1更新

圖表晝出來卻沒有分析，上圖的error為什麼avx avxunroll會有誤差，看了王紹華同學的筆記，才聯想到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_n^2}{4}}$$

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

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

如此可以求出多邊形的邊長

$\overline{CD}$，就可以求出近似的圓周。

$$\pi =\frac{n\times \overline{CD}}{2\times 1}$$

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