http://qs321.pair.com?node_id=358150

Public Scratchpad

Download, Select Code To D/L

---

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};
    }
  }
}
[download]

---

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];
  }
}
[download]