added approx to make faster

1 files changed, 14 insertions, 15 deletions

diff --git a/challenge-112/james-smith/perl/ch-2.pl b/challenge-112/james-smith/perl/ch-2.pl
index 7650a2a06d..541c0eb97b 100644
--- a/challenge-112/james-smith/perl/ch-2.pl
+++ b/challenge-112/james-smith/perl/ch-2.pl
@@ -16,20 +16,18 @@ my $N = @ARGV     ? $ARGV[0] : 30;
 my $I = @ARGV > 1 ? $ARGV[1] : 100_000;
 my $cache;
 
-is(climb(                   $_), $ans[$_] ) foreach 1..$N;
-is(climb_fib(               $_), $ans[$_] ) foreach 1..$N;
-is(climb_fib_1liner(        $_), $ans[$_] ) foreach 1..$N;
-is(climb_fib_global(        $_), $ans[$_] ) foreach 1..$N;
-is(climb_fib_1liner_global( $_), $ans[$_] ) foreach 1..$N;
+is(climb(            $_), $ans[$_] ) foreach 0..$N;
+is(climb_fib(        $_), $ans[$_] ) foreach 0..$N;
+is(climb_fib_1liner( $_), $ans[$_] ) foreach 0..$N;
+is(climb_fib_approx( $_), $ans[$_] ) foreach 0..$N;
 
 done_testing();
 
 cmpthese($I,{
   'climb'  => sub { climb(            $_ ) foreach 0..$N; },
   'fib'    => sub { climb_fib(        $_ ) foreach 0..$N; },
-  'fib-g'  => sub { climb_fib_global( $_ ) foreach 0..$N; },
   'fib-1'  => sub { climb_fib_1liner( $_ ) foreach 0..$N; },
-  'fib-1g' => sub { climb_fib_1liner_global( $_ ) foreach 0..$N; },
+  'fib-a'  => sub { climb_fib_approx( $_ ) foreach 0..$N; },
 });
 
 ## Once we look at the formula for climb - we
@@ -44,6 +42,13 @@ cmpthese($I,{
 ## speeds it up futher - this is down to
 ## storing the caclulation of phi^(n+!) only
 ## temporarily
+##
+## Also we note that actually we can forgo this - by
+## noting that the contribution to the fibonnaci
+## value from the (1/phi)^n part is less than 1. So
+## we can replace the formula with the approximation below.
+##
+## This works for all values of n>0;
 
 sub climb {
   my($a,$b) = (1,1);
@@ -51,12 +56,6 @@ sub climb {
   return $b;
 }
 
-my $p;
-sub climb_fib_global {
-  $p = ((1 + sqrt 5)/2)**($_[0]+1);
-  return int(0.001+ ($p - ($_[0]&1?1:-1)/$p)*sqrt 0.2);
-}
-
 sub climb_fib {
   my $q = ((1 + sqrt 5)/2)**($_[0]+1);
   return int(0.001+ ($q - ($_[0]&1?1:-1)/$q)*sqrt 0.2);
@@ -66,6 +65,6 @@ sub climb_fib_1liner {
   return int(0.001 + (($a = ((1+sqrt 5)/2)**($_[0]+1)) - ($_[0]&1?1:-1)/$a)*sqrt 0.2);
 }
 
-sub climb_fib_1liner_global {
-  return int(0.001 + (($p = ((1+sqrt 5)/2)**($_[0]+1)) - ($_[0]&1?1:-1)/$p)*sqrt 0.2);
+sub climb_fib_approx {
+  return int(0.4 + (0.5+sqrt 1.25)**($_[0]+1)*sqrt 0.2);
 }