Quod Erat Demonstrandum

2009/07/02

十進制轉二進制

Filed under: HKCEE,Junior Form Mathematics,mathematics — johnmayhk @ 12:13 下午
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″

    迴響 由 路人甲 — 2009/07/02 @ 7:39 下午 | 回覆

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

    因在校外開會,晚上回家再打打後記(見內文)。

    迴響 由 johnmayhk — 2009/07/02 @ 11:30 下午 | 回覆

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

    通告 由 我的數學情意結 « — 2009/07/03 @ 1:59 下午 | 回覆

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

    迴響 由 Yee — 2009/07/03 @ 10:49 下午 | 回覆

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

      迴響 由 johnmayhk — 2009/07/04 @ 5:56 下午 | 回覆

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

    迴響 由 廢過大佬檠 — 2009/07/05 @ 12:11 下午 | 回覆

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

      迴響 由 johnmayhk — 2009/07/05 @ 5:39 下午 | 回覆

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

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

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

    迴響 由 hotcooljoe — 2009/07/19 @ 2:48 上午 | 回覆

  7. 我投降了 ……

    迴響 由 森林木 — 2009/07/28 @ 11:10 下午 | 回覆


RSS feed for comments on this post. TrackBack URI

發表迴響

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

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 變更 )

Twitter picture

You are commenting using your Twitter account. Log Out / 變更 )

Facebook照片

You are commenting using your Facebook account. Log Out / 變更 )

Google+ photo

You are commenting using your Google+ account. Log Out / 變更 )

連結到 %s

在 WordPress.com 建立免費網站或網誌.

%d 位部落客按了讚: