7

整数の配列を使用して JavaScript で BigInt 型を実装しようとしています。今のところ、それぞれに 256 の上限があります。すべての整数演算の実装を終了しましたが、BigInt をその文字列表現に変換する方法がわかりません。もちろん、簡単な方法は次のとおりです。

BigInt.prototype.toString = function(base) {
    var s = '', total = 0, i, conv = [
        ,,
        '01',
        '012',
        '0123',
        '01234',
        '012345',
        '0123456',
        '01234567',
        '012345678',
        '0123456789',
        ,
        ,
        ,
        ,
        ,
        '0123456789abcdef'
    ];
    base = base || 10;

    for(i = this.bytes.length - 1; i >= 0; i--) {
        total += this.bytes[i] * Math.pow(BigInt.ByteMax, this.bytes.length - 1 - i);
    }

    while(total) {
        s = conv[base].charAt(total % base) + s;
        total = Math.floor(total / base);
    }

    return s || '0';
};

しかし、BigInts が実際に大きくなると、追加して変換できなくなります。base-x の配列を base-y の配列に変換するにはどうすればよいですか?

4

2 に答える 2

1

最近の同様の質問に対するこの回答で私が示した例を参照してください (これは base-10 から base-3 に対するものですが、原則は転送可能でなければなりません): C Fast base convert from decimal to ternary .

要約すれば：

低い値から高い値まで、入力数字を反復処理します。各桁位置について、最初に 1000....000 (基数 256) が出力表現になるかを計算します (前の 256 の累乗の 256 倍です)。次に、その結​​果に数字を掛けて、出力表現に累積します。

出力表現で乗算と加算を実行するルーチンが必要になります。乗算ルーチンは、加算ルーチンの観点から記述できます。

このアプローチが何らかの形で高速であるとは主張していないことに注意してください（桁数はO（n ^ 2）だと思います）。これよりもアルゴリズム的に高速なアプローチがあると確信しています。

于 2011-05-03T23:25:42.600 に答える
0

あなたが今の私よりも数学的な思考力を身につける準備ができているなら、誰かがパスカルの三角形を使って数字表現を変換する方法を説明したようです:

http://home.ccil.org/~remlaps/DispConWeb/index.html

下部にソース コードへのリンクがあります。それらは JavaScript ではなく Java で書かれていますが、数学を理解する努力をしているのであれば、おそらく独自の実装を考え出すか、コードを移植する努力をすることができます...

于 2011-05-03T23:33:18.200 に答える