■

多倍長整数を32bitのunsigned long値を要素とするvectorで管理するのだけれども、演算した際の桁あふれをどう扱うか考えてみた。

まずCPUのレジスタにアクセス出来るならばフラグレジスタのCFビットを検査し、桁あふれが起きたかどうかを確認する事が出来る。しかし今回はそこだけアセンブラで書くのも面倒くさいので違う方法を取りたい。（言語レベルで簡単にチェック出来る方法がないかググッが、無さそうな感じだった）

まず、二つの整数A,Bを正の整数とすると加算演算のパターンは
以下の通りが考えられる
a. A+B 
b. A-B
c. -A+B ( -(A-B) )
d. -A-B ( -(A+B) )
本質的には以下の二通りと考えられる
1. A+B
2. A-B
しかし、A>0, B>0なのでA-Bがオーバーフローを起こす事は無い
（ -limit < A-B < limit, limit=2^32)。
これよりA+Bの場合だけ考えるとオーバーフローした場合以下の
ような状態となる

 A+B < A  ... (Ⅰ)

これをオーバーフローの条件とすればよい。

次に正の整数A,B,Cを考える。（Cは桁上がりしてきた整数と考え
られる）この場合、加算演算のパターンは以下の４通りと考えら
れる。

1. A+B+C
2. A+B-C
3. A-B+C
4. A-B-C
  
1の場合)
 B+Cを (I)の条件でオーバーフローしているか調べ、しているな
らばそれをストックしておきオーバーフローしたB+CとAの加算を
(I)の条件でチェックしながら行う

2の場合)
 B-Cが負の場合はA+B-Cはオーバーフローを起こさないのでその
まま。
 B-Cが正の場合はその結果とAの加算を(I)の条件でチェックしな
がら行う

3の場合)
 B-Cが正の場合はA-B+Cはオーバーフローを起こさないのでその
まま。
 B-Cが負の場合はその結果とAの加算を(I)の条件でチェックしな
がら行う

4の場合）
 B+Cを(I)の条件でチェックし、オーバーフローしていなければ
A-B-Cはオーバーフローしないのでそのまま。
 B+Cがオーバーフローした場合、B+Cのオーバフロー後の値をB'
とし以下の２通りが考えられる
  - A-B' > 0
　　この場合リミット値をLとすると加算の結果は -L+A-B'
    であり、これはオーバーフローを起こさない
  - A-B' < 0
    この場合は -L+A-B'がオーバーフローを起こす場合がある
    ので　-(L+ (B'-A))で(I)のチェックを行う。

加算の場合はこれで準備が整った。
次に乗算だけれども以下のように行う

32bitの正の整数A,Bを上16bitと下16bitに分け以下の演算を行う
X = 65535 (=2^15+2^14+...+2^0)
A_h = A >> 16
A_l = A & X

(A*Bの演算結果) = A_l * B_l + (A_h * B_l + A_l * B_h) & X
(A*Bの桁上がり) = (A_h * B_L + A_l * B_h)>>16 + A_h * B_h