多倍長演算の除算

解決

QA 2009-05-01 21:13:25 No: 34235

http://oku.edu.mie-u.ac.jp/~okumura/algo/algo_pas.html
（「コンピュータ・アルゴリズム事典」のソース CHAP04.pas）
で公開されている多倍長演算の除算で、小数点以下を求めようとして以下のようにコーディングしたのですが、除数と被除数の差が小さいとき小数点以下が正しく計算できません。
  たとえば
(a)9999999999999999999999999999999999  被除数
    899999999999999999999999999999999  除数（先頭が8）
(b)99999  被除数
    9999  除数
などはだいじょうぶですが
(c)9999999999999999999999999999999999  被除数
    999999999999999999999999999999999  除数（先頭が９）
(d)99999  被除数
   98999  除数
などはダメです。
  ちなみに最小桁しか用いない場合
(e)9999  被除数
   9998  除数
のように差が1でもＯＫです。

  いろいろ試行錯誤しながらコードを弄っているのですが、なかなかうまくいきません。解決策をご教示いただけたら幸いです。
-------------------------------------------------------------------------
【CHAP04.pasを変更した部分】
const
   BASE      = 10000;     // 10000 進法
   BASE_ONE  = BASE-1;    // BASE-1 = 9999
   BASE2     = BASE*BASE; // BASE*BASE = 100,000,000（１億）
   MAXLEN    = 100000;    // BASE 進法での最大桁数

type
Digit = 0..BASE_ONE; // 各桁の数(0 から 9999)

  TSuperLong = record
     Len: 0..MAXLEN;
     Num:array [0..MAXLEN] of Digit;
  end;

  例外処理で writeln を使用していたところは raise Exception.Create に替えました。
-------------------------------------------------------------------------
//数値文字列を多倍長整数に変換
function StrToSuperLong(const S: string; n: Integer): TSuperLong;
var
  X      :TSuperLong;
  dmy    :string;
  L, i, k:Integer;
begin
  L := Length(S);  i := 1;
  repeat
    k := L-i*n+1;
    if k < 1 then dmy := Copy(S,1,n-1+k)
    else          dmy := Copy(S,k,n);
    X.Len := i;
    X.Num[X.Len] := StrToInt(dmy);
    Inc(i);
  until k <= 1;
  Result := X;
end;
//多倍長整数を数値文字列に変換
function TForm1.SuperLongToStr(X: TSuperLong): string;
var
  i :Integer;
begin
  Result := IntToStr(X.Num[X.Len]);
  for i := X.Len-1 downto 1 do
    Result := Result+Format('%.4d',[ X.Num[i] ]);
  if X.Len = 0 then Result := '0';
end;
//小数点以下を求める
procedure   TForm1.Button1Click(Sender: TObject);
var
  W, Bunshi, Bunbo, R, R2: TSuperLong;
  i: Integer;
begin
  if (Edit1.Text = '') or (Edit2.Text = '') then Exit;
  W.Num[0] := 0;    R.Num[0] := 0;     R2.Num[0] := 0;

  Bunshi := StrToSuperLong(Edit1.Text,4);//数値文字列を多倍長整数に
  Bunbo  := StrToSuperLong(Edit2.Text,4);
  if (Bunbo.Num[1] = 0) and (Bunbo.Len = 1) then
  begin
    MessageDlg('0 では割れません。', mtInformation, [mbOK], 0);
    Exit;
  end;
  LongDiv(W, Bunshi, Bunbo, R);     //W:商 R:余
  if R.Num[1] = 0 then
    Edit3.Text := SuperLongToStr(W) //多倍長整数を数値文字列に
  else
  begin
    Edit3.Text := SuperLongToStr(W)+'.';
    ShortMul(R2,R,10);  //余を10倍
    for i := 1 to 30 do //小数点以下30桁
    begin
      LongDiv(W, R2, Bunbo,R);
      Edit3.Text := Edit3.Text+SuperLongToStr(W);
      if R.Num[1] = 0 then break;
      ShortMul(R2,R,10);
    end;
  end;
end;

KHE00221 2009-05-02 04:42:12 No: 34236

99999/99998 をやると 1.0000 となるが、
このとき R.Num[1] = 0 R.Num[2] = 1 になっている
なので
R.Num 全て 0 の時に Break するとようにすれば良いと思うけど？

QA 2009-05-02 06:45:19 No: 34237

> 99999/99998 をやると 1.0000 となるが、
> このとき R.Num[1] = 0 R.Num[2] = 1 になっている
ここまではデバッガで確認していました。しかし
> R.Num 全て 0 の時に Break するとようにすれば良いと思うけど？
と思いつかないおバカな私でした。
いつも貴重なアドバイスありがとうございます。

QAあれ？ 2009-05-02 18:25:08 No: 34238

(a)差が1
9999999999999999999999999999999999  被除数
9999999999999999999999999999999998  除数
(b)
9999999999999999999999999999999999  被除数
9899999999999999999999999999999998  除数（先頭から2番目が8）
9800099999999999999999999999999999  除数
9800099990000999999999999999999999  除数
-------------------------------------------------------------------------
(a)がＯＫなので問題ないと思っていたのですが、(b)の例では多倍長同士の除算（LongDiv）を実行した時点ですべての R.Num がゼロになり、結果は 1 になります。LongDiv のバグでしょうかねえ？
http://f31.aaa.livedoor.jp/~oilerex/pzip/