これは実際にはプログラミングコンテストのためのものですが、私は本当に一生懸命に努力しましたが、これを行う方法についての最も微妙な手がかりさえも得ていません。
n mの最初と最後のk桁を見つけます。ここで、nとmは非常に大きくなる可能性があります〜10^9。
最後のk桁については、べき乗剰余を実装しました。
最初のkについては、特定の累乗まで二項定理を使用することを考えましたが、階乗の計算が非常に多く、n ^ mを（x + y）として展開できる最適な点を見つける方法がわかりません。m。
では、計算全体を実行せずに最初のk桁を見つける既知の方法はありますか？
更新1<=k <= 9であり、kは常にnmの<=桁になります
確かではありませんが、アイデンティティn m = exp10（m log10（n））= exp（q（m log（n）/ q））ここで、q = log（10）が頭に浮かび、最初のK exp10（x）の桁= exp10（frac（x））の最初のK桁ここで、frac（x）=xの小数部分=x-floor（x）。
より明確に言うと、n mの最初のK桁は、仮数の最初のK桁= exp（frac（m log（n）/ q）* q）です。ここで、q = log（10）です。
または、この会計演習をさらに進めて、exp（（frac（m log（n）/ q）-0.5）* q）* sqrt（10）を使用することもできます。これも同じ仮数（+したがって最初のKは同じ）です。 exp（）関数の引数が0を中心に（および+/- 0.5 log 10 = 1.151の間に）配置されるように、スピーディーな収束を実現します。
（いくつかの例：2 100の最初の5桁が必要だとします。これは、exp（（frac（100 log（2）/ q）-0.5）* q）* sqrt（10）=1.267650600228226の最初の5桁に相当します。 2100の実際の値はMATLABによると1.267650600228229e+030であり、bignumライブラリは便利ではありません。21,000,000,000の仮数の場合、4.612976044195602を取得しますが、実際にチェックする方法はありません。誰かがすでにハードワークを行っているMersenneプライムのページ; 220996011 -1 = 125,976,895,450 ...そして私の式はMATLABで計算された1.259768950493908を与え、9桁目以降は失敗します。）
テイラー級数（ n mではなくexpとlog ）をエラー範囲とともに使用し、エラー範囲が最初のK桁を下回るまで項を追加し続ける場合があります。（通常、関数近似にテイラー級数を使用しません-それらの誤差は、目的の間隔ではなく、単一の点の周りで最も正確になるように最適化されます-しかし、数学的に単純であるという利点があります。項を追加するだけで、精度を任意の精度に上げることができます）
対数については、お気に入りの近似値を使用します。
良い。最初のn桁
だけを計算して取得したい。
次の繰り返しで計算します。
あなたが持ってい
ます。それぞれを正確に計算する
わけではありません。問題は、 の相対誤差がa の相対誤差のn倍未満であるということです。
未満の最終的な相対誤差を取得したいと考えています
。したがって、各ステップの相対誤差は になる可能性があります
。各ステップで最後の桁を削除します。
たとえば、a=2、b=16、n=1 です。最終的な相対誤差は 10^{-n} = 0,1 です。各ステップの相対誤差は 0,1/16 > 0,001 です。したがって、各ステップで 3 桁が重要です。n = 2 の場合、4 桁を保存する必要があります。
2 (1)、4 (2)、8 (3)、16 (4)、32 (5)、64 (6)、128 (7)、256 (8)、512 (9)、1024 (10) - -> 102, 204 (11), 408 (12), 816 (13), 1632 (14) -> 163, 326 (15), 652 (16).
答え: 6.
このアルゴリズムの複雑さはO(b)です。しかし、 O(log b)を取得するように変更するのは簡単です
二乗による指数化を見たことがありますか？必要なものだけを計算するように、メソッドの1つを変更できる場合があります。
私の最後のアルゴリズムクラスでは、あなたがしていることに似た何かを実装する必要があり、そのページが有用であったことを漠然と覚えています。
各ステップで切り捨てるとしますか? これがどれほど正確かはわかりませんが、たとえば、n=11 m=いくつかの大きな数を取り、最初の 2 桁が必要です。
再帰的に:
12 x 11 -> 132 トランケート -> 13 リピート、
(132 切り捨て) x 11 -> 143. ...
最後に、行った切り捨ての数に相当する #0 を追加します。