私は大きな整数でCライブラリを構築しています。基本的に、私はその中の任意の整数をバイナリ表現から10進数に変換するための高速アルゴリズムを探しています
JDKのBiginteger.toString()
実装を見ましたが、数値を任意の基数に変換するために作成されたため、かなり重く見えます(各桁に除算を使用するため、数千桁を処理する場合はかなり遅くなります)。
それで、あなたがそれについて共有するためのドキュメンテーション/知識を持っているならば、私はそれを読んでうれしいです。
編集:私の質問についてより正確に:
Pをメモリアドレスとします
NをPで割り当てられた(そして設定された)バイト数とします。
アドレスPのNバイトで表される整数(簡単にするためにリトルエンディアンとしましょう)をC文字列に変換する方法
例:
N = 1
P =「00101010」を格納するランダムメモリアドレス
out string = "42"
まだあなたの答えをありがとう
BigInteger.toStringメソッドが重く見える理由は、チャンクで変換を行うためです。
簡単なアルゴリズムでは、最後の桁を取得し、残りがなくなるまで大きな整数全体を基数で除算します。
これに関する1つの問題は、大きな整数の除算は非常に高価であるため、数値は通常の整数の除算(BigIntの除算ではなく)で処理できるチャンクに分割されることです。
static String toDecimal(BigInteger bigInt) {
BigInteger chunker = new BigInteger(1000000000);
StringBuilder sb = new StringBuilder();
do {
int current = bigInt.mod(chunker).getInt(0);
bigInt = bigInt.div(chunker);
for (int i = 0; i < 9; i ++) {
sb.append((char) ('0' + remainder % 10));
current /= 10;
if (currnet == 0 && bigInt.signum() == 0) {
break;
}
}
} while (bigInt.signum() != 0);
return sb.reverse().toString();
}
とは言うものの、固定基数の場合、コメントで示唆されているように、「ダブルダブル」アルゴリズムをニーズに移植する方がおそらくさらに良いでしょう:https: //en.wikipedia.org/wiki/Double_dabble
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加