c - 大きな数を分割する方法は？

Question

2つの変数に大きな数（整数、符号なし）が格納されています（ご覧のとおり、数の高い部分と低い部分）：

unsigned long long int high;
unsigned long long int low;

他の種類の変数を加算または減算する方法を知っています。

しかし、私はそれを分割する必要があります-種類の数。どうやってするの？私は知っています、私はN回引くことができます、しかし、多分、もっと良い解決策があります。;-)

言語：C

score 6 · Accepted Answer

はい。これにはシフトが含まれるため、Cで行うことはお勧めしません。これは、アセンブラーがその価値を証明でき、物事を数百倍速く簡単に実行できるまれな例の1つです（誇張しているとは思いません）これ。）

私は完全な正しさを主張しませんが、以下はあなたを動かすはずです：

（1）結果をゼロに初期化します。

（2）除数を被除数より大きくならないように、できるだけ左にシフトします。

（3）シフトされた除数を被除数から減算し、結果に1を加算します。

（4）除数をもう一度右にシフトすると、残りの被除数より少なくなり、右シフトごとに、左シフトの結果が1ビットずつ少なくなります。停止条件を満たさない限り、（3）に戻ります。（停止条件は「除数がゼロになった」のようなものである必要がありますが、それについてはよくわかりません。）

いくつかの実際のプログラミングの問題に戻るのは本当に素晴らしい気分です:-)

score 2 · Accepted Answer

2

GNU MP BigNumなどの多数のライブラリを見たことがありますか？

于 2009-06-19T17:28:04.153 に答える

score 2 · Accepted Answer

私は知っています、私はN回引くことができます、しかし、多分、もっと良い解決策があります。

Nが大きい場合、N回の減算は遅くなる可能性があります。

小学校で小数の筆算を行うために学んだアルゴリズムを使用して、より良い（つまり、より複雑ですがより高速な）シフトアンドサブトラクションがあります。

[このような番号については、サードパーティのライブラリやコンパイラ固有のサポートがある場合もあります。]

score 0 · Accepted Answer

0

これは、128ビット演算を実行する別のライブラリです。 GnuCash：Math128。

于 2009-06-19T17:38:50.240 に答える

score 0 · Accepted Answer

うーん。「高」に余裕がある場合は、すべてを1桁上にシフトし、高を数値で除算してから、余りを残りの一番上の桁に低で加算し、低を数値で除算してから、すべてを元に戻すことができると思います。

score 0 · Accepted Answer

以下の私のコメントによると、私の以前の答えは愚かでした。

すぐに、私の新しい答えは、過去にこれを試みたとき、ほとんどの場合、シフトが含まれるということです。これは、複数の「単語」に適用できる唯一の操作であり、見た目が良いからです。 1つの大きなワードであるかのように（キャリーオーバービットを追跡する必要があることを除いて）。

これにはいくつかの異なるアプローチがありますが、ハードウェアに特別な操作がない限り、シフトを使用するよりも一般的な方向性はわかりません。

score 0 · Accepted Answer

文字列配列で除算を行う「BigInt」タイプのアルゴリズムを実装できます。高低のペアごとに1つの文字列配列を作成し、除算を行います。結果を別の文字列配列に格納してから、高整数と低整数のペアに変換し直します。

言語はCであるため、配列はおそらく文字配列になります。上で述べた「文字列配列」に類似していると考えてください。

score 0 · Accepted Answer

アセンブラループと「キャリー付き加算/減算（adc / sbb）」命令を使用して、任意の大きさのバイナリオブジェクトの加算と減算を行うことができます。それらを使用して他の操作を実装できます。私はこれらの2つを超えて個人的に何かをすることを調査したことはありません。

score 0 · Accepted Answer

プロセッサ（またはCライブラリ）に高速の64ビット除算がある場合は、128ビット除算を分割できます（16ビット除算のプロセッサで32ビット除算を行うのと同じ方法です）。

ちなみに、被除数と除数の一般的な値がわかっている場合は、さまざまなトリックを使用できます。これらの数字の出所は何ですか？多くのケースを迅速に解決できれば、場合によっては時間がかかることもあります。

また、おおよその答えがOKである場合を見つけることができれば、それは多くの迅速な近似への扉を開きます。

9 に答える 9