by jynx (Priest)
 on Jun 01, 2004 at 15:49 UTC 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];
}
}

Create A New User
Chatterbox?
 [stevieb]: ohhh, aaaand, I just learned that you can power an Arduino (Uno at least) by connecting any single analog pin to 5v on the Pi GPIO! That's bloody handy

How do I use this? | Other CB clients
Other Users?
Others drinking their drinks and smoking their pipes about the Monastery: (3)
As of 2017-06-22 23:05 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
How many monitors do you use while coding?

Results (531 votes). Check out past polls.