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):

factorial(18)+1=6402373705728001

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: 

2 comments:

  1. Just a word of warning about creating large spreadsheets with lots and lots of isprime() calls.

    Whilst the code is clean, and executes quickly, I recommend you experiment before filling several screenfuls of cells with isprime() of large integers (say 15 digits or so)

    At some point all those calls will ask something of your CPU, and that would maybe tax a netbook into submission.

    I can perhaps comment further when I have filled a few pages myself, but as yet, I have not used Gnumeric with sheets and sheets full of isprime() to say for sure.

    ReplyDelete
  2. Having now had an opportunity to try out isprime() on columns of possible primes, I can now say something further.

    If you have 50 ten digit prime candidates to test, then pasting isprime() into 50 cells at once, should not stretch a modern desktop/laptop processor too much.

    Once you get above 15 digit prime candidates, then things start to slow down a bit (understandably)

    Pasting isprime() into cells, to perform hundreds of isprime() tests on 16 digit numbers, all at once, will produce a noticeable slowdown.

    Just a Gnumeric tip about E+15 notation, which will appear when numbers 16 digits or greater are pasted into Gnumeric:
    Right Click on the Column and change type to Number from 'General' to see the number in full expansion.

    Note: Seeing the number in full expansion, might not mean that every formula or operation on that number, operates at full precision. All current desktop spreadsheet software has known precision limits, that will sometimes produce results you might not expect.

    If you are on a low power portable / tablet, then isprime() on numbers larger than 15 digits might prove prohibitively slow.

    ReplyDelete