The Gilda language is intended to make it easier and to build high quality software. This is achieved by addressing issues with portability, reuse, ease of use, software maintenance, reliability, testing, and debugging. The language integrates several innovations with a clean and simple syntax.
These primality tests extend Steve Worley's 32 bit primality test. They improve on Jim Sinclair's test that uses 7 SPRP tests. 32 bit numbers are checked with a single SPRP test, two are used for 49 bit numbers, and three for 64 bit numbers.
Numbers under 2^32 can be tested using the SPRP bases in: is.prime.32.base.data
Numbers from 2^32 to 2^64 can be tested using the base pairs in: is.prime.64.base.data
The is.prime.gg
Gilda function determines if any 64 bit number is prime.
The list.is.prime.32.g
program lists the bases used to test 32 bit numbers for primality.
It uses this sprp.gg implementation
of the Strong Probable Prime test.
The sprp test can be substantially sped up with negligible overhead by interleaving it with trial division over small primes. A modulus by a small prime is computed in each iteration of the loop for Base ^ D mod N.
Numbers with 49 or fewer bits fit in a floating point double. The modulus can be computed by multiplying by the reciprocal of small primes that are pre-computed and stored in an array. Division is avoided and processors can perform floating point operations in parallel with integer operations.
This Visual C code, sprp_two_trial_49.c, computes 2^E mod N and trial division for small primes.
Likewise numbers with 50 to 64 bits needs to use integer division. Arithmetic operations can still be issued in parallel with the divisions to reduce the overhead of trial division. The sprp_two_trial.c procedure illustrates this strategy.
Primality testing was 1.4 times faster for 32 bit numbers, 2.4 times faster for numbers with 33 to 49 bits, and 4.75 times faster for 50 to 64 bit numbers. Even though integrating trial division finds more numbers to be composite, it's not that many more. These procedures can also be used as the first stage of factorization routines to take advantage of the trial division results.
Please let me know if you can verify any of these algorithms or suggest improvements. If you revise the Visual C code to work with other compilers, pass them along to me and I'll merge it with the samples and post them. You can also visit this page for recent progress involving the Miller-Rabin primality test.
This paper looks at the Collatz Conjecture using analysis based on entropy.
A Windows program to print the revised Collatz series: collatz.exe
Design notes for a high fidelity low cost stereo system.
B. A. Berg, "Disentangling Exceptions", Brown University, December, 2008
Ahmad, Berg, Cetintemel, Humphrey, Hwang, Jhingran, Maskey, Papaemmanouil, Rasin, Tatbul, Xing, Zdonik, "Distributed Operation in the Borealis Stream Processing Engine", 2nd International Conference on Geosensor Networks, Boston, MA, October 2006
B. A. Berg, "A Distributed Catalog for the Borealis Stream Processing Engine", Brown University, May 31, 2006
Daniel V. Bailey, Bradley Berg, "Remote management interface using credentials associated with respective access control intervals", United States Patent: 9,455,977, September 27, 2016