The GNU 3DLDF Prime Numbers Page

Author: Laurence D. Finston.

This copyright notice applies to the text and source code of this web site, and the graphics that appear on it. The software described in this text has its own copyright notice and license, which can be found in the distribution itself.

Copyright (C) 2005, 2006 The Free Software Foundation

Permission is granted to copy, distribute, and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation; with no Invariant Sections, with no Front-Cover Texts, and with no Back-Cover Texts. A copy of this license is included in the file COPYING.TXT

Last updated: January 20, 2006.

Table of Contents

Introduction

2005.12.06.
I have started working on functions and parser rules for prime numbers. You can find the n^th prime number by using the get_prime operator:

ulong_long L;
L := get_prime 24;
show L;
--> 89

It's also possible to store a range of prime numbers in a ulong_long_vector by using the get_prime_vector operator:

ulong_long_vector LV;
LV := get_prime_vector 3 7;
show LV;
--> 
>> ulong_long_vector:
size: 5
(0) : 5
(1) : 7
(2) : 11
(3) : 13
(4) : 17

In the fullness of time, I plan to add more functions for use with prime numbers. However, testing for primality and finding the prime factors of composite numbers are not easy tasks.

Implementation Details

The prime number functions involve a considerable amount of overhead.

get_prime returns a value of the type ulong_long, which I've added especially for prime numbers. ulong_long corresponds to the unsigned long long type in C and C++. numeric, on the other hand, corresponds to either float or double, depending on the value of a preprocessor variable when 3DLDF is built. Currently, the default is double.

The problem with the floating point types float and double is that they represent integers with limited precision, whereas the integer types (char, short, int, long, and long long, with their unsigned variants) represent integers exactly. I also wanted to be able to work with the largest possible prime numbers, so I chose unsigned long long rather than unsigned int or unsigned long. The prime numbers are all positive, so there was no need to use signed long long.

The objects and functions for the prime numbers are declared in namespace Prime_Numbers. When Prime_Numbers::get_prime() is called for the first time, it causes a table of prime numbers to be created. It is stored in a vector<unsigned long long> pointed to by the pointer Prime_Numbers::primes_table. Just before 3dldf exits, it writes a binary file called primes.lbn, creates a checksum for it (stored in the file primes.lsm), and compresses it using gzip to create primes.lbn.gz. The next time 3dldf is run, it uncompresses primes.lbn.gz, checks primes.lbn against the checksum, and if it hasn't been corrupted, reads the values it contains into *primes_table.

If get_prime is called with an argument larger than the number of primes already stored in primes_table, additional primes are added up to and including the one specified by the argument. If this occurs, primes.lbn, primes.lbn.gz, and primes.lsm are regenerated at the end of the run, if they already exist. If they don't already exist, they will be created. If they don't exist, and get_prime is never called, they won't be created.

Since 3DLDF uses threads, it's necessary to protect primes_table and the associated files using mutexes. It's also necessary to determine whether a system provides unsigned long long. If it doesn't, unsigned long or unsigned int is used instead. It is very unlikely that a system wouldn't provide unsigned long. In addition, it's necessary to check what functions are available for creating checksums, and whether gzip is available for compression.