3

私はBigIntを実装しようとしていて、それに関するいくつかのスレッドと記事を読みました。それらのほとんどは、より高いベース（256または2 32、さらには2 64）を使用することを提案しました。

なぜより高い塩基がこの目的に適しているのですか？

私が持っている他の質問は、文字列をより高い基数（> 16）に変換する方法です。base64以外に標準的な方法はないことを読みました。そして最後の質問は、これらのより高い塩基をどのように使用するかです。いくつかの例は素晴らしいでしょう。

4

2 に答える 2

9

レジスタに収まる数を乗算または加算するために費やされるCPUサイクルは、同じになる傾向があります。したがって、レジスタ全体を使い切ることで、反復回数を最小限に抑え、最高のパフォーマンスを得ることができます。つまり、32ビットアーキテクチャではベースユニットを32ビットにし、64ビットアーキテクチャでは64ビットにします。それ以外の場合、たとえば、32ビットレジスタの8ビットだけを埋めると、サイクルが無駄になります。

于 2012-04-16T16:36:27.673 に答える
2

  1. 最初の答えはこれが最も良いと述べました。私は個人的にベース2^16を使用して、乗算でオーバーフローしないようにしています。これにより、オーバーフローすることなく、任意の2桁を1回乗算できます。

  2. より高い塩基に変換するには、高速除算方法と、可能な限り数値をパックする必要があります（ur BigInt libが複数の塩基を処理できると仮定）。

10進数->2進数を考えてみましょう。実際の変換は10->10000->32768-> 2になります。これは遅いように見えるかもしれませんが、10進数から10000への変換は非常に高速です。10000から32768の間で変換するための反復の量は、反復する桁が非常に少ないため、非常に高速です。32768から2への解凍も非常に高速です。

したがって、最初にベースを移動可能な最大のベースにパックします。これを行うには、数字を組み合わせるだけです。オーバーフローを防ぐために、このベースは<= 2^16である必要があります。

次に、ターゲットベース以上になるまで数字を組み合わせます。ここから、他のシナリオでは通常オーバーフローする高速除算アルゴリズムを使用して、ターゲットベースで除算します。

いくつかの簡単なコード

if (!packed) pack()

from = remake() //moves all of the digits on the current BigInt to a new one, O(1)
loop
    addNode()

    loop
        remainder = 0
        remainder = remainder*fromBase + from.digit
        enter code here`exitwhen remainder >= toBase
        set from = from.prev
        exitwhen from.head

    if (from.head) node.digit = remainder
    else node.digit = from.fastdiv(fromBase, toBase, remainder)

    exitwhen from.head

速い除算を見てください

loop
    digit = remainder/divide
    remainder = remainder%divide

    //gather digits to divide again
    loop
        this = prev
        if (head) return remainder

        remainder = remainder*base + digit
        exitwhen remainder >= divide

        digit = 0

return remainder

最後に、開梱する必要がある場合は開梱します

パッキングとは、数字を組み合わせただけです。

基数10から基数10000の例

4th*10 + 3rd
*10 + 2nd
*10 + 1st
  1. ???

toStringのアルファベットとサイズを格納するBaseクラスが必要です。Baseが無効な場合は、数字をコンマ区切りのリストに表示するだけです。

すべてのメソッドは、定数ではなく、BigIntの現在のベースを使用する必要があります。

それで全部です？

そこから、あなたは次のようなことをすることができるでしょう

BigInt i = BigInt.convertString("1234567", Base["0123456789"])

[]がオーバーロードされ、新しいベースを作成するか、すでに作成されたベースを返す場合。

また、次のようなことができるようになります

i.toString()
i.base = Base["0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"]
i.base = 256
i.base = 45000

など^_^。

また、整数を使用していて、BigIntの余りを返すことができるようにしたい場合、除算は少しトリッキーな= Pになる可能性がありますが、それでもかなり簡単です^_^。

これは私がvjassでコーディングしたBigIntライブラリです（はい、Warcraft 3の場合、笑、私を判断しないでください）

スレッドがクラッシュしないようTriggerEvaluate(evalBase)にするだけです（悪意のある操作制限）。

頑張ってください：D

于 2012-04-16T19:32:17.620 に答える