查看完整版本 : 任意大整數 16 進位轉 10 進位

assembly.jc 2019-2-17 06:35 PM

任意大整數 16 進位轉 10 進位

問題來源係用 assembly 編寫程式計算 Fibonacci number,但要轉成 10 進位顯示,唔何以用任何 library 幫助。而且要係類似 FreeDos 咁嘅 real mode 環境執行,即係除法和加法運算指令只限於 16 Bit。計算 Fibonacci number 倒是問題不大,因有 Carry flag 幫助,任意大整數都可以相加。但 16 進位轉 10 進位需要用到除法,就比較難少少。問題已經解決,今次出帖是想比大家挑戰一下: 試用 assembly 計算第 2019 個 Fibonacci number,並用10 進位顯示。

第 2019 個 Fibonacci number 係 [url=https://computer.discuss.com.hk/viewthread.php?tid=27950623&page=1]https://computer.discuss.com.hk/viewthread.php?tid=27950623&page=1[/url]

煙民母親生賤種 2019-2-18 01:42 AM

[quote]原帖由 [i]assembly.jc[/i] 於 2019-2-17 06:35 PM 發表 [url=https://computer.discuss.com.hk/redirect.php?goto=findpost&pid=495002135&ptid=28040619][img]https://computer.discuss.com.hk/images/common/back.gif[/img][/url]
問題來源係用 assembly 編寫程式計算 Fibonacci number,但要轉成 10 進位顯示,唔何以用任何 library 幫助。而且要係類似 FreeDos 咁嘅 real mode 環境執行,即係除法和加法運算指令只限於 16 Bit。計算 Fibonacci number 倒是問題不大,因有 Carry flag 幫助,任意大整數都可以相加。但 16 進位轉 10 進位需要用到除 ... [/quote]你認為呢度,除左閣下,仲有人識嗎?:fst_016:

darigold 2019-2-18 05:13 AM

先不討論 assembly , 那只是實現的細節。
如果用傳統的 remdiv 算法,那速度應該會相當慢。
除了 BCD ,有沒有更好的算法?

sswroom 2019-2-18 02:24 PM

[quote]原帖由 [i]darigold[/i] 於 2019-2-18 05:13 AM 發表 [url=https://computer.discuss.com.hk/redirect.php?goto=findpost&pid=495022279&ptid=28040619][img]https://computer.discuss.com.hk/images/common/back.gif[/img][/url]
先不討論 assembly , 那只是實現的細節。
如果用傳統的 remdiv 算法,那速度應該會相當慢。
除了 BCD ,有沒有更好的算法? [/quote]BCD計加減數很難, 直接用DIV轉10進位最簡單, 我20年前已用過這方法, 速度不是很慢......

除10的Inner loop有概是這樣, dx是餘數: (MASM Syntax)[code]lea si,valBuff[valSize]
mov cx,valSize
mov bx,10
xor dx,dx
shr cx,1
lop:
lea si,[si-2]
mov ax,word ptr [si]
div bx
mov word ptr [si],ax
loop lop[/code]

darigold 2019-2-19 06:04 AM

[quote]原帖由 [i]sswroom[/i] 於 2019-2-18 02:24 PM 發表 [url=https://computer.discuss.com.hk/redirect.php?goto=findpost&pid=495039160&ptid=28040619][img]https://computer.discuss.com.hk/images/common/back.gif[/img][/url]
BCD計加減數很難, 直接用DIV轉10進位最簡單, 我20年前已用過這方法, 速度不是很慢......

除10的Inner loop有概是這樣, dx是餘數: (MASM Syntax)lea si,valBuff[valSize]
mov cx,valSize
mov bx,10
xor dx,dx
shr cx,1
lop:
lea si,[si-2]
mov ax,wo ... [/quote]
看不明白,這只是 inner loop ?
我想大數除法每做一次都要 go through 整個大數吧?

我的 remdiv algorithm 是這樣的。

結果=""
while(大數 > 10)
{
  大數 remdiv 10 = floor(大數/10) 和餘數。
  結果 = 餘數 concat 結果
}

問題係 floor (大數 / 10) 不容易計,在十六進位表達,成個數都會變晒,局住 scan 晒成個大數。
如此 iteration 要做 log 大數次,每次大既要 process O(log n) 個 bytes 。
整體 algorithm 速度是 (log n) squared 。

有冇更快既 algorithm ?


[url]https://en.wikipedia.org/wiki/Division_algorithm#Goldschmidt_division[/url]

[[i] 本帖最後由 darigold 於 2019-2-19 06:07 AM 編輯 [/i]]

sswroom 2019-2-19 10:03 AM

[quote]原帖由 [i]darigold[/i] 於 2019-2-19 06:04 AM 發表 [url=https://computer.discuss.com.hk/redirect.php?goto=findpost&pid=495070113&ptid=28040619][img]https://computer.discuss.com.hk/images/common/back.gif[/img][/url]

看不明白,這只是 inner loop ?
我想大數除法每做一次都要 go through 整個大數吧?

我的 remdiv algorithm 是這樣的。

結果=""
while(大數 > 10)
{
  大數 remdiv 10 = floor(大數/10) 和餘數。
  結果 = 餘數 concat 結果
}

問題係 floor (大數 / 10) 不容易計 ... [/quote]
我寫的部分相當於:
dx = LargeInteger % 10
LargeInteger /= 10

用Assembly寫是很容易的~~

assembly.jc 2019-2-19 04:22 PM

[quote]原帖由 [i]darigold[/i] 於 2019-2-18 05:13 AM 發表 [url=https://computer.discuss.com.hk/redirect.php?goto=findpost&pid=495022279&ptid=28040619][img]https://computer.discuss.com.hk/images/common/back.gif[/img][/url]
先不討論 assembly , 那只是實現的細節。
如果用傳統的 remdiv 算法,那速度應該會相當慢。
除了 BCD ,有沒有更好的算法? [/quote]

是,都係用  remdiv 算法。sswroom 兄已給出答案了,利用長除法,一次可處理16 個 bits (trick 位係 div 會自動把餘算放回 dx, 下次再除會用 dx:ax / dividor)。
如果只係計 第 2019 個 Fibonacci number 應該夠用 (小弟未試)。這個數有 422 個 digits, 約 180 個 bytes, 90 個 Words,除一次 10,要行 div instruction 90 次,成個數就行 422 * 90 次。實際用時要睇返 cpu 處理 div 的速度,可參考[url=https://superuser.com/questions/643442/latency-of-cpu-instructions-on-x86-and-x64-processors]https://superuser.com/questions/643442/latency-of-cpu-instructions-on-x86-and-x64-processors[/url]。

darigold 2019-2-20 09:46 AM

可能是我想多了。


有一次我要計 9^(9^9) 發現用 Python 計非常慢,但用 Haskell 相當快,這才想到要找快速大數除法算法。


對了,有沒有人見過汪汪?好似好耐冇出沒
頁: [1]
查看完整版本: 任意大整數 16 進位轉 10 進位