今日は bignum.c のリファクタリングや最適化だけでした。
akr:r41942 2013-07-13 23:03:13 +0900
bignum.c のビットシフト演算を行う関数を統合して big_shift2() および big_shift3() という関数でシフト方向によらず処理できるようにしています。
akr:r41955 2013-07-14 00:16:23 +0900
bignum.c の乗算処理の最初に呼ばれる bary_mul_precheck() という関数で x もしくは y が 1 の時に他方をコピーするだけの簡易処理を実施していたところを x が2の累乗の時にシフト演算に落とすようにしています。ただ y が 1 の時の処理というのが x の配列長が 1 の時の if の中に入っているため x が大きくて y が 1 の時にショートカット処理がされませんが、この前に xl と yl の比較をして xl が yl 以下になるように入れ替える処理が存在するため実は xl だけチェックすれば良かったみたいです。
svn:r41956 2013-07-14 00:16:27 +0900
version.h の日付更新。
akr:r41959 2013-07-14 00:19:48 +0900
bignum.c の big_shift() で long の引数を正負反転して unsigned long にキャストするところでオーバフローを考慮して -(n+1) してキャスト後に +1 するようにしています。
これは n = -(2**x) の時に(x は sizeof(long)*8-1)
- -n = (2**x) (← この時点で long は 2**x を表現できない(正の数は 2**x-1 まで)のでオーバフローしている)
- (unsigned long)(-n) = (unsigned long)(2**x) (途中オーバフローしているので厳密には未定義)
となるのを
- n+1 = -(2**x-1)
- -(n+1) = 2**x-1 (← これは long の範囲内に収まっている)
- (unsigned long)(-(n+1)) = (unsigned long)(2**x-1)
- 1+(unsigned long)(-(n+1)) = (unsigned long)(2**x)
でオーバフローしないようにしているかと思います(この部分は n < 0 の条件分岐内なので n = 2**x-1 の時は考えなくても良い)。
akr:r41960 2013-07-14 00:36:18 +0900
Bignum#[] の実装で負の数の時に配列をなめる処理をしていて遅かったのを改善しています。
akr:r41961 2013-07-14 00:38:52 +0900
bignum.c で未使用になっていたマクロ DIGSPERLONG と DIGSPERLL の定義を削除しています。
