Problem 99 - 指数的爆発

Scheme

うほ。簡単。と思って取り組んでみたら罠が・・・。


Problem 99 - PukiWiki

指数の形で表される2つの数, 例えば 2^11 と 3^7, の大小を調べることは難しくはない. 電卓を使えば, 2^11 = 2048 < 3^7 = 2187 であることが確かめられる.

しかし, 632382^518061 > 519432^525806 を確認することは非常に難しい (両者ともに300万桁以上になる).

各行に1組が書かれている1000個の組を含んだ22Kのテキストファイル base_exp.txt から, 最大の数が書かれている行の番号を求めよ.

注: ファイル中の最初の二行は上の例である.


Schemeはこういうの得意だろうと思ってやってみたら・・・。

(define (problem99 data)
  (letrec ((iter (lambda (n max-n max-value lis)
                   (if (null? lis)
                       max-n
                       (let ((e (expt (caar lis) (cadar lis))))
                         (if (> e max-value)
                             (iter (+ n 1) n e (cdr lis))
                             (iter (+ n 1) max-n max-value (cdr lis))))))))
    (iter 1 0 0 data)))

(problem99 *data99*) ; 終わらず

最初の数行こなすのに何分かかかる。30分くらい回してみたけどムリだった。


むぅSchemeパワーを発揮してもムリだとわかったので、対数パワーを借りる。


公式はコレだ。


log a^b = b log a


指数的爆発には対数で挑め！！

(define (problem99 data)
  (letrec ((iter (lambda (n max-n max-value lis)
                   (if (null? lis)
                       max-n
                       (let ((e (* (cadar lis) (log (caar lis) ))))
                         (if (> e max-value)
                             (iter (+ n 1) n e (cdr lis))
                             (iter (+ n 1) max-n max-value (cdr lis))))))))
    (iter 1 0 0 data)))

(problem99 *data99*) ; 709

すぐ終わりました。ハイ。

参考

  • 基礎からよくわかる基礎解析
    • 1989年発行。高校の先輩から貰った参考書を今でも使ってます。

先輩ありがとう!!