Sunday, November 28, 2010

Gnumeric isprime() trial division

Gnumeric is one of several spreadsheet choices available to a Debian and / or GNU / Linux user.

How useful is Gnumeric to a mathematician? Quite.

It does include several functions that a more general package LibreOffice / OpenOffice Calc / Excel might not include.

Statistics and Number Theory are areas where Gnumeric currently outpaces the competition, in terms of available functions.

Here is one example, the isprime() function:
 * Returns -1 (out of bounds), 0 (non-prime), or 1 (prime).
static int
isprime (guint64 n)
      int i = 1;
      guint64 p = 2;

      if (n <= 1)
            return 0;

      for (i = 1; p * p <= n; i++) {
            if (ithprime (i, &p))
                  return -1;
            if (n % p == 0)
                  return 0;

      return 1;

Do not be alarmed if you are not comfortable looking through the above code, it is simply there so that I may elaborate next.

The method here is trial division, which is a reasonable way of going about things for integers say of a billion or so. It is implemented in C and so is likely pretty fast at getting it's answer.

In fact a little bit of trial and error can show (very roughly) where the threshold for this isprime() function lies:

Firstly a candidate number (fairly large by spreadsheet standards):


which isprime() answers with #LIMIT!

Now those handy zeros at the end of the number will serve to reduce the number in size a little. Removing a zero from ...001 give ...01 and a new number:  640237370572801

...which Gnumeric isprime() is happy to process and return FALSE.

If you are wondering, then the new number ending ...2801 has a factor of 2801, how interesting, and completely accidental.

Anyway, I have provided a 15 digit number that isprime() will process, and demonstrated that it does have a limit to what it will attempt.

So no, you are not going to find huge primes by using entries in a Gnumeric spreadsheet, however it does provide very convenient environment, for exploring integer construction.

Should you use Gnumeric, to test out your hypothesis for prime number patterns?
Well why not, there is value in knowing that constructive forms hold true up to 15 digits certainly.

Later you will maybe explore a dedicated number theory program, there are several great open source offerings. However Gnumeric seems like a great place to just dive in.

Links and further reading: