12

100〜1000桁のような非常に大きな数を除算する（整数除算、浮動小数点は重要ではありません）ためのアルゴリズム（これは割り当てであるため、サードパーティのライブラリを使用できません）を作成する必要があります。http://en.wikipedia.org/wiki/Fourier_divisionアルゴリズムを見つけましたが、それが正しい方法かどうかわかりません。何か提案はありますか？

1) check divisior < dividend, otherwise it's zero (because it will be an int division)
2) start from the left
3) get equal portion of digits from the dividend
4) if it's divisor portion is still bigger, increment digits of dividend portion by 1
5) multiply divisor by 1-9 through the loop
6) when it exceeds the dividend portion, previous multiplier is the answer
7) repeat steps 3 to 5 until reaching to the end
4

5 に答える 5

11

小学校のように「長い」道を分けることは、潜在的なルートになると思います。元の数値を文字列として受け取っていると想定しているので、各桁を解析します。例：

ステップ0：

   /-----------------
13 | 453453453435....

ステップ1：「13は4に何回入りますか？0

     0
   /-----------------
13 | 453453453435....

ステップ2：「13は45に何回入りますか？3

     03
   /-----------------
13 | 453453453435....
   - 39
     --
      6

ステップ3：「13は63に何回入りますか？4

などなど。この戦略では、任意の数の長さを持つことができ、int（除数）とdouble（被除数）のためにメモリに十分な桁を保持するだけで済みます。（私がそれらの用語を正しく理解したと仮定します）。結果は、結果文字列の最後の桁として保存します。

数字が残っておらず、計算が1回以上実行されないポイントに到達すると、結果が返されます。これは、すでに文字列としてフォーマットされています（intよりも大きくなる可能性があるため）。

于 2010-05-21T17:37:07.957 に答える
11

大きな数に対して実装する最も簡単な除算アルゴリズムは、シフトと減算です。

if numerator is less than denominator then finish
shift denominator as far left as possible while it is still smaller than numerator
set bit in quotient for amount shifted
subtract shifted denominator from numerator
repeat
the numerator is now the remainder

シフトは文字通りである必要はありません。たとえば、減算する前に値全体を実際に左にシフトするのではなく、左にシフトした値を別の値から減算するアルゴリズムを作成できます。比較も同様です。

長分割のステップの 1 つが長分割であるため、長分割は実装が困難です。除数が int の場合、長い除算をかなり簡単に行うことができます。

于 2010-05-21T18:42:13.977 に答える
9

Knuth、Donald、The Art of Computer Programming、ISBN 0-201-89684-2、Volume 2：Seminumerical Algorithms、Section 4.3.1：The Classical Algorithms

于 2010-05-21T17:38:08.910 に答える
3

おそらく、長い割り算のようなものを試してみるべきですが、数字の代わりにコンピューターの単語を使用してください。

高水準言語では、「数字」を最大の固定精度整数の半分のサイズと見なすのが最も便利です。長い除算方法では、固定精度の除算では任意精度の除数の最上位部分しか処理できないため、部分的な中間結果が 1 ずれている可能性がある場合を処理する必要があります。

任意精度の演算を行うには、より高速で複雑な方法があります。適切なウィキペディアのページをチェックしてください。特に、ニュートン ラフソン法は、慎重に実装すると、除算の時間性能が任意精度の乗算の一定の係数内に収まるようにすることができます。

于 2010-05-21T17:49:01.720 に答える
1

あなたの課題の一部が完全にオリジナルでない限り、私は (そしておそらくあなたも) 手で大規模な除算を行うために小学校で教えられたアルゴリズムを使用します。

于 2010-05-21T17:34:44.817 に答える