Forth for Enlightenment, part thirteen of ten, Primes too

In part nine we had an introduction to testing if a number is prime. A function to check for primality was presented. It's short and to the point. And, since it checks by dividing the number by all integers up to the square root of the number, the execution time is proportional to the square root of the number. Is there something that can be done to speed it up? Absolutely.

For one thing, all numbers greater than two are divisible by two. So dividing by those numbers doesn't have to be done. One can test for even numbers by starting with three and skipping every other number. That's a quick and easy test. One can apply the same logic and skip numbers divisible by three after three. That's a little more complicated. The easiest approach appears to be to note that you can skip every other division by three, since those are divisible by two. That is, one can skip by six, and only check some of the numbers in each block. This code performs this sort of check. It searches two and three, then by sixes starting with five.

«
 0 0 → n s a «
  IF n 2 < THEN
   1 'a' STO
  ELSE
   IF n 3 > THEN
    IF n 2 MOD 0 == THEN
     2 'a' STO
    ELSE
     IF n 3 MOD 0 == THEN
      3 'a' STO
     ELSE
      IF n 7 > THEN
       n √ FLOOR 's' STO
       5 s FOR x
        IF n x MOD 0 == THEN
         x 'a' STO
         s 'x' STO
        END
        IF n x 2 + MOD 0 == THEN
         x 2 + 'a' STO
         s 'x' STO
        END 
       6 STEP
      END
     END
    END
   END
  END
  a
 »
» 'ISP2' STO

Here are some timings to show the speed up. On the left is the number that is tested. Then, the number of seconds for ISP and ISP2 to complete the check. Note that all numbers tested are, in fact, primes. So this is sort of the worst case. There was no run of 10000019 for ISP.

Number	ISP	ISP2
10007	5	2.3
100003	15	5.4
1000003	47.3	15.5
10000019	na	47.7

In any case, it's pretty clear that as the number goes up, so does the time. Of note is that ISP2 performs about as well as ISP does on numbers that are ten times larger. That's because both algorithms have time that goes up with the square root of the number. The ISP2 implementation is faster because instead of checking every number, it checks two numbers for every six. That's one third the number of divide checks. Since it does one third as much work, it should perform about as well on number 3 * 3 = 9 times larger. Nine is pretty similar to ten from a benchmark perspective.

This factor of three performance increase comes at a cost. For the HP-28c, this cost is size. While ISP only requires 82 bytes, ISP2 requires 443 bytes. Is that a big deal? Yes. For one thing, since this is a single big function, if you make a mistake and need to edit it, you get "No room to enter". You have to type the whole function in again from scratch.

Are there prime number test algorithms that do better than going up in time with the square root of the number? Yes. But they either require remembering stuff, or have more code, or both. The HP-28c simply doesn't have the memory to do a significant sieve or the code for the Miller-Rabin primality test.