Beefy Boxes and Bandwidth Generously Provided by pair Networks
Clear questions and runnable code
get the best and fastest answer
 
PerlMonks  

jynx's scratchpad

by jynx (Priest)
on Jun 01, 2004 at 15:49 UTC ( #358150=scratchpad: print w/ replies, xml ) Need Help??


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]; } }
Log In?
Username:
Password:

What's my password?
Create A New User
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others taking refuge in the Monastery: (11)
As of 2014-09-15 09:54 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite cookbook is:










    Results (146 votes), past polls