:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: : method LIST.IS.PRIME.32: List SPRP bases for 32 bit primality testing. local Odd word, &32 bit odd numbers. Size word, &Number of composites in a bucket. Miss Bit, &Set if a composite failed an SPRP test. Log |= 8, &Number of buckets is 2^Log. Bound |= 2^Log - 1, &Upper bound of bucket range. Shift |= 32 - Log, &Number of bits to shift when hashing. Scale |= #ad625b89, &Multiplier for hashing. Max |= 9_999_999 :Big enough to hold all composites per bucket. global Bucket[ Max ] word :Composites in a single bucket. : :............................................................................... DO Hash = 0 to Bound: DO over buckets, Size = 0 Odd = 9; First odd composite. DO always: DO over 32 bit odd numbers, IF Hash = (Scale _* Odd) // Shift: IF an odd is in this bucket, IF Is.Prime.Worley( Odd ) = 0: IF composite (Worley's test), assert Size <= Max fault Hash; FAULT: A bucket overflowed. Bucket[ Size ] = Odd; Put composites in a bucket. Size += 1; Number of saved composites. . . UNDO IF Odd = #ffff_ffff; UNDO IF at the maximum odd value. Odd += 2 - DO Base = 3 to #ffff: DO over 16 bit bases, Miss = 0; Assume all composites are covered. DO I = 0 to Size - 1: DO over composites in this bucket, IF Sprp( Bucket[ I ], Base ): IF a psp, Miss = 1; A base did not fully cover. UNDO; UNDO on a failed base. - . : Skip any bases where a prime is in the bucket and: Base % Prime = 0 : This is not required, but ensures there is no ambiguity in these cases. : IF Miss = 0: IF all SPRP bases pass, DO Prime from Prime( word{3} ): DO over small primes, UNDO IF Base _< Prime; UNDO IF all primes are covered, IF Hash = (Scale _* Prime) // Shift: IF a prime in the bucket, IF Base % Prime = 0: IF a factor of the base, Miss = 1; Cannot use the base. PRINT ": skip base =", Base, &Comment when skipped. "with prime =", Prime, & "in the bucket." UNDO; UNDO when skipping. . - . . UNDO IF Miss = 0; UNDO IF a base covers the bucket. - assert Miss = 0 pass Hash; ERROR: No base found for a bucket. PRINT Base; List an SPRP base for the bucket. - return