#! perl -slw use strict; use 5.010; use Time::HiRes qw[ time ]; use constant { GR => 1.6180339887498948482, ROOT5 => sqrt( 5 ), }; sub fibCalc { int( GR ** \$_[0] / ROOT5 + 0.5 ); } sub fibIter { my \$n = shift; return \$n if \$n < 2; my( \$f1, \$f2, \$fib ) = ( 1, 0, 0 ); for ( 2 .. \$n ) { \$fib = \$f1 + \$f2; ( \$f1, \$f2 ) = ( \$fib, \$f1 ); } return \$fib; } sub fibMem { state %cache; my \$n = shift; return \$n if \$n < 2; return ( \$cache{ \$n - 2 } //= fibMem( \$n - 2 ) ) + ( \$cache{ \$n - 1 } //= fibMem( \$n - 1 ) ); } sub fibRec { my (\$n) = @_; return 0 if \$n == 0; return 1 if \$n == 1; return fibRec(\$n-2) + fibRec(\$n-1); } printf "%2d : rec:%8d mem: %8d iter:%8d calc:%8d\n", \$_, fibRec( \$_ ), fibMem( \$_ ), fibIter( \$_ ), fibCalc( \$_ ) for 1 .. 30; my \$start = time; my \$total = 0; \$total += fibRec( \$_ ) for 1 .. \$ARGV[0]; printf "recursive: Got %d; took %f seconds\n", \$total, time() - \$start; \$start = time; \$total = 0; \$total += fibMem( \$_ ) for 1 .. \$ARGV[0]; printf "memoized: Got %d; took %f seconds\n", \$total, time() - \$start; \$start = time; \$total = 0; \$total += fibIter( \$_ ) for 1 .. \$ARGV[0]; printf "iterative: Got %d; took %f seconds\n", \$total, time() - \$start; \$start = time; \$total = 0; \$total += fibCalc( \$_ ) for 1 .. \$ARGV[0]; printf "calculate: Got %d; took %f seconds\n", \$total, time() - \$start; __END__ C:\test>885839 35 1 : rec: 1 mem: 1 iter: 1 calc: 1 2 : rec: 1 mem: 1 iter: 1 calc: 1 3 : rec: 2 mem: 2 iter: 2 calc: 2 4 : rec: 3 mem: 3 iter: 3 calc: 3 5 : rec: 5 mem: 5 iter: 5 calc: 5 6 : rec: 8 mem: 8 iter: 8 calc: 8 7 : rec: 13 mem: 13 iter: 13 calc: 13 8 : rec: 21 mem: 21 iter: 21 calc: 21 9 : rec: 34 mem: 34 iter: 34 calc: 34 10 : rec: 55 mem: 55 iter: 55 calc: 55 11 : rec: 89 mem: 89 iter: 89 calc: 89 12 : rec: 144 mem: 144 iter: 144 calc: 144 13 : rec: 233 mem: 233 iter: 233 calc: 233 14 : rec: 377 mem: 377 iter: 377 calc: 377 15 : rec: 610 mem: 610 iter: 610 calc: 610 16 : rec: 987 mem: 987 iter: 987 calc: 987 17 : rec: 1597 mem: 1597 iter: 1597 calc: 1597 18 : rec: 2584 mem: 2584 iter: 2584 calc: 2584 19 : rec: 4181 mem: 4181 iter: 4181 calc: 4181 20 : rec: 6765 mem: 6765 iter: 6765 calc: 6765 21 : rec: 10946 mem: 10946 iter: 10946 calc: 10946 22 : rec: 17711 mem: 17711 iter: 17711 calc: 17711 23 : rec: 28657 mem: 28657 iter: 28657 calc: 28657 24 : rec: 46368 mem: 46368 iter: 46368 calc: 46368 25 : rec: 75025 mem: 75025 iter: 75025 calc: 75025 26 : rec: 121393 mem: 121393 iter: 121393 calc: 121393 27 : rec: 196418 mem: 196418 iter: 196418 calc: 196418 28 : rec: 317811 mem: 317811 iter: 317811 calc: 317811 29 : rec: 514229 mem: 514229 iter: 514229 calc: 514229 30 : rec: 832040 mem: 832040 iter: 832040 calc: 832040 recursive: Got 24157816; took 49.278000 seconds memoized: Got 24157816; took 0.000115 seconds iterative: Got 24157816; took 0.000416 seconds calculate: Got 24157816; took 0.000073 seconds ##```## #! perl -slw use strict; use futures; sub fibonacci { my \$n = shift; return \$n if \$n < 2; my \$r1 = futures->new( \&fib_t1, \$n -2 ); my \$r2 = futures->new( \&fib_t1, \$n -1 ); return \$r1 + \$r2; } sub fib_t1 { my \$n = shift; return \$n if \$n < 2; my \$r1 = futures->new( \&fib_t2, \$n -2 ); my \$r2 = futures->new( \&fib_t2, \$n -1 ); return \$r1 + \$r2; } sub fib_t2 { my \$n = shift; return \$n if \$n < 2; return fib_t2( \$n -2 ) + fib_t2( \$n -1 ); } printf "\$_ : %d\n", fibonacci( \$_ ) for 1 .. \$ARGV[ 0 ]; __END__ C:\test>885839-t 20 1 : 1 2 : 1 3 : 2 4 : 3 5 : 5 6 : 8 7 : 13 8 : 21 9 : 34 10 : 55 11 : 89 12 : 144 13 : 233 14 : 377 15 : 610 16 : 987 17 : 1597 18 : 2584 19 : 4181 20 : 6765 ##``````## package futures; use threads; sub TIESCALAR { my( \$class, \$thread ) = @_; return bless [ \$thread ], \$class; } sub STORE { die "Futures cannot be assigned to"; } sub FETCH { my \$self = shift; my \$r = \$self->[0]->join; return \$r; } sub new { my( \$class, \$code, @args ) = @_; my \$thread = &async( \$code, @args ); tie my \$future, 'futures', \$thread; return \$future; } 1; ```