公度、輾轉相除、還有世界的和諧

各位好,歡迎回到「讀數怡智」。

今天要介紹的是一個非常古老但厲害的演算法:輾轉相減/除。這很可能是目前仍在使用中的最悠久而古老的算法

這個算法的精神,就是用來回答上週我們最後碰到的問題:要如何有效地找到最適合的度量呢?

簡單一點來說,今天我們被賦予了兩個量,要如何找到第三個量,也就是所謂的度量,能讓我們用來數完第一個量,也能夠用來數完第二個量呢

擷取

 

於是我們回頭仔細地想了想度量的性質:
「如果這個度量,能夠數完第一個量A,也能夠數完第二個量B,那麼他一定可以數完A扣去B的總量吧?」

舉例來說,如果我們有兩根竹子A和B,竹子A能夠分成若干個竹節,竹子B也能夠分成幾個竹節。如果我們將比較長的,拿來剁去比較短的相等長度,剩下的一定也是若干個竹節阿

就這樣大刀一揮,剁完之後,我們便得到了一共兩種長度的竹子:一個是原先較短的長度,另外一個是剁完剩下的長度。
等一下…這個問題怎麼好像有點熟悉
這不就是跟剛剛同樣的問題嗎?雖然長度有所變化,但我們的目的仍然是找尋可以同時度量這兩個新長度的量阿

於是我們可以再次進行這個操作、反覆的進行這個操作,不停地把竹子的剩餘長度縮短。而的動作,在數字上看來就是所謂的「相減」。持續減著減著,可能發現原先較長的竹子A,長度居然比B還短了!這時候也不太需要驚慌,改用剩餘的竹子A去剁取竹子B就好了。這就是所謂的「輾轉」,而兩個合併就是所謂的「輾轉相減」

重複的「相減」我們可以合併在一起做稱為「相除」,因此「輾轉相減」也可因此稱為「輾轉相除」

如此減著減著,直到某次我們可能發現:
其中一個量居然可以完整的度量另外一個量了
這同時也代表這個量可以完整的度量再前面的一種量,更前面的一種量,前前前面的量…
所有前面在操作中曾經出現的各種量,都可以被這個最後找到的量完整的度量,包括我們最一開始被賦予的那兩個量。

這時候我們知道,這個新找到的量,就會是我們朝思暮想的那個,最適合拿來量測原先的兩個量的單位了。因為他既是A的度量,也是B的度量,所以我們就給他一個名字,叫做公度

當然同時是A也是B的度量有很多,但透過剛剛的方法找出來的,會是裡面最大的,所以被稱為最大公度這個方法當然也可以套用到數字上面,所找到的就會是最大公因數,也就是能夠同時整除一開始的兩個數字的第三個數字。例如:

阿財有78頭牛,我有87頭不能再多了,想要找出幾個一組,能簡單的數完我和阿財的牛,那就是

87 –  78 = 9
78 – 9 * 8 = 6,
(也可以很辛苦地減很多次,寫成
78 – 9 = 69, 69 – 9 =60, 60 – 9 = 51, 51 – 9 = 42, 42 – 9 = 33, 33 – 9 = 24, 24 – 9 = 15, 15 – 9 = 6)

9 – 6 = 3
6 – 3 * 2 = 0 (用3除完了!)

因此我們就知道一組三隻,這個組法就能輕易地數完我和阿財的牛數。

當然到了這裡,各位很可能會質疑:你這只是運氣好吧?搞不好就這樣剁半天什麼也沒找到阿?但其實,只要A跟B之間至少有一個公度存在,就算我們不知道他多大,透過這個方法是一定保證會找到東西的

這邊就不詳細的證明了,一個比較簡單的說明就是,每次相除,只要沒有完全度量完,都一定有一個量變得比另外一個更小,如此的往復下去,竹子的長度每次都會縮短,除非因為整除而停止。但我們也知道,只要有一個公度的存在的話,這個量不可能無限的小下去,至少也會比公度大,畢竟再怎麼說,他可是要能夠被公度量測的。
以數字來說,所有的整數都能被1數完,所以一定做的完。附帶一提,在很多年後,法國數學家Gabriel Lamé證明了這個方法用在最大公因數問題上,所需要的步數不會超過最小數字位數的五倍,這也算是相當早期的對於計算複雜度的研究。

換句話說:只要這個世界都能數,我就有辦法數掉他!
從過去的經驗,我們總是能找到一個更小的單位把東西量的更精準,任意兩個量之間應該都有一個公度的存在。任意兩個量之間,都是簡單整數比。

這個世界,真的是能完全被簡單的數字所描述阿!

不知道大家是否相信呢?
很久很久以前,畢達哥拉斯和他的快樂夥伴們,確實就是這麼認為的。他們相信世界的和諧,所有的量,都是能夠寫成兩個整數之比的。
但最後出現的,不是世界的和諧,而是所謂的「數學第一次危機」,還有一場流傳至今的謀殺案….

然而本週的「讀數怡智」就必須要在這裡先告一個段落了,想知道更多的朋友,我們下周六再見!

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com 標誌

您的留言將使用 WordPress.com 帳號。 登出 /  變更 )

Google photo

您的留言將使用 Google 帳號。 登出 /  變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 /  變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 /  變更 )

連結到 %s

WordPress.com.

向上 ↑

%d 位部落客按了讚: