多数の数式表現ですか？

Question

大きな数字を入力（800桁以上）する関数を記述しようとしていますが、複雑な数学のない単純な式を文字列として返します。

は、単純な数学では、私はちょうど数字とを意味+、 - 、*、/、^と（）必要に応じて。

'4^25+2^32' = giveMeMath(1125904201809920); // example

任意の言語を行うだろう。私はそれをリファクタリングすることができます。ちょうどロジックの助けを求めています。

ボーナス。出力が短いほど良い。処理時間は重要です。また、数学的精度は必須です。

更新： 明確にする、すべての入力値が正の整数（小数なし）Javaで

Answer 1

はPythonで私の試みです：

def give_me_math(n): 

    if n % 2 == 1: 
     n = n - 1 # we need to make every odd number even, and add back one later 
     odd = 1 
    else: 
     odd = 0 
    exps = [] 

    while n > 0: 
     c = 0 
     num = 0 
     while num <= n/2: 
      c += 1 
      num = 2**c 

     exps.append(c)  
     n = n - num 
    return (exps, odd) 

結果：

>>> give_me_math(100) 
([6, 5, 2], 0) #2**6 + 2**5 + 2**2 + 0 = 100 

>>> give_me_math(99) 
([6, 5, 1], 1) #2**6 + 2**5 + 2**1 + 1 = 99 

>>> give_me_math(103) 
([6, 5, 2, 1], 1) #2**6 + 2**5 + 2**2 + 2**1 + 1 = 103 

私は結果が正確だと思いますが、他の基準についてはわかりません。

編集：

結果：約1秒で計算されます。

>>> give_me_math(10**100 + 3435) 
([332, 329, 326, 323, 320, 319, 317, 315, 314, 312, 309, 306, 304, 303, 300, 298, 295, 294, 289, 288, 286, 285, 284, 283, 282, 279, 278, 277, 275, 273, 272, 267, 265, 264, 261, 258, 257, 256, 255, 250, 247, 246, 242, 239, 238, 235, 234, 233, 227, 225, 224, 223, 222, 221, 220, 217, 216, 215, 211, 209, 207, 206, 203, 202, 201, 198, 191, 187, 186, 185, 181, 176, 172, 171, 169, 166, 165, 164, 163, 162, 159, 157, 155, 153, 151, 149, 148, 145, 142, 137, 136, 131, 127, 125, 123, 117, 115, 114, 113, 111, 107, 106, 105, 104, 100, 11, 10, 8, 6, 5, 3, 1], 1) 

800桁があまりにも速く動作します：

>>> give_me_math(10**800 + 3452) 

しかし、出力はもちろんのOPS懸念され、ここに投稿するには長すぎます。

ここで時間の複雑さは0（ln（n））なので、かなり効率的です。

Answer 2

なり、あなたが持つjava.mathパッケージにBigDecimalクラスを見てみる必要があります。

Answer 3

は、私はあなたがinteger factorizationを見てみましょう算術演算

を実行するための

1. GMPライブラリ（GNU多重精度演算ライブラリ）を見てすることをお勧めしたいです。リンクはWikipediaにリダイレクトされ、おそらく良い概観を与えるはずです。しかし、もう少し科学的であるために：

   イリノイ
の大学の Daniel Bernstein
2. Integer Factorization Algorithms（PDF）による
   • Integer factorization（PDF）物理学科のコネリーバーンズ、オレゴン州立大学

でここで

Answer 4

私は長い問題のバイナリ表現の問題をrun-length encodingに書き直すことができると思います。

はたとえば、以下の番号を取る：これはかなり恐ろしい見えます

17976931348623159077293051907890247336179769789423065727343008115773 
26758055009631327084773224075360211201138798713933576587897688144166 
22492847430639474110969959963482268385702277221395399966640087262359 
69162804527670696057843280792693630866652907025992282065272811175389 
6392184596904358265409895975218053120L 

。しかし、バイナリでは、

>>> bin(_) 
'0b11111111111111111111111111111111111111111111111111111111111111111 
11111111111111111111111111111111111111111111111111111111111111111111 
11111111111111111111111111111111111111111111111111111111111111111111 
11111111111111111111111111111111111111111111111111111111111111111111 
11111111111111111111111111111111111111111111111111111111111111111111 
11111111111111111111111111111111111111111111111111111111111111111111 
11111111111111111111111111111111111111111111111111111111111111111111 
11111111111111111111111111111111111111100000000000000000000000000000 
00000000000000000000000000000000000000000000000000000000000000000000 
00000000000000000000000000000000000000000000000000000000000000000000 
00000000000000000000000000000000000000000000000000000000000000000000 
00000000000000000000000000000000000000000000000000000000000000000000 
00000000000000000000000000000000000000000000000000000000000000000000 
00000000000000000000000000000000000000000000000000000000000000000000 
00000000000000000000000000000000000000000000000000000000000000000000 
0000000' 

です。これは約500ものもので、それに続く500のゼロです。これは、次のような表現を示唆しています。

2**1024 - 2**512 

どのように最初に大きな数値を取得したかです。

整数のバイナリ表現で著しく長い実行がない場合、これはまったく機能しません。 101010101010101010....が最悪です。