巨大な数値の効率的な指数化（私はGoogolsと話している）

Question

私は解が2 ^（n-1）である単純な結合問題を解く途中です。

唯一の問題は、1 < = N <ある= 2^31 -1（符号付き32ビット整数の最大値）

私はJavaのBigIntegerのクラスを使用して試みたが、タイムアウト番号2^10分の31用^ 4以上では、明らかにうまくいかない。

また、JavaまたはC++の組み込みクラスのみに限定されています。

私はスピードが必要であることを知っているので、私は文字列の算術演算を行うC++でクラスを作成することを選択しました。

私は乗算を行うと、私のプログラムは、紙の上に乗って効率を上げる方法（繰り返し文字列を追加するのではなく）と同様に乗算します。

しかし、それがあっても、2を31倍にすることはできません。それだけでは十分ではありません。

だから、これは私は、べき乗を解決することができることを意味し

（/整数の除算を表し、％はモジュラスを表す）私はこの問題にテキストを読み始めて、私は

2^n = 2^(n/2) * 2^(n/2) * 2^(n%2) ...の溶液に来ました乗数の対数。しかし、私には、このメソッドを自分のコードにどのように適用すればいいのでしょうか？どのようにして下限を選ぶのですか、最終的な乗算に必要なさまざまな数値を追跡する最も効率的な方法は何ですか？

誰かがこの問題の解決方法について知識を持っている場合は、詳細を教えてください（サンプルコードは高く評価されます）。すべてのあなたの助けをみんなに

UPDATE

ありがとう！明らかにこの問題は現実的な方法で解決されることを意図していますが、ceil（log2（n））回だけを実行するパワー関数を使ってjava.math.BigIntegerを上回る性能を達成しました。

誰もが私が作成したコードに興味がある場合は、ここではそれはあなたがまったくの乗算を行う必要はありません...

using namespace std; 

bool m_greater_or_equal (string & a, string & b){ //is a greater than or equal to b? 
    if (a.length()!=b.length()){ 
     return a.length()>b.length(); 
    } 
    for (int i = 0;i<a.length();i++){ 
     if (a[i]!=b[i]){ 
      return a[i]>b[i]; 
     } 
    } 
    return true; 
} 

string add (string& a, string& b){ 
    if (!m_greater_or_equal(a,b)) return add(b,a); 
    string x = string(a.rbegin(),a.rend()); 
    string y = string(b.rbegin(),b.rend()); 
    string result = ""; 
for (int i = 0;i<x.length()-y.length()+1;i++){ 
    y.push_back('0'); 
} 

int carry = 0; 
for (int i =0;i<x.length();i++){ 
    char c = x[i]+y[i]+carry-'0'-'0'; 
    carry = c/10; 
    c%=10; 
    result.push_back(c+'0'); 
} 
if (carry==1) result.push_back('1'); 
return string(result.rbegin(),result.rend()); 

} 

string multiply (string&a, string&b){ 
    string row = b, tmp; 
    string result = "0"; 

    for (int i = a.length()-1;i>=0;i--){ 

     for (int j= 0;j<(a[i]-'0');j++){ 
      tmp = add(result,row); 
      result = tmp; 
     } 
     row.push_back('0'); 
    } 
    return result; 
} 

int counter = 0; 

string m_pow (string&a, int exp){ 
    counter++; 
    if(exp==1){ 
     return a; 
    } 
    if (exp==0){ 
     return "1"; 
    } 
    string p = m_pow(a,exp/2); 
    string res; 
    if (exp%2==0){ 
     res = "1"; //a^exp%2 is a^0 = 1 
    } else { 
     res = a; //a^exp%2 is a^1 = a 
    } 
    string x = multiply(p,p); 
    return multiply(x,res); 
    //return multiply(multiply(p,p),res); Doesn't work because multiply(p,p) is not const 

} 

int main(){ 


    string x ="2"; 

    cout<<m_pow(x,5000)<<endl<<endl; 
    cout<<counter<<endl; 

    return 0; 
} 

Answer 1

このメソッドをコードに適用する最も簡単な方法は、再帰的に適用することです。それだけでなく、2のために、任意の数のaのために働くので、私はそれをより面白くするために、パラメータとしてaを取るコード書いた：@オリの答えで述べたように

MyBigInt pow(MyBigInt a, int p) { 
    if (!p) return MyBigInt.One; 
    MyBigInt halfPower = pow(a, p/2); 
    MyBigInt res = (p%2 == 0) ? MyBigInt.One : a; 
    return res * halfPower * halfPower; 
} 

Answer 2

です。 2 ^（n-1）はちょうど1 << (n-1)であり、1には(n-1)のゼロ（2進数）が続く。

Answer 3

を、これは、コンピューティング2^nの問題ではありませんこれはちょうど1であり、続いて0sがバイナリである。

しかし、10進数で印刷したいので、非常に大きな数値の場合は2進数から10進数に変換する方法の問題になります。

私の答えは現実的ではないということです。（私はこの質問はただ好奇心から茎を願っています。）

あなたは2^(2^31 - 1)を計算しようとすると、小数点のそれをプリントアウト言及。その番号はです。646,456,993桁の長さです。です。

• Java BigIntegerはできません。これは数が少ない場合に意味され、アルゴリズムはO(n^2)です。
• コメントに記載されているとおり、C++にはBigNumライブラリが組み込まれていません。
• でもMathematicaには、それを処理することはできません。General::ovfl : Overflow occurred in computation.
• あなたの最善の策はGMPライブラリを使用することです。

---

あなたは答えの一部を見ることにだけ興味があるなら：

2^(2^31 - 1) = 2^2147483647 = 

880806525841981676603746574895920 ... 7925005662562914027527972323328 

(total: 646,456,993 digits) 

これは近いソースのライブラリを使用して行われ、およそ37秒とメモリの3.2ギガバイトを取りました。大規模なテキストファイルに6億4600万桁すべてを書き込むのに必要な時間を含めて、Core i7 2600K @ 4.4 GHzで。
（それはそれを計算するのに必要以上のファイルを開くために、メモ帳より長くかかりました。）

---

を今、実際に一般的なケースでは、そのような力を計算する方法のあなたの質問に答えるために、@dasblinkenlightはその答えを持っていますこれはExponentiation by Squaringの亜種です。

大量の場合、バイナリから小数への変換は非常に難しい作業です。ここの標準アルゴリズムはDivide-and-Conquer conversionです。

私は、後者を実装しようとはお勧めしません。これは、プログラマを開始する範囲をはるかに超えているためです。 （また多少の数学的集約もあります）