3

1 つの基数/基数でエンコードされたn桁の大きな整数を取り、それを別の任意の基数に変換する既知のアルゴリズムはありますか? (基数 7 から基数 19 までとしましょう。) nは 100 000 桁を超えるなど、非常に大きくなる可能性があるため、O( n 2 ) 実行時間よりも優れたものを探しています。

高速フーリエ変換 (FFT) を使用して 2 つの巨大な整数を乗算できるアルゴリズムをいくつか見てきました。理論上の複雑さは O( n log n ) で、nは桁数です。基数変換？

4

1 に答える 1

2

私自身はこのトピックに精通していませんが、単純な剰余と除算のアルゴリズムよりも少し速く基数変換を行う方法を示唆するページを次に示します。

このページは、高速な分割統治除算アルゴリズムが必要であることを示唆しており、これには高速な乗算アルゴリズム (からつば、Toom-Cook、FFT など) が必要です。

于 2011-08-02T17:24:21.223 に答える