Public Scratchpad | Download, Select Code To D/L |

As per discussion over here.

A few notes:- I've used closures like this before, but i don't know if this is what is meant by "memoization". As such, i'm sure i'm doing many things wrong, but i'm trying to get a feel for what was intended. Any feedback is appreciated.
- For small numbers memory space shouldn't be a problem so the duplication from having both a hash and an array isn't a big deal.
~~For larger values i'd forego the hash and use a binsearch on the array to emulate the exists call.~~For larger values don't use this algorithm since its horribly inefficient. - Graff's version later in the thread performs the caching more suitably to the problem being solved. This is meant as a more generic algorithm.

**Update**: Some modifications have been made. The code now only caches primes up until the square root of the candidate. It memoizes all candidates (prime or not). ~~A purge on extraneous values occurs whenever a candidate is proposed that's lower than the current prime threshhold.~~ A purge on extraneous values occurs directly after a fill. This means all accesses of previously checked numbers are in O(1) time.

{ my @primes = (2, 3); my %primes = (2 => 2, 3 => 3); my %memo; my $_is_prime = sub { my $posit = shift; my $sqrtp = sqrt($posit); for my $p (@primes) { last if $p > $sqrtp; return 0 unless $posit % $p; } return 1; }; my $_fill = sub { my $bar = int sqrt(shift); for (my $last = $primes[-1] + 2; $primes[-1] < $bar; $last += 2) { if (exists $memo{$last} and $memo{$last}) { push @primes, $primes{$last} = delete $memo{$last}; } else { push @primes, $primes{$last} = $last if $_is_prime->($last); } } }; my $_purge = sub { foreach (keys %memo) { if ($_ < $primes[-1]) { delete $memo{$_}; } } }; sub is_prime { my $posit = shift; if ($primes[-1] < $posit) { return $memo{$posit} if exists $memo{$posit}; $_fill->($posit); $_purge->(); return $memo{$posit} = $_is_prime->($posit) ? $posit : 0; } else { return exists $primes{$posit}; } } }

As an amusement, here's the same algorithmic setup as above (caching all numbers <= the requested one making accessing them much faster at the expense of space), only applied to Fibonacci numbers. My guess (though i could be wrong?) is that this is just as useless as the algorithm above.

{ my @fib = (1, 1); sub comp_fib { my $posit = shift; while (@fib < $posit) { push @fib, $fib[-1] + $fib[-2]; } return $fib[$posit-1]; } }