-! Copyright (c) 2007 Aaron Schaefer.
+! Copyright (c) 2008 Aaron Schaefer.
! See http://factorcode.org/license.txt for BSD license.
-USING: alien.syntax kernel math math.functions math.parser math.ranges memoize
+USING: kernel math math.constants math.functions math.parser memoize
project-euler.common sequences ;
IN: project-euler.025
! Memoized brute force
MEMO: fib ( m -- n )
- dup 1 > [ 1- dup fib swap 1- fib + ] when ;
+ dup 1 > [ [ 1 - fib ] [ 2 - fib ] bi + ] when ;
<PRIVATE
: (digit-fib) ( n term -- term )
- 2dup fib number>string length > [ 1+ (digit-fib) ] [ nip ] if ;
+ 2dup fib number>string length > [ 1 + (digit-fib) ] [ nip ] if ;
: digit-fib ( n -- term )
1 (digit-fib) ;
1000 digit-fib ;
! [ euler025 ] 10 ave-time
-! 5237 ms run / 72 ms GC ave time - 10 trials
+! 5345 ms ave run time - 105.91 SD (10 trials)
! ALTERNATE SOLUTIONS
<PRIVATE
-: phi ( -- phi )
- 5 sqrt 1+ 2 / ;
-
: digit-fib* ( n -- term )
- 1- 5 log10 2 / + phi log10 / ceiling >integer ;
+ 1 - 5 log10 2 / + phi log10 / ceiling >integer ;
PRIVATE>
1000 digit-fib* ;
! [ euler025a ] 100 ave-time
-! 0 ms run / 0 ms GC ave time - 100 trials
+! 0 ms ave run time - 0.17 SD (100 trials)
-MAIN: euler025a
+SOLUTION: euler025a