ホーム ] 実行時間計測ラブラリ ] EXIF情報ライブラリ ] 文字式演算 ] クイックソートライブラリ ] 多倍長演算ライブラリ ] 多倍長演算ライブラリU ] 画像処理ライブラリ ]

上へ
多倍長語の構造
プログラミング仕様
インストール
ユーティリティ
数学定数システム
四則演算
数学関数

多倍長演算ライブラリU(CompactPrecision)

技術解説/四則演算

最終更新日:2007/04/26 新規

●概要

 仮数部の配列が固定長なので、MegaPrecision と若干異なる。

●方式

 配列が固定長であるが、常に全長に対して演算すると無駄な時間が生じるので、CompactLong.ValidSize を参照して、末尾の0要素を演算対象から除外するなどの処置を施している。

●関係演算

 先ず、符号、指数により篩いし、両者同じであると、仮数部の比較を行う。ValidSize が大きいほうに合わせて比較する。

●加減算

 符号、値の大小関係により加算か減算を決定し、指数部の大きい方を基準とし、小さい方を同じ指数になるまで、仮数部をシフトダウンし、桁あわせを行う。この時、512要素からはみ出した部分は切り捨てられる。要素間の加減算は、末尾の0要素は省略される。

 最終的なキャリー/ボローは変数で持ち、その有無で正規化方法が変わる。指数は大きい方を基準にし、正規化の結果で調整する。

●乗算

 従来方式の乗算で、指数部の加算と、仮数部配列間の乗算で行う。

○Base×Base、配列×Base

 一方が、1億(Base)未満であれば、他方の配列に直接ネイティブ乗算を行う。双方がそうであれば、単なる乗算を行う。これらは非常に高速となる。

○配列×配列

 双方が、Base以上であれば、この乗算となる。筆算による乗算アルゴリズムをそのまま実行しているだけである。双方のValidSize部分のみ乗算を行っている。

●除算

 従来方式の除算で、指数部の減算と、仮数部配列間の除算で行う。多倍長の除算は、公称精度+拡張精度(4096桁)まで商を求めるので、完全ネイティブ除算はできない。

○配列/Base

 除数が、1億(Base)未満であれば、他方の配列に直接ネイティブ除算を行う。

○配列/配列

 この場合は、除算の原理である、A/B は A に B は、何回現れるか? を算出する。つまり、 A - Q*B = 0 となる Q を減算の繰り返しで求める。但し、一般には、0 とならないので、適当に演算を打ち切る。今回は、公称精度+拡張精度(4096桁)が限度なる。除算の場合、ValidSize はあんまり関係がなく、それに拠らずに、商は、4096桁求めるからである。但し、途中で現れる、減算や桁移動ではValidSizeが関係する。

 商は、10進の1桁づつ頭から求めて行く。A()/B() に於いて、ある時点での商は、A => B の場合に、B を減算できる回数となる。しかし、常に減算をすれば、平均、商1桁当たり、5回の A - B が必要となり、時間が掛かる。通常は、仮商として、Q = A(0)/B(0) とし、A <= Q*B を検算して、補正する方法をとる。除算中、A() は、刻々と変化するが、B() は一定となる。また。Q は、0 〜 10 の整数だから、Q*B は、その除算中は、高々10個の定数と見なせる。これらを除算開始時に予め算出しておけば、

 A - Q*B → A - BB(Q)

とできる。BB() は、Q*B のテーブル。つまり、Q*B の毎回の乗算が不要となる。

以上のコード例を示す。

AA() は被除数配列、BB() は除数配列,C()は商配列

Dim BBB(10)() As Integer    'Q*B のテーブル
AL = GetValidSize(AA)
BL = GetValidSize(BB)
L = Math.Max(AL, BL)
For i = 1 To 10
   ReDim BBB(i)(FullSize - 1)
   NumAdd(BB, BL, DD, BL, BBB(i), CU)    'Q*Bテーブルの生成
   Array.Copy(BBB(i), DD, FullSize)
Next
Array.Clear(C, 0, FullSize)
For i = 0 To FullPrecision - 1
   If AA(0) >= BB(0) Then
      Q = AA(0) \ BB(0)            '仮商
      DD = BBB(Q)               'Q*B を得る
      Select Case NumComp(AA, DD)   'A と Q*B を比較する
         Case CompactRelation.Equal    '= の場合は割り切れたことになり、除算は終了
            SetDigit(C, i, Q)                   '商Q を所定の桁位置に格納
            Exit For
         Case CompactRelation.GraterThan   'A > Q*B なので、Q は正しい
            SetDigit(C, i, Q)
         Case Else                                     'A < Q*B なので補正する
            Q = Q - 1
            If Q > 0 Then
               SetDigit(C, i, Q)
               DD = BBB(Q)
            End If
      End Select
   Else
      Q = 0
   End If
   If Q > 0 Then
      NumSubt(AA, L, DD, L, AA)   ' A = A - Q*B
   End If
   NumMulID(AA, 10)                    'A を1桁シフトアップ
Next