6

10 進法で約 10k 桁の数字があります。基数2（1010101001 ...）に変換したい。私が考えることができるのは、原始的なアルゴリズムだけです:

take last digit mod 2 -> write down bit

number divide by 2;

文字列に小学校の区分を実装するのは難しくないはずですが、非常に非効率的だと思います。私が正しければO(l^2)、それは になります。ここでl、基数 10 の数値の長さを意味します。それをより速く行うことはできますか?

4

3 に答える 3

1

大きな数で作業している場合は、多精度ライブラリを使用することをお勧めします。GMPまたはMPRFなどを試してください。
-Øystein

于 2012-11-19T14:39:05.457 に答える
1

2 で割り算することは、1/2 を掛けることと同じです。後者の場合、よく知られている高速乗算アルゴリズム (Toom–Cook、Schönhage–Strassen など) を使用できます。

于 2012-11-19T14:50:23.763 に答える
1

私が理解していることから、あなたの大きな数字は一連の10進数として表されています。その場合、乗算と加算を使用して「バイナリ」表現を計算できます。

value = sum(i in 0...n-1) 10 i * digit i

この計算は、分割統治法で部分に分割できますが、O(n log n) アルゴリズムに到達できるかどうかはわかりません。

于 2012-11-19T14:12:25.323 に答える