Monday, May 19, 2008

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: [] [] []

6 comments:

Tim Wu said...

如果是為了效率

1. 不覺得p/q表示法會比compiler內建的soft-float來得快耶, 轉換過程花的時間太長了, 精度也不見得好到哪去.

2. 文章裏面說的轉binary其實應該就指這招,
http://en.wikipedia.org/wiki/Q_(number_format)

像 freetype2就是用26.6來表達座標,
同樣32bit, 26 bits給整數, 6 bits給浮點.

http://freetype.sourceforge.net/freetype2/docs/glyphs/glyphs-6.html

PS. freetype2 在 16bit MCU 一樣跑得很順喔!

York said...

To Tim,

其實概念上是相通的:

p/q ~= x
q = 2**Q

=> x ~= p<<Q

簡言之,都是要決定適當的 Q 值,以保持足夠的精度。

我這篇著重於以分數來逼近某個數(例如:PI, E 等)。沒探討到後續的四則運算要怎麼處理。

在作四則運算時,你提到的 Q number 是個系統化的運算方法。另一方面,對一些簡單的應用,可能不必那麼「正規」,反正達到加速的目及足夠的精度,也就行了。

Wallace said...

我就是那位用工程計算機(小算盤)來轉的。看來這樣的作法不太人性,沒人了解,才會讓板主又寫了一次程式。
我也不是一定要使用shift,不過做為Firmware工程師,有時要寫FPGA。Shift在FPGA中省下的運算及時間會比較多。沒辦法,因為每一個Bits都要好好利用。

York said...

To Wallace,


你用的竟然是小算盤,這真的太不人性了!

我就是叫出小算盤,找不到可用於小數的十進位跟二進位轉換,手邊剛好也沒其他工程計算機,一氣之下,索幸用 Python 寫的。

另外,我會覺得一股腦用 shift 有點偏執,一個很重要的理由是它未必比較快,code size 也未必較省,這視 Compiler 及底層的硬體而定。

現在我 coding 時的心態是,除非明顯造成妨礙,否則可讀性優先。

Anonymous said...

To Wallace
請問用小算盤該怎麼按?
謝謝

Wallace said...

叫出小算盤,使用工程型。就有16,10,8,2位元轉換。但16,8,2位元數只能接收整數。想要轉出小數部分,要符合位元移動運算,但小算盤沒有。變通的方法是乘以2的次方,又因在16,8,2位元數每四位數有分開,所以乘以2的4次方倍會比較好看。乘好次方再轉就可以看到。我個人習慣乘2的32次方。
以pi為例乘以2的32次方結果為13493037704.522018958598982648896
轉換16為3 243F 6A88就等於0x3.243F 6A88。