Beefy Boxes and Bandwidth Generously Provided by pair Networks
"be consistent"
 
PerlMonks  

jynx's scratchpad

by jynx (Priest)
on Jun 01, 2004 at 15:49 UTC ( [id://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
Domain Nodelet?
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others scrutinizing the Monastery: (3)
As of 2024-03-29 06:06 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found