暗算の世界記録

人間計算機ことフランス人のAlexis Lemaire氏によって暗算の世界記録が更新されたそうだ。数学界におけるフランス人の活躍っぷりは異常。

86332348800352843610126990022313468510477370930755992152681390347795323097511687170057636480807271413833247121705763111108558415623458020018\ 525612852897226196105357173387251523920946707380414694987101という200桁の自然数の13乗根を72.438秒で解いたという話。

答えは2397兆2076億6796万6701

本人曰く「最初と最後の桁は直ぐにわかるが中間が難しい」との事なので、一般の計算メソッドとそれほど変わらない気がする。頭を対数、尾を余剰法で決定した上で、中間は分割法なり擬似ニュートン法でも用いながら一気に候補を絞り込んで行くといった感じだろうか。２分法だと７００回ぐらいループさせる必要があるが、うまい漸近法を持ってくればなんとかなるだろう。

安直に思いついた発想では対数から１〜２桁ぐらいの精度で初期値を与え、Nの13乗根に収束する適当な漸化式

例えば
x \rightarrow \frac{N+12x^{13}}{13x^{12}}
で絞った上で最後の２〜３桁は余剰法で処理するという方法。級数展開とどちらが速いかはわからない。

自分がやると紙が使えても１時間は掛かりそうだ。

と、思ったので少し調べてみると13乗根計算は結構いろいろな性質が使えるようで、意外に計算量を抑えられるかも知れない。例えば、オイラー関数φ(10)=4なのでフェルマーの小定理により『X^13≡X(mod10)』が成立する。同様に、１３乗根と７７乗は10^4を法として合同だ。あとは慣れだろうね。彼は100桁の13乗根を3.62秒で解いているそうなので、単純な試算で計算量は桁が２倍になる毎に２０倍程度のようだ。

PS. 森博嗣の小説を思い浮かべた方は猛省されたし。