C++ で文字列を使用して大きな数を除算するプログラムを作成しました。つまり、数値の各桁を格納するために使用される文字列です。剰余と商を得るために連続減算を使用しました。
For ex:
16/5
Subtract 16-5=11
11-5=6
6-5=1
1 is less than 5 so stop
quotient = 3 and remainder = 1
しかし問題は、この方法は非常に大きな数に対して非常に遅いことです。それを速くするために他にどのような方法がありますか？
4715 次
4 に答える
3
bignum の計算を高速化する 1 つの方法は、基数に高い値を使用することです。
例として、合計を考えてみましょう
12301922342343 +
39234932348823
--------------
51536854691166
この計算を手で行う場合、右端の数字から開始し、結果が 9 を超えた場合の「キャリー」を念頭に置いてそれらを合計します。右から左へ 3+3=6、4+2=6、3+8=1+キャリー 1、2+8+1=1+キャリー 1 など。
ただし、できることは、複数の桁のチャンクで計算を行うことです...たとえば
012 301 922 342 343 +
039 234 932 348 823
-------------------
051 536 854 691 166
これは以前と同じ計算ですが、基数 9 (数字は 000 から 999 まで) の代わりに基数 1000 を使用しており、同じアプローチを使用できます。右端の桁は 343+823=166 キャリー 001、342 + 384 + 001 = 691、922 + 932 = 854 キャリー 001 などです。
乗算 (除算アルゴリズムにも必要) を簡単に実行できるようにするには、32 ビット整数の基数として 9999 を選択するのが妥当です。
基数を 10**n の形式で使用すると、一度に 1 桁ずつ 10 進数で結果を簡単に出力できます。
于 2011-10-29T05:58:07.620 に答える
1
私は過去に有効数字をプログラムしようとしましたが、私の解決策は、分子の最上位桁を分母の最上位桁で除算し、スケールの違いを調整することでした。これは、回答の最初の桁です。これに分母を掛け、分子から引きます。次に、これを新しい分子として繰り返します。これは小学校の筆算のようなものです
10000 / 3
=10/3 * 1000 + ?
=3*1000 + ?
=3000 + (10000-3000*3)/3
=3000 + (1000 / 3) //repeat recursively from beginning
于 2011-10-29T05:37:26.730 に答える
0
bignum 乗算には非常に高速な ( O(n log n) 時間 ) アルゴリズムがいくつかあるため、バイナリ検索でそれを使用して O( n * ( log n )^2 ) の全体時間を取得できます。
于 2011-10-29T10:20:06.463 に答える
-1
n* 倍の数を引きます。しかし、あなたが言うように、それは遅いです。
しかし、これを考慮してください：
Dividend Divisor
123456789 987
9 digits vs 3 digits
9 digits - 3 digits = 6 , subtract 1 so the factor is 5: 10^5 = 100.000
それで：
9 digits 3+5 digits = 100.000 times
123.456.789 - 987*100.000 = 24.756.789
----------------------------------------------
8 digits 3+4 digits = 10.000 times (now 110.000 times)
24.756.789 - 9.870.000 = 14.886.789
-----------------------------------------------
8 digits 3+4 digits = 10.000 times (120.000 times)
14.886.789 - 9.870.000 = 5.016.789
-----------------------------------------------
7 digits 3+3 digits = 1000 times (121.000 times)
5.016.789 - 987.000 = 4.029.789
-------------------------------------------------
等々...
それが役に立てば幸い！
于 2014-10-06T20:37:34.413 に答える