Posted to tcl by kbk at Tue Aug 21 01:11:44 GMT 2012view raw

  1. namespace path ::tcl::mathop
  2.  
  3. interp recursionlimit {} 120000
  4.  
  5. proc fib {n {i 0} {this 0} {next 1}} {
  6. if {$i >= $n} {
  7. return $this
  8. } else {
  9. tailcall fib $n [+ $i 1] $next [+ $this $next]
  10. }
  11. }
  12.  
  13. puts [time {set result [fib 40000]}]
  14. #puts "fib(40000) == $result"
  15.  
  16. proc fib {n} {
  17. variable memo
  18. if {[info exists memo($n)]} {
  19. return $memo($n)
  20. } elseif {$n == 0} {
  21. return 0
  22. } elseif {$n == 1} {
  23. return 1
  24. } else {
  25. return [set memo($n) [+ [fib [- $n 2]] [fib [- $n 1]]]]
  26. }
  27. }
  28.  
  29. puts [time {set result [fib 40000]}]
  30. #puts "fib(40000) == $result"
  31.  
  32. exit