問題タブ [biginteger]

大きな数とは何か、そしてそれらを処理するために使用される一般的なアルゴリズムは何かと考えていました。Coders at Work でこの用語が言及されているのを聞いた.インタビューで、大きな数を扱うライブラリを作成するように求められた.

BigInteger、BigDecimalなどを使用せずに、大きな数に関するプロジェクトを作成しています。すべての基本を実行できましたが、階乗をカウントする機能を追加する必要があります。私のBigNumberはデータをint[]として保存します。

これはBigIntegerを使用したサンプルソリューションですが、実際の数値がないと使用できません。

では、値を数える方法は？最後から最初にintを追加し、10を10倍し、100を100倍にするなどして、それを長く保存しますか？

BigIntegerのソース：http： //developer.classpath.org/doc/java/math/BigInteger-source.html

BigInteger の valueOf には制限がありますか? よくわかりませんが、どこかで読んだところ、指定された数値は length = long のみである可能性があります。

メソッドはどのくらい複雑ですかmultiply、divideそして現在powはBigInteger？ドキュメント（または他のどこにも）には計算の複雑さについての言及はありません。

APIドキュメントによると

BigInteger は操作の結果を収容するために必要な大きさになるため、オーバーフローに関する Spec の詳細はすべて無視されます。

これは、十分なメモリが利用可能であると仮定して、BigInteger がオーバーフローしないことを意味しますか? もしそうなら、なぜ一部の「型」をオーバーフローさせ、一部をオーバーフローさせないのでしょうか?

言語が進化するにつれて、オーバーフローするメカニズムをプログラマーから隠す型が好まれるでしょうか?

そのため、操作は2次式であるように見えるため、 .net4のBigIntegerクラスが提供する操作の一部を改善しようとしています。大まかなカラツバの実装を行いましたが、それでも予想よりも遅いです。

主な問題は、BigIntegerがビット数をカウントする簡単な方法を提供していないことであると思われるため、BigInteger.Log（...、2）を使用する必要があります。Visual Studioによると、時間の約80〜90％が対数の計算に費やされています。

それで、私はそれをスピードアップするために何ができますか？

オプションの割り当てとして、BigInteger クラスの独自の実装を作成することを考えています。ここでは、加算、減算、乗算などの独自のメソッドを提供します。

これは、数百桁の長さであっても、任意の長さの整数用です。

これらの数値の計算を行っている間、1 桁ずつ計算するのは難しくありません。私の「BigInteger」を表すのに最適なデータ構造は何だと思いますか?

最初は配列の使用を検討していましたが、大規模な加算または乗算の後、まだオーバーフロー (配列スロットが不足) する可能性があると考えていました。O（1）時間の複雑さで数字を追加できるので、これはリンクされたリストを使用する良いケースでしょうか?

リンクされたリストよりも適している他のデータ構造はありますか? 私のデータ構造が保持する型は、私が利用できる最小の整数型であるべきですか?

また、「キャリー」変数の保存方法に注意する必要がありますか? それ自体は、私の「BigInteger」タイプである必要がありますか?

私は、非常に多くの桁数を持つ膨大な数の算術を含むアプリを書いています。以前、大きな数値を文字列として定義し、低速の算術文字列関数を使用することで、大きな数値の処理を簡素化するクラスを作成しました。これが最善の方法ですか？そうでない場合、この問題にどのようにアプローチすればよいですか? C# には、そのような状況に対応する組み込み機能はありますか?

64ビットのunsignedintである値があり、それらをunsignedint型を持たないmongodbに格納する必要があります。それらを他のフィールドタイプに保存し、出入りを変換するための3つの主な可能性があります。

署名されたintを使用するのがおそらく最も簡単で、スペース効率が最も高いですが、人間が読めないという欠点があり、誰かが変換を忘れると、一部が機能し、エラーがわかりにくくなる可能性があります。

生のバイナリは、経験の浅いプログラマーにとっておそらく最も扱いにくく、人間が読めないという問題もあります。

文字列表現はスペース効率が最も低くなります（ユニコードで最大40バイト、フィールドあたり8バイト）が、少なくともすべての可能な値が適切にマップされ、クエリでは、より複雑な変換ではなく、文字列への変換のみが必要になります。

これらの値をさまざまなプラットフォームから利用できるようにする必要があるため、単一のドライバー固有のソリューションを選択することはできません。

私が見逃した主な長所と短所はありますか？どちらを使いますか？

0 (含む) から n (含まない) の範囲で任意に大きなランダムな整数を生成する必要があります。最初は n を掛けて n を掛けようと考えていましたが、n が 2 ⁵³nextDoubleよりも大きくなると、結果は一様に分布しなくなります。

BigInteger次のコンストラクタが利用可能です。

^{0 から (2 numBits} - 1)までの範囲に均一に分散された、ランダムに生成された BigInteger を構築します。

n が 2 の累乗でない場合、これを使用して 0 から n の範囲のランダムな値を取得するにはどうすればよいでしょうか?