[分享] 大數運算

[math120908 (小小郭)]

話說因為Worksheet有出現簡單的大數，所以就PO了篇簡單的大數文給大家參考:p。
//是說我絕對不會說內容是偷偷改自之前編的講義的:P
--

大部分程式語言中的資料型別,其所能儲存的值都有一定的範圍,那若要做的運算超出
這個範圍時該怎麼辦?或所需求精準度很高時該怎麼做?等咻碰嗎?!當然不可能啦,所以
這時候...嘿嘿~就必須自己寫一種資料結構了。

§大數的資料結構實踐(Data Structure Implementation)

我們分別使用一個陣列來儲存各個位數還有一個變數來紀錄大數。
例如:21474836472147483647
以上用大數儲存就如下

index : 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
value : 7 4 6 3 8 4 7 4 1 2 7  4  6  3  8  4  7  4  1  2

length = 20

話說為什麼是這樣反過來存呢？(其實我是正的存!只是index是從左到右寫而已XD(無誤))
因為這樣兩個數字在做運算的時候，第i位才會剛好是對到陣列的第i-1格～

嗯...我只是覺得這樣比較好寫啦XD，當然也是有人一直以來都是反過來做= =+。
而且我看大家作業大部分都反過來作，感覺這樣還要去對齊位數有點麻煩:p，如果一開始
輸入的時候就把字串reverse，可能會比較好做一點這樣...。

※註:因為在 C 的語法中,陣列是由 0 開始存取,所以實際位數是到 length-1。但是以下
偽代碼,陣列都是由 1 開始到 length,這點要注意一下。

§大數加法(Addition)

一般來說,我們都是利用直式加減乘除法來做運算,所以說以下的運算方法,皆是使用
直式運算方式來思考。
BIGNUM_ADD (bignum a,bignum b)
  create c as a bignum
  c.length ← max( a.length , b.length )
  for i ← 1 to c.length
     do c[i] ← a[i] + b[i]
  for i ← 1 to c.length
     do c[i+1] ← c[i+1] + c[i] / 10
        c[i] ← c[i] mod 10
  if c[c.length] ≠ 0
    then c.length ← c.length + 1
  return c

§大數減法(Subtraction)

基本上有兩種想法,一種是最基本的借位補位直式減法,也就是平常最常用的方法。
再來另一種,就是利用補數的概念,來算減法。
也就是先求被除數的補數,再利用加法將兩數相加,最後在減掉多出位即可。
例如:
2147483647 – 123456789
= 2147483647 + (10000000000 – 0123456789) –1000000000
= 2147483647 + 9876543211 – 1000000000
= 12024026858 –1000000000
= 2024026858
其中 9876543211 為 0123456789 的 10 補數。而至於實際寫法,就請大家自己練習了。

§大數乘法(Multiplication)

與直式乘法相同,將兩邊的每一位相乘即可。其中要注意的是 a 的第 i 位乘以 b 的第 j
位,會對應到 c 的第 i + j 位,所以我們有以下的寫法。
BIGNUM_MULTIPLY (bignum a,bignum b)
  create c as a bignum
  c.length ← a.length + b.length
  for i ← 1 to a.length
     do for j ← 1 to b.length
           do c[i + j] ← c[i + j] + a[i] * b[j]
  for i ← 1 to c.length
     do c[i+1] ← c[i+1] + c[i] / 10
        c[i] ← c[i] mod 10
  if c[c.length] ≠ 0
    then c.length ← c.length + 1
  return c

§大數除法(Division)

既然乘法是連加,那除法可以用連減的方式來解決囉?當然是可以的,只是當商數非常
大的時候,你的連減就會變的非常的慢,而且,我剛剛乘法也不是用連加的不是嗎 XD。
所以我們還是用老方法,直式除法,就像我們平常熟悉的,一位一位去減下來,所以有以下
的代碼。

BIGNUM_DIVIDE (bignum a,bignum b)
  create c as a bignum
  b move right for a.length – b.length digits // b * 10^(a .length-b.length)
  for i ← a.length – b.length downto 0
     do if a > b
          then c[i] ← c[i] + 1
               a ← a–b
        else if a <= b
            then b move left for 1 digit       // b / 10
     c.length ← a.length – b.length
     if c[c.length] = 0
       then c.length ← c.length - 1
  return c

別看上面寫的短短的,自己寫過就會知道有多不好寫了(笑)。

§大數優化(Bignumber optimization)

事實上,大數運算還可以運用一些技巧來進行優化,想一想?宣告的陣列本身的空間,
只記一位會不會浪費掉?因此很明顯的,我們可以利用「壓位數」的技巧來使運行速度增快
,而壓位數的意思就是代表陣列裡一格不只存一位的意思,但是壓位數須要注意的是不要不
小心 Overflow 了,特別是乘法部分。而且壓位數的除法會變得複雜一點點,這就留給你們
自己想了。

※建議:本人不建議直接使用 long long 存取(記憶體使用大並且也比較慢),而較建議用
int 存 7,8 位,只要運算過程記得形態轉換就 OK 了。

§小結(Conclusion)

以上介紹的就是基本的大數運算,不過上面只討論正數問題,當遇到負數怎麼辦呢,有
小數點又怎麼辦呢?嘿嘿!這時候就必須考驗你的智慧了!!
剛開始的時候大數常常會被直接當成一種考題,但是到後來會變成一種出題者心機的手
段,所以當看到一個題目時,先估計數值範圍是必要的!但是也不要以為,假如輸出答案是
在 int 或 long long 內就不用寫大數,在運算過程中 Overflow 或 Downflow 是常有的
事,所以大數的適用與否,必須經過適當的估計,當用則用,以免造成無法挽回的後果!!

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.82
推 icehall:推一個
※ 編輯: math120908      來自: 140.112.30.82        (10/27 08:58)
推 m80126colin:用心推......話說一個位數存7.8位要怎麼乘呀@@
→ math120908:+-*作法都差不多 改成10^7進位之類的就好了~
→ math120908:除法就要另外想XD 本來除法就是很麻煩的東東:p~~
→ math120908:哦還是你是要問存7,8位會overflow要怎麼乘@_@...?
→ math120908:反正就是途中先轉成long long之後再轉回來吧XDrz
推 bztfir:先推再說!!!!!
推 OppOops:推！！！
推 cluster159:推
推 ryan8175ptt:沒時間仔細看 先轉寄(按)......先推再說!
推 jimmy9988:push!!!
推 monkey020626:推~
推 yuscvscv:之前好像有看過有文章說轉long long效率不會高太多?
推 williamiced:推
推 MrGreat:推~ 真用心
推 alan0511:推