The Fraction from a Decimal

定點數運算常用於 embedded systems 中，因為大部分低階的 MCU （例如： 8051, PIC, AVR 等）開發環境雖提供浮點運算，卻是軟體模擬的，除了慢，還明顯佔用原本就少得可憐的記憶體空間。 C/C++ 語言雖無定點數運算專用語法，程式員卻可通過手動調整，有效以整數運算完成相同效果。

定點數運作的原理，簡言之，就是將原來的實數（real number）或者小數（decimal），改寫成分數（fraction）：如果 x 是個含小數的實數，我們可以找來兩個整數（p, q），將它們相除，來近似原來的 x （p/q ~= x）。

實務上人們可能還會要求上述的 q 要是 2 的冪次，因為電腦處理的都是 0, 1 的二進位運算， q 表示成 2 的冪次可以達到較高的精度；另一個原因我想是許多 f/w 程式員都患了 shift 偏執症 :p

有個友人前陣子寫了江湖一點訣，還在 CSZone 引發一陣討論，有人提到說他用工程計算機把十進位數轉成二進位就搞定了，何苦寫程式來 try 出 p, q 。

最近興起，也想把數字轉成二進位以找出 p, q 時，發現手邊沒有合用的計算機，不爽之餘，再次以爬說語搞定這件事：

"""
File: fract.py
Converts a decimal into an equivalent fraction.
"""
__author__ = "Jiang Yu-Kuan, yukuan.jiang(at)gmail.com"
__date__ = "2008/05/17"
__revision__ = "1.2"

def fract(x, bits=8, deduced=False):
    """Find p, q such that p/q ~= x and p, q < 2**bits
    """
    p, q = x, 1
    while p < 2**bits:
        if deduced:
            print "%f = %d/%d" % (round(p)/float(q), round(p), q)
        p *= 2
        q *= 2
    return int(p/2+0.5), q/2

if __name__ == "__main__":
    p, q = fract(3.1415926535, deduced=True)
    print "p=%d, q=%d" % (p, q)

用例：

J:\trial\python>python -i fract.py
3.000000 = 6/2
3.250000 = 13/4
3.125000 = 25/8
3.125000 = 50/16
3.156250 = 101/32
3.140625 = 201/64
p=201, q=64
>>> from math import e, pi
>>> e
2.7182818284590451
>>> fract(e)
(174, 64)
>>> 174/64.
2.71875
>>> pi
3.1415926535897931
>>> fract(pi)
(201, 64)
>>> 201/64.
3.140625
>>>

Tags: [embedded] [Python] [math]