scratchpad
jynx
<!-- <br>
My usual disclaimer:<p>
i'm not a master at obfu, and these may or may not be
harder to read than the original, but they
were a fun exercise for me and i hope they show a few different things for the original poster to chew on later...<p>
nuf evah,<br>
jynx<p>
<hr>
-->
<br>
<p>As per discussion over [id://610314|here].</p>
A few notes:<ul>
<li>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.</li>
<li>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. <del>For larger values i'd forego the hash and use a binsearch on the array to emulate the exists call.</del> For larger values don't use this algorithm since its horribly inefficient.</li>
<li>[Graff]'s [id://610253|version] later in the thread performs the caching more suitably to the problem being solved. This is meant as a more generic algorithm.</li>
</ul>
<p><b>Update</b>: 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). <del>A purge on extraneous values occurs whenever a candidate is proposed that's lower than the current prime threshhold.</del> A purge on extraneous values occurs directly after a fill. This means all accesses of previously checked numbers are in O(1) time.</p>
<hr>
<code>
{
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};
}
}
}
</code>
<hr>
<p>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.</p>
<code>
{
my @fib = (1, 1);
sub comp_fib {
my $posit = shift;
while (@fib < $posit) {
push @fib, $fib[-1] + $fib[-2];
}
return $fib[$posit-1];
}
}
</code>