Quod Erat Demonstrandum

七月 2, 2009

十進制轉二進制

Filed under: HKCEE, Junior Form Mathematics, mathematics — johnmayhk @ 12:13 pm
Tags: ,

同事在中二的數學考卷擬了一道題：把 101.5_{(10)} 表達成二進制的數字。

整數部分，同學易求，現在的關注點是

0.5_{(10)} 如何轉成二進數？這個也簡單，

0.5_{(10)} = \frac{1}{2} = 0.1_{(2)}

對卷後，梁同學問我，那麼

0.4_{(10)} 如何轉成二進數？

這又是我這個授課員不能秒殺題。

同學，試探究一下：是否任何有理數都可轉成二進數？

對我來說，這仍是開放問題。高手見笑。

最無聊（trivial）的結果是

(a) 任何形如 \frac{n}{2^k} 的有理數必可轉成二進數。（其中 n, k 為正整數）

比如

\frac{5}{64} = \frac{5}{2^6}

由於 5_{(10)} = 101_{(2)}，所以

\frac{5}{64} = \frac{2^2 + 2^0}{2^6} = \frac{1}{2^3}(\frac{1}{2} + \frac{1}{2^3}) = 0.000101_{(2)}

是否只有形如 \frac{n}{2^k} 的有理數，才能轉成二進數？

不一定，大家看看以下的二進數：

0.111\dots_{(2)} = \frac{1}{2} + \frac{1}{2^2} + \frac{1}{2^3} + \dots

學了等比數列和的同學，易知

0.111\dots_{(2)} = 1_{(10)}

這裡揭示了，我們可以運用循環小數來製作二進數。

比如

0.101010\dots_{(2)} = 0.\overline{10} = \frac{1}{2} + \frac{1}{2^3} + \dots = \frac{2}{3}

又例如

0.\overline{110} = (\frac{1}{2} + \frac{1}{2^2}) + (\frac{1}{2^4} + \frac{1}{2^5}) + \dots = \frac{3}{2^2} + \frac{3}{2^5} + \dots = \frac{6}{7}

0.\overline{00101} = (\frac{1}{2^3} + \frac{1}{2^5}) + (\frac{1}{2^8} + \frac{1}{2^{10}}) + \dots = \frac{5}{2^5} + \frac{5}{2^{10}} = \frac{5}{31}

可以看到，上述兩例的答案，其分母都是形如 2^k - 1 的。

如果分數 \frac{a}{b} 的分母 b 形如 2^k - 1 ，是否一定能轉之為二進數？

讓我再給一個頗無聊的結果：

(b) 形如 \frac{2^m}{2^k - 1} （其中 m　為非負整數， k (k > m) 為正整數） 必能轉成二進數。

這是因為

\frac{2^m}{2^k - 1} = \frac{2^{m-k}}{1-\frac{1}{2^k}} = \frac{1}{2^{k-m}} + \frac{1}{2^{2k-m}} + \frac{1}{2^{3k-m}} + \dots

舉例

\frac{1}{7} = \frac{2^0}{2^3 - 1} = \frac{1}{2^3} + \frac{1}{2^6} + \dots = 0.\overline{001}
\frac{2}{7} = \frac{2^1}{2^3 - 1} = \frac{1}{2^2} + \frac{1}{2^5} + \dots = 0.\overline{01001}_{(2)}

從上面兩例，我隨即想：

\frac{3}{7} = \frac{1}{7} + \frac{2}{7} = 0.\overline{001} + 0.\overline{01001} = 0.\overline{011}_{(2)}

咦，這豈不是把 \frac{3}{7} 轉化為二進數？於是我猜想

(c) 形如 \frac{a}{2^k - 1} （其中 a, k 為正整數）的有理數必可轉為二進數

比如

\frac{5}{7} = (2^2 + 2^0)(\frac{1}{2^3} + \frac{1}{2^6} + \dots) = (\frac{1}{2} + \frac{1}{2^4} + \dots) + (\frac{1}{2^3} + \frac{1}{2^6} + \dots)
=\frac{1}{2} + \frac{1}{2^3} + \frac{1}{2^4} + \frac{1}{2^6} + \dots = 0.1\overline{011}_{(2)}

不過有時有一些要進位的情況，要小心考慮。

循環小數已玩過，那麼無窮不循環的情況如何？比如

0.1011011101111\dots_{(2)} = ?

嗯，似乎不能有一概而論（就算是十進制時也不一定可以把它輕易變成某個無理數的 “closed form”），所以，都是停筆，有機會再想。

那麼：0.4_{(10)} = ? 請繼續看看。

- – - – - – - – - – - – - – - – - – - – - – - – -
後記 (12:00 a.m.)

中二教科書用「除法」把十進整數化為二進數，至於分數的，我嘗試用「乘法」。

\frac{1}{7}
= \frac{1}{2^3}\frac{2^3}{7} (分子分母同時乘 2 的冪，以致分子剛剛大於分母 7)
= \frac{1}{2^3}(1 + \frac{1}{7})
= \frac{1}{2^3} + \frac{1}{2^3}\frac{1}{7} (看 \frac{1}{7} 又走了出來)
= \frac{1}{2^3} + \frac{1}{2^3}(\frac{1}{2^3} + \frac{1}{2^3}\frac{1}{7}) (又重覆出現，可歸納了)
\dots
= \frac{1}{2^3} + \frac{1}{2^6} + \frac{1}{2^9} + \dots
= 0.\overline{001}_{(2)}

好了，不用 WolframAlpha，徒手做

\frac{2}{5}
= \frac{1}{2^2}\frac{8}{5} (分子分母同時乘 2 的冪，以致分子剛剛大於分母 5)
= \frac{1}{2^2}(1 + \frac{3}{5})
= \frac{1}{2^2} + \frac{1}{2^2}\frac{3}{5}
= \frac{1}{2^2} + \frac{1}{2^3}\frac{6}{5} (分子分母同時乘 2 的冪，以致分子剛剛大於分母 5)
= \frac{1}{2^2} + \frac{1}{2^3}(1 + \frac{1}{5})
= \frac{1}{2^2} + \frac{1}{2^3} + \frac{1}{2^3}\frac{1}{5}
= \frac{1}{2^2} + \frac{1}{2^3} + \frac{1}{2^6}\frac{2^3}{5} (分子分母同時乘 2 的冪，以致分子剛剛大於分母 5)
= \frac{1}{2^2} + \frac{1}{2^3} + \frac{1}{2^6}\frac{8}{5} (嗯，\frac{8}{5} 又出現了！)
= \frac{1}{2^2} + \frac{1}{2^3} + \frac{1}{2^6}(1 + \frac{1}{2} + \frac{1}{2^4}\frac{8}{5})
= \frac{1}{2^2} + \frac{1}{2^3} + \frac{1}{2^6} + \frac{1}{2^7} + \frac{1}{2^{10}}\frac{8}{5}
= \frac{1}{2^2} + \frac{1}{2^3} + \frac{1}{2^6} + \frac{1}{2^7} + \frac{1}{2^{10}}(1 + \frac{1}{2} + \frac{1}{2^4}\frac{8}{5})
= \frac{1}{2^2} + \frac{1}{2^3} + \frac{1}{2^6} + \frac{1}{2^7} + \frac{1}{2^{10}} + \frac{1}{2^{11}} + \frac{1}{2^{14}} + \dots
= 0.0\overline{1100}_{(2)}

存在了這個所謂算法，是否一定可以化十進分數為二進數小數？

有沒有較為簡潔的證明？仍在思考中。

=========================================

後後記

後記中的所謂算法太煩，我想了一個連小學生都應該懂的算法，去片：

9個回應 »

  1. use the powerful wolfram alpha
    search” convert 0.4 to base 2″

    Comment by 路人甲 — 七月 2, 2009 @ 7:39 pm | Reply

  2. 比路人甲快我一步！Thx！

    因在校外開會，晚上回家再打打後記（見內文）。

    Comment by johnmayhk — 七月 2, 2009 @ 11:30 pm | Reply

  3. [...] 3年沒算數學題 老師教的東西也差不多忘得一乾二淨 剛剛在wordpress 推介看到這個 Quod Erat Demonstrandum 數學blog的文章 十進制轉二進制 [...]

    Pingback by 我的數學情意結 « — 七月 3, 2009 @ 1:59 pm | Reply

  4. 任何大於二的正整數都可以當成進位的基底來表示所有的有理數，不只2和10。
    表為有限小數或無限循環小數。

    Comment by Yee — 七月 3, 2009 @ 10:49 pm | Reply

    • 如何以非算法的方式保證該 bijection 存在？即以數系中的什麼特性來保證它。

      Comment by johnmayhk — 七月 4, 2009 @ 5:56 pm | Reply

  5. 阿sir後後記的方法確實鬼斧神工,阿sir對數學的運算概念實在融會貫通,你的數感很強,在下甘拜下風

    Comment by 廢過大佬檠 — 七月 5, 2009 @ 12:11 pm | Reply

    • 所謂「青出於藍」，不日，你們的數學功力，必然遠超我之上，這就是我由 Day 1 開始的願望。

      Comment by johnmayhk — 七月 5, 2009 @ 5:39 pm | Reply

  6. 如果懂得二進制加減，應該也可以利用 “後後記” 的同樣方法計算得出同樣結果。

    即 2 = 10_(2)，5 = 101_(2)。2/5= 10_(2) / 101_(2)。利用長除法找餘數重複出現應可得知。

    但令我感興趣的是，既然電腦以二進制計算，如何處理 0.4 這些二進制中的 “循環小數”？
    若取很多小數位的近似值的話，0.4 的次方便用很多的計算時間？

    Comment by hotcooljoe — 七月 19, 2009 @ 2:48 am | Reply

  7. 我投降了 ……

    Comment by 森林木 — 七月 28, 2009 @ 11:10 pm | Reply


以RSS訂閱此篇文章的意見 TrackBack URI

Leave a comment

Blog at WordPress.com.