# 從 $\sqrt{2}$ 的運算談浮點數 ## $\sqrt{2}$ 的緣起 ![](https://i.imgur.com/jXkculR.png) 邊長為 1 的正方形對角線長度是多少?中學數學提到,直角邊長為 1 的等腰**直角** 三角形的斜邊長就是 $\sqrt{2}$,而這個數是個無理數,也就是說它並不能被寫成兩個整數相除的形式。 * 延伸閱讀: [根號 2 讓一代人的信仰崩潰,你信嗎?](https://kknews.cc/news/qyamxnb.html) 影片: [第一次數學危機,天才是怎麼被扼殺的?](https://www.youtube.com/watch?v=nAOVQEcqjSM) 畢氏定理的畢氏,指的是古希臘學者畢達哥拉斯。相傳此定理在當時是由畢達哥拉斯所發現的,雖然這並不是他最早發現的 (古巴比倫人在他出生前的一千多年以前就已發現),但至少可知道,畢達哥拉斯把這個定理又帶回來給西方世界,所以西方世界多用畢氏定理來稱這個常見的定理。 在數學之外,畢達哥拉斯也是集數學、天文、音樂理論於一身的高手,他願意將部分的知識傳播給大眾,而且他也是當時少數讓女性也能來聽講的學者(當時禁止女性來聽公開演講)。不過,這些知識也有分等級,分享給大眾聽的,是比較一般的知識,若你想提問,或者你想知道更高深的知識,你需要加入畢達哥拉斯學派。 畢達哥拉斯學派的正統信徒必須宣誓,不會將學派的秘密以及較高深的學說外流出去,同時也必須經過嚴格的訓練,才會被承認為正式的教徒。除此之外,還必須嚴守各種的清規戒律,某種程度就是在修行;同時也會將自己所研究出來的新成果,成就歸於導師畢達哥拉斯。 畢達哥拉斯等人對數學是有一定的狂熱,他們不是為了實際的應用而去鑽研數學。他們相信,透過數學,即可以探究這世界,上段所提的音樂理論,也是從數學推演出來的。為了抽象地去形容宇宙,或者單純只是為了美,畢達哥拉斯的學派在數學上也有很多的特殊想法,例如:萬物皆數。 萬物皆數,照字面上的意思就是萬物的本質皆是數字,這也是為什麼他們相信能利用數學來尋找真理。這個數是有嚴謹定義的,或者說,他們認為所有的數都有一個性質:可公度性。 可公度性要如何理解呢?若用線段長度來看,兩條線段之間必定能用一個特殊長度的整數倍來形容,例如 2 公分和 6 公分,可寫成 `1 x 2` 公分和 `3 x 2` 公分,皆可用 2 公分的整數倍來形容;7 公分和 5.5 公分,可寫成 `14 x 0.5` 公分和 `11 x 0.5` 公分。要找這個特殊長度,可以先把長的扣掉短的,得到的新線段,再拿第二短的去扣掉最短的又得到新線段,接著重複上述過程,直到能剛好減到 0,此時最短線段的長度就是這個特殊長度。 例如 7, 5.5 -> 7, 5.5, 1.5 -> 7, 5.5, 4, 1.5 -> 7, 5.5, 4, 2.5, 1.5 ->  7, 5.5, 4, 2.5, 1.5, 1 -> 7, 5.5, 4, 2.5, 1.5 ,1 , 0.5,最後得到 7, 5.5, 4, 2.5, 1.5,1, 0.5, 0.5,這個特殊長度即是0.5,與輾轉相除法找最大公因數很像。 可公度性的另一種說法是:畢達哥拉斯認為所有的數,皆是整數或者兩個非零整數的比值,也就是有理數。等等,這觀點和我們今日所知的數學原理不一致,發展的轉折就要提及希帕索斯(Hippasus)。 希帕索斯是畢達哥拉斯學派的信徒,傳聞他是個非常認真的學生,亦愛鑽研可公度性這個性質。有一次,他鑽研正五邊形的性質時,卻發現有兩條線段的長度,不論怎麼樣也無法找到可公度性所需要的特殊長度,只能無窮無盡的切割下去,沒有停止的那天。換言之,這代表了這兩條線段並沒有可公度性這個性質,那麼,他們當初所相信的一個性質--所有數都是可公度的,便是錯誤的,或者說,這世界上存在著不是整數、亦不能寫成兩整數比值的數。 後來希帕索斯改良使用更為直覺的方式,利用正方形的對角線與邊長,來說明存在兩數是不可公度的。 在畢達哥拉斯的指使或者漠視下,希帕索斯被門徒淹死在河裡。有人說畢達哥拉斯也搞了政治,但是其地位後來已經岌岌可危,是不容許再出現”學說錯誤”這樣的汙點。有的故事則說,希帕索斯提出不可公度這件事時,畢達哥拉斯已經死去一段日子,被處死這件事情與畢達哥拉斯沒有太大關係。也有故事說,希帕索斯是與同門搭船時,與大家爭論不可公度這件事情時,被惱怒的同門丟下船溺死的。 無論是哪個版本,都指向一個諷刺的結果:希帕索斯運用理性找出的真相,被當時最能代表理性、邏輯和數學的一群人否定了,而他的生命也被這群人不理性的抹殺了。 仔細想想,畢達哥拉斯或者其學派的人,不太可能不懂希帕索斯提出的疑慮,或者說不定,以畢達哥拉斯這樣的大師來說,說他早就發現了這件事情也不稀奇,可是為什麼這些信徒,仍舊選擇抹殺這個發現問題的學生呢? 因為信仰,不是宗教上的信仰,而是一種你內心認同的價值觀。 畢達哥拉斯一生都在追求真理,同時他也不斷的宣揚萬物皆數這樣的想法。試著這麼想,如果有一天,你發現了"真理”與你所想像的不同,跟你這一生所信奉的不一樣,也與你這大半輩子所宣揚的有所違背,你會做甚麼選擇?承認錯誤,讓自己變得更接近真理?如果你這麼選擇,那麼你一定會成為不凡之人。 只可惜多數的人,可能也包含畢達哥拉斯與其信徒,沒有那麼大的勇氣去否定他們的信仰,去承認過去的努力只是個錯誤。因為這也是在否定他自己。如果他們是自己發現了這個事實,那麼能採取的,只能欺騙自己。 如果一件事情變成了信仰,而信仰者卻沒有透過自省或質疑來去強化信念,那麼他的信仰即使看起來很堅定,也就只是虛有其表。在這種情況之下,你會發現他們為了鞏固那並不是很堅固的信仰,會編撰出很多理由,即使這些理由從邏輯或知識上來看根本過於荒謬。 那麼,會不會是因為他們邏輯推理的能力不足、學識不夠豐富,才無法藉由理性與科學證據來修正自己的信仰呢? 不是,邏輯和知識當然是承認錯誤的必要條件,但即使他們有這些能力,若不曾自省與質疑,那麼這些能力也只會變成他們用來找尋藉口或荒謬理由的工具而已。不提最近的議題,看看前面的故事就知道,即使當代最有邏輯與學識的一群人,一旦把教條當成不可質疑的信仰時,就算有人提出毫無瑕疵的證據質疑其說法,也只會像希帕索斯一樣,被這樣想要堅定自己搖搖欲墜的信仰之人推向深淵抹除,而在這種情形下,恐怕還有很多不同名字的希帕索斯這樣的消失在這個世界上。 我們藉由中學的數學,已知無理數的存在 (或者不可公度的存在),可以大概推得,希帕索斯的發現並沒有隨著他的生命而消失。這個理論後來似乎隨著畢達哥拉斯學派的式微或者教條約束力的減弱,也漸漸流傳出去。這理論沒有沉到水裡,至於希帕索斯的發現是否對他的信仰(數學)造成了傷害呢?的確這個發現造成了第一次數學危機,但是也讓數學發展向前邁進了一大步。 別讓信仰殺死希帕索斯,因為他會帶領我們更走向真理。 > 以上改寫自 [因信仰而死的希帕索斯](https://m.facebook.com/notes/%E5%AE%8B%E6%94%BF%E8%92%B2/%E5%9B%A0%E4%BF%A1%E4%BB%B0%E8%80%8C%E6%AD%BB%E7%9A%84%E5%B8%8C%E5%B8%95%E7%B4%A2%E6%96%AF/10207331849244095/) ## 兩河流域古文明時期 針對這個數學問題,考古學家發現在西元前 1800 年的古巴比倫泥板上已記載了答案。 兩河流域文明時代最早的居民是蘇美人,在公元前 4000 年就抵達幼發拉底河和底格里斯河之間的美索不達米亞平原,大體位於現今的伊拉克。屬于塞姆語系的阿卡德人、巴比倫人、亞述人以及迦勒底人,繼承和發展了蘇美人的成就,使兩河流域的文明成為人類文明史上重要的一頁。其中,巴比倫人的成就最大,因此兩河流域的文明又被稱為巴比倫文明。 兩河流域的居民主要用使用牛、驢拉著木犁耕地,古代兩河地區的金屬制造工藝達到了相當純熟的水平。古巴比倫人使用楔形文字表示數字,以 60 進位來做計算。考古學家在中東地區發掘了數以萬計的古巴比倫泥板碎片,其中一片現存於耶魯大學的泥板依稀刻印著一個正方形的對角線的圖案,以及一排以楔形文字的數字。 ![](https://i.imgur.com/EcBHx6Y.png) 後來考古學家解譯出上圖這組楔形數字是: `1`, `24`, `51`, `10`。 由於古巴比倫人用的是 60 進位系統,將這組數字轉換為 10 進位的數值得到以下: ![](https://i.imgur.com/qKEW7N3.png) 這個數字極為近似 $\sqrt{2}$ 的值 `1.41421356`。 泥板上還給出了一個計算的例子,在正方形邊線上標註了數字 `30`,也就是十進位 `0.5`,代表正方形邊長。這個時候對角線長度的楔形數字為 `42`, `25`, `35`,轉換十進位得到: ![](https://i.imgur.com/C6jeLXa.png) 這個值正是 $\sqrt{2}$ 的一半,也就是邊長 `0.5` 正方形的對角線長度。 ### 十分逼近法算 $\sqrt{2}$ 古巴比倫人的時代距離今天已約 3800 年之久,我們無法確實知道古巴比倫人是如何計算出這麼精準的 $\sqrt{2}$ 數值。 我們可以試試估算 $\sqrt{2}$ 的數值。先回想平方根的定義,一個數 n 的平方根會滿足 > n = (n平方根)^2^ 現在考慮三個數 `1`, `2`, `4`,由於 `1 < 2 < 4`,如果對這三個數開平方根也會有下面的關係: > $\sqrt{1}$ < $\sqrt{2}$ < $\sqrt{4}$ 這裡 `1` 和 `4` 都是平方數,可以很容易地算出 $\sqrt{1}$ = 1 和 $\sqrt{4}$ = 2,帶入上式可得到: > 1 < $\sqrt{2}$ < 2 這個式子告訴我們 $\sqrt{2}$ 的數值介於正整數 `1` 和 `2` 之間,不過我們還不能確定 $\sqrt{2}$ 的數值比較靠近 `1` 還是比較靠近 `2`。 這個情況下我們可以用一個方法更進一步確定 $\sqrt{2}$ 的數值。將 `1` 到 `2` 再細分為 10 等分,也就是 `1.1`, `1.2`, …, `1.9`, `2`,再計算每一個細分刻度的平方: ![](https://i.imgur.com/FVt96VI.png) 在數線上方我們列出 n 平方根的十等分值,在下方列出相對應的 n = (n平方根)^2^ 的值。我們可以看到 n = (n平方根)^2^ 有一個重要的變化點,也就是由 `1.96` 遞增到 `2.25` 之處,遞增的 n 值由小於 `2` 變成大於 `2`: ![](https://i.imgur.com/4sDjIjo.png) 而我們要找的 $\sqrt{2}$ 答案應該就在這個區間。 ![](https://i.imgur.com/GoMIEPj.png) 藉由這樣細分刻度的方法,我們可以將 $\sqrt{2}$ 的答案逼近到小數點後第一位,知道了 $\sqrt{2}$ 的值介於 `1.4` 和 `1.5` 之間。這個方法就稱為十分逼近法。 再一次利用十分逼近法,我們將 `1.4` 和 `1.5` 之間再細分為 10 等分: ![](https://i.imgur.com/22cD3a3.png) 這一次跨越 `2` 的區間落在 `1.9881` 和 `2.0164` 之間: ![](https://i.imgur.com/MYb3JlZ.png) 在這個關鍵的區間我們可以再次觀察到: ![](https://i.imgur.com/AaVuzus.png) 因此確定了 $\sqrt{2}$ 在小數點後第 2 位的數值,$\sqrt{2}$ 的值會大於 `1.41`,而小於 `1.42`。如此重複運用十分逼近法可以求得更精確的 $\sqrt{2}$ 數值。 ### Google 內建的計算機 根據平方根的定義,一個數 n 的平方根會滿足 n = (n平方根)^2^。如果只考慮 n 平方根是正整數的部分,n 的平方根 = $\sqrt{n}$。 平方根的英文叫做 square root,在數學表示式裡常常會用縮寫 `sqrt` 表示平方根,$\sqrt{n}$ 也可以記成 n 平方根 = `sqrt(n)`。 Google 的網頁搜尋列支援計算機功能,我們可在 Google 搜尋列鍵入`sqrt(2)`: ![](https://i.imgur.com/YRk4qfd.png) 這時 Google 會顯示出一個計算機的畫面,告訴我們 2 的平方根等於`1.41421356237`: ![](https://i.imgur.com/0y5ysVs.png) 這個看似簡單的動作事實上包含了輸入輸出的步驟和一個內建的平方根演算法;我們一開始在計算機裡輸入 n 的值等於 2,計算機依據內建的平方根演算法幫我們算出 n 平方根 = `1.41421356237`,然後輸出在答案列。 Google 也提供函式繪圖的功能,我們試試 Google 搜尋列中鍵入`y=sqrt(x)`: ![](https://i.imgur.com/Ptn49Db.png) 我們會看到 Google 返回一張 `sqrt(x)` 的圖: ![](https://i.imgur.com/2x85YE2.png) 這張圖的意義在於將函數 `y=sqrt(x)` 的幾何圖形畫在二維的卡氏座標系裡。可見縱軸座標表示的就是 n 平方根,橫軸座標表示的是 n。 `y=sqrt(x)` 的圖表畫出了一條抛物線,每一個 `x` 的點都可以透過平方根函式求得一個對應的 `y` 值,因此每一個橫軸上的 `x` 座標,對應到縱軸的y座標,就可以畫出一個點。例如圖中的 `x = 2.00000347`,平方根函式就會算出對應的 `y = 1.41421479`,然後在座標系描出這個點。 當程式掃描橫軸上很多的 `x` 座標,就可以繪製出這條 `y=sqrt(x)` 的抛物線。 ### 二分逼近法算 $\sqrt{2}$ `y=sqrt(x)`,或說 n 平方根 = `sqrt(n)` 是一條抛物線狀的連續函數,要在這種連續函數上找到 $\sqrt{2}$ 的值,二分逼近法是一種簡單而可靠的計算方法。 二分逼近法有 4 個基本步驟: 1. 先設定左右兩個邊界值。先前已經知道 $\sqrt{2}$ 的值介於 1 和 2 之間,我們將第一個邊界值設在 `y = 1` 的地方,再將第二個邊界值設在 `y = 2` 的地方。 2. 再來以兩個邊界點平均求中間點,在 1 到 2 這個範圍中間點是`y = 1.5`,我們將中間點也標註在線段上。 ![](https://cdn-images-1.medium.com/max/800/1*IQmgNVycCpnvpv2U0uPNPg.png) 3. 接下來檢查`x` 值在落在左右那一個區間內。由於 $\sqrt{2}$^2^ = 2 介於 1 和 2.25,所以我們可以知道 $\sqrt{2}$ 的值會介於 1 到 `1.5`。 ![](https://cdn-images-1.medium.com/max/800/1*TY6VB3lW3jdGiENQAAIz9A.png) 4. 重複步驟 1–3,直到 $\sqrt{2}$ 的值收斂到理想範圍。 ![](https://cdn-images-1.medium.com/max/800/1*kHD8VWf2b47yh6TqzTQD1w.png) ![](https://cdn-images-1.medium.com/max/800/1*iHNYR7NCuAtQyLAJ32YCBQ.png) ![](https://cdn-images-1.medium.com/max/800/1*-bu9Vr33VQEwrcSpgw6z4w.png) ![](https://cdn-images-1.medium.com/max/800/1*cpXuCnzKPN1A9PB8ZsMF-A.png) ![](https://cdn-images-1.medium.com/max/800/1*fRUBeAdfsCSn99QxI51Mlg.png) ![](https://cdn-images-1.medium.com/max/800/1*33pAZ8VkUqydMho9iPki3A.png) ![](https://cdn-images-1.medium.com/max/800/1*xOL0N03P2DLFAFvtKFguYg.png) 用二分逼近法重複到第 8 次可以計算出 $\sqrt{2}$ 的值到小數點後第二位,實際的值會介於 `1.4140625` 和 `1.41796` 之間,不難發現二分計算法收斂的速度不快。 ## 導入遞迴求解 遞迴是程式語言中的一個重要概念。用遞迴法解決問題首先需要找出問題的規律性,然後將問題分解為同類的子問題,重複求解直到確定滿足我們要的答案。 遞迴強大的地方在於允許使用者用有限的語句描述無限的物件。大多數的電腦程式語言支援遞迴法,允許一個函式呼叫它自己,來達到遞迴的目的。 在二分逼近法和十分逼近法的程式裡,我們都用了遞迴的程式技巧。遞迴有三個重要的步驟: 1. 設定問題的初始值。在二分設定法中,我們製做了兩個變數,上限值和下限值。上限值的初始設定為使用者輸入的n值,下限值的初始設定為1。 2. 將一個問題分解為可重複解決的較小的子問題。計算出上、下限值的平均值當做一個n平方根的檢查點,n 平方根的檢查點會將數線分為左右兩半,檢查 n 是落在左段或右段。如果 n 落在左段,則重新設定上限值為n平方根的檢查點。如果 n 落在右段,則重新設定下限值為n平方根的檢查點。重複上面的兩個步驟。如下圖所示,n平方根的檢查點的漸漸逼近真正的n平方根。 ![](https://cdn-images-1.medium.com/max/800/1*BP9FS4mLbWwV1N_9ijnZwg.png) 3. 設定找到答案的條件。如果條件尚未滿足,進行下一次的遞迴呼叫,一旦滿足這個條件則離開遞迴呼叫。 如果 n 平方根檢查點的平方和 n 的絶對值差距在 `0.0000001` 之內,n平方根已經有相當的精準度,則跳出遞迴呼叫。 展示影片: [二分逼近法和十分逼近法求平方根](https://www.youtube.com/watch?time_continue=31&v=PHPj0jLhcnM) ## 二進位系統的平方根 Wikipedia: [Binary numeral system (base 2)](https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Binary_numeral_system_(base_2)) ## Fast Inverse Square Root (平方根倒數) 3D 繪圖經常要計算平方根倒數,原理是牛頓法,避開開根號和除法運算,節省很多計算時間。 《雷神之鎚 III》(Quake III) 的[原始程式碼](https://github.com/id-Software/Quake-III-Arena)直到 QuakeCon 2005 才正式釋出,但早在 2002 年,反平方根快速演算法的程式碼就出現在論壇中。最初人們猜測是 John D. Carmack 寫下了這段程式碼,但他否定這個觀點,並猜測可能是先前曾幫 id Software 最佳化雷神之鎚的資深組譯程式設計師 Terje Mathisen 寫下了這段程式碼,而後者表示,他在 1990 年代初,曾作過類似的實作,確切來說這段程式碼亦非他所作。現在所知的最早實作是由 Gary Tarolli 在 SGI Indigo 中實作的,但他亦坦承他僅對常數 R 的取值做了一定的改進,實際上他不是原作者。向發明 MATLAB 而聞名的 Cleve Moler 查證後,Rys Sommefeldt則認為原始的演算法是 Ardent Computer 公司的 Greg Walsh 所發明,但他也不能確認。 ![](https://i.imgur.com/dSysIc7.png) * Wikipedia: [Fast inverse square root](http://en.wikipedia.org/wiki/Fast_inverse_square_root) * [Chris Lomont 的分析](http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf) * [A Brief History of InvSqrt](https://cs.uwaterloo.ca/~m32rober/rsqrt.pdf) * [揭祕·變態的平方根倒數演算法](http://www.hsfzxjy.site/uncover-the-secret-of-fast-inverse-square-root-algorithm/) ```cpp float InvSqrt(float x) { float xhalf = 0.5f * x; int i = *(int *) &x; i = 0x5f3759df - (i >> 1); x = *(float *) &i; x = x * (1.5f - xhalf * x * x); return x; } ``` ## 參考資料 * [Scratch & Math: 無理的道理(二)](https://medium.com/@peterwei_62634/scratch-math-%E7%84%A1%E7%90%86%E7%9A%84%E9%81%93%E7%90%86-%E4%BA%8C-eeaa3c6ccfa7) * [Number](http://www.csie.ntnu.edu.tw/~u91029/Number.html)