Projects by Bradley Berg
White Papers
Climate Emergency Essential Links
A general purpose programming language and compiler
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.
-
Get the Preview Edition of the Gilda Compiler
Overview of the Gilda Programming Language
Design and Implementation of Iterative Loops
64 Bit Primality Test
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.
Collatz Conjecture
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 be incomplete. They may seem 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 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 so that no infinitely long run (requiring a bias towards odd values) cannot exist.
The Algebraic Expansion Of The Collatz Sequence is useful for analysis. A Python program, RunSeed.py, prints parameters for the equation: