Archive for the ‘bigint’ Tag

projecteuler29

 projecteuler問題29は、2 から 100 までの自然数を 2 乗から 100乗 して、同じものを除くと何個になるかという問題。
 だから、スクリプトは単純、

(let (lst)
  (for (i 2 100)
    (for (j 2 100)
      (push (apply * (cons 1L (dup i j))) lst -1)
    )
  )
 (length (unique lst)))

 こんな感じ。1L を cons しているのは、大整数にするため。100 乗するには 64 ビット整数では足りないですからね(笑)

(let (lst)
  (for (i 2 100)
    (for (j 2 100)
      (push (apply * (map bigint (dup i j))) lst -1)
    )
  )
 (length (unique lst)))

でも同じになります。
 ここで bigint は整数を大整数に変換します。
 また、unique は同一数値を除去してくれます。
 これを実行すると

9183
> 

 と答えが求まります。

 以上、如何でしょうか?

広告

projecteuler20

 projecteuler問題20 は、100 の階乗を求め、各桁を足した和を求めるという問題。
 桁数に制限のない大整数のある newLISP とって、得意とするところ。

> (apply * (map bigint (sequence 1 100)))
93326215443944152681699238856266700490715968264381621468592963895217599993229915
608941463976156518286253697920827223758251185210916864000000000000000000000000L
> (apply + (map int (explode (chop (string (apply * (map bigint (sequence 1 100))))))))
648
> 

 これでおしまい。答えは 648 。
 これでは、解説しようが無い(笑)

 以上、如何でしょうか?

projecteuler16...または、大整数の使い方

 projecteuler問題16 は、2 の 1000 乗を求め、桁ごとの数値を足した和を求める問題。
 ポイントは、300桁以上ある 2 の 1000 乗を桁落ち無しで求めること。
 64ビット整数では 21桁 が限度ですから、その桁数が大きさが問題となっている訳です。
 でも、newLISP には大整数がありますので、全く問題になりません(笑)
 答えは、

> (let (res (apply * (dup 2L 1000))) res)
10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376L
> (let (res (apply * (dup 2L 1000))) (apply + (map int (explode (chop (string res))))))
1366
> 

 ざっと、こんなもん。
 さて、解説ですが、数値の末尾に L を付けると大整数になります。
 string で 文字列にして、explode で各桁数に分解し、int で整数にもどして、足すだけ。
 chop は大整数の L を外すためのもの。
 int のオプションを使って

> (let (res (apply * (dup 2L 1000))) (apply + (map (fn (x) (int x 0)) (explode (string res)))))
1366
> 

 とすることもできます。

 以上、如何でしょうか?

projecteuler15...または、再帰による組み合わせ

 projecteuler問題15 は、格子の道筋を数える問題。
 とは言え、N×Nの正方格子で下と右の二つを半分ずつ選ぶことになるから、その組合せ数を求めるだけなら、以下の計算で十分。

> [cmd]
(int (/ (apply * (map bigint (sequence 40 21)))
        (apply * (map bigint (sequence 20  1)))))
[/cmd]
137846528820
> 

 bigint大整数にしておくのがみそ(笑)
 さて、具体的に道筋を求めるには、下と右をそれぞれ '1''0' とすれば、

(define (test n m (bit '()) res)
  (let (c (count '(0 1) bit))
    (if (= (length bit) (+ n m)) (push bit res -1)
      (begin
        (when (< (c 0) n) (setq res (test n m (cons 0 bit) res)))
        (when (< (c 1) m) (setq res (test n m (cons 1 bit) res)))
      ))
  res))

 として、

> (test 2 2)
((1 1 0 0) (1 0 1 0) (0 1 1 0) (1 0 0 1) (0 1 0 1) (0 0 1 1))
> (length (test 2 2))
6
> 

 再帰を使っているので 20×20 を実行させると恐ろしく時間がかかります。ご注意を(汗)

 以上、如何でしょうか?

projecteuler13...または、有効桁数について

 projecteuler問題13は、既にやっていますが、今回は番外編。
 大整数(big integers)が使えるようになった newLISP には簡単な問題ですが、求める答えが和の最初の 10 桁だけなら、大整数を使うまでもありません。
 組込関数 bigint前回bigint の代わりに eval-string を使っています)で大整数にせずとも、float を使って浮動小数点数で計算しても、こと足りるのです。
 何故なら、問題は高々 50 個の加算ですから、10 桁の値を得るには、12 桁の精度を保持しておけば十分です。そして、

> (format "%f" (float 37107287533902102798797998220837590246510135740250L))
"37107287533902104311025740304689820495323647180800.000000"
>

 このように、newLISP の浮動小数点数は 64 ビット長倍精度なので、16 桁くらいまでは精度が保たれます。つまり、問題13 は newLISP の浮動小数点数で十分対応可能です。
 浮動小数点数に変換したリストを入れた data を使って、結果だけ記せば、

> (apply add data)
5.53737623e+051
> (format "%f" (apply add data))
"5537376230390877287140145935443224959721771787878400.000000"
> (0 10 (format "%f" (apply add data)))
"5537376230"
> 

 こんな感じで、答えは合っています。
 まっ、大整数のある newLISP には要らぬことですが(笑)。
 今回の例ではピンと来ないかもしれませんが、技術計算では有効桁数を常に頭に入れて置くことが必須です。newLISP を使っていると往々にして忘れがちですが(汗)。
 ちなみに v.10.5.5 から、大整数の整数演算における引数が二つという制限がなくなり、ますます使いやすくなります。また、浮動小数点数の標準表記も 10 桁から 15 桁になるようです。詳しくは、こちらでどうぞ。

 以上、如何でしょうか?