メモリと計算時間のトレードオフ

「DNA鑑定とバースデイ・パラドクス」にて

・対数を使うにしても、Rでやるにもn!;n=10^9とかになってくると、メモリの問題が出てくるようだ
・そんなのを少し回避しながら計算してみた

メモリと計算時間は互いにトレードオフの関係にある。
計算時間は掛かる（べらぼうに！でも許容範囲）がメモリは全く使わないプログラムを書けばよいだけだ。
このプログラムは引用元のプログラムが以下に無駄な計算をしているかを明示している。

func <- function(n) {
    q <- 4.7e12
    p <- 1
    for (i in 1:n - 1) {
        p <- p*(q-i)/q
    }
}

n = 10^i で i が 1 大きくなると，計算時間は 10 倍になる。
システム時間がほとんど掛かっていないところにも注目。

> for (i in 0:8) {
+     print(system.time(func(10^i)))
+ }
   ユーザ   システム       経過  
     0.001      0.000      0.000
   ユーザ   システム       経過  
         0          0          0
   ユーザ   システム       経過  
     0.001      0.000      0.001
   ユーザ   システム       経過  
     0.002      0.000      0.002
   ユーザ   システム       経過  
     0.018      0.000      0.018
   ユーザ   システム       経過  
     0.190      0.001      0.190
   ユーザ   システム       経過  
     1.941      0.011      1.939
   ユーザ   システム       経過  
    19.492      0.089     19.387
   ユーザ   システム       経過  
   196.289      1.623    196.516