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.
The Collatz sequence is chaotic and cannot be resolved using conventional algebra. Consequently proof strategies attempting to cover all possible values in sequence runs will not work. They often appear to cover all values, but there are always some cases that are overlooked. Terence Tao's important paper generalizes this phenomenon and reduces the bounds to minuscule limits.
There are two different problems to consider here - a linear sequence problem and a circular sequence problem. Instead of looking for patterns in the values produced by the sequence, these papers analyze the underlying mechanics of the sequence. For anyone interested in the topic they give the reader insight into the workings of these two problems and lay out compelling strategies that address both.
After this talk in the Q&A Terence Tao said about the linear problem, "If you get to randomize N every time you pass through this [region] it becomes like this [linear downward] drift." He also limited his paper to the linear problem saying, "The only way to disprove it is to produce a cycle."
This first paper uses Shannon entropy to analyze the linear problem for the Collatz Conjecture. For a pseudo random number generator to be unbiased it must use operations that generate values with an equal distribution of zero and one bits. The sequence does just that, however, an infinitely long run requires values biased towards one so it cannot be generated.
The second paper addresses the circular problem for the Collatz Conjecture by deriving bounds on the sequence. One set of bounds show that the starting seed value has to be relatively large to form a loop of a given length. Another contradictory set of bounds show that the seed is limited to much smaller values.
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