Beefy Boxes and Bandwidth Generously Provided by pair Networks
The stupid question is the question not asked

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?

What's my password?
Create A New User
[LanX]: I mean hiding my friends FROM my friends
[Your Mother]: Yeah. I don't know what they expect. If a stranger can see the post or list or whatever, so can a harvesting program.
[Your Mother]: HA.
[NodeReaper]: he's already hiding from me :(
[Corion]: Your Mother: Even I don't remember what "related and neat" I could have that would fit to 1211240 :) Maybe "pjax", which turns a static site into a Javascript-partial -reloading site? That's purely Javascript though
[LanX]: true I might get visa problems when they hear about my love for massacres ...
[Your Mother]: Corion, it was something similar to Cometd/Websockets.
LanX is reminded that public sarcasm is causing rpoblems nowadays ... ehm ...
[Your Mother]: Americans love massacres as long as it's brown and red people. Ooops. That was supposed to be a state secret. There goes my Q clearance.

How do I use this? | Other CB clients
Other Users?
Others meditating upon the Monastery: (11)
As of 2018-03-19 13:35 GMT
Find Nodes?
    Voting Booth?
    When I think of a mole I think of:

    Results (240 votes). Check out past polls.