This site is a static rendering of the Trac instance that was used by R7RS-WG1 for its work on R7RS-small (PDF), which was ratified in 2013. For more information, see Home. For a version of this page that may be more recent, see PrimesGauche in WG2's repo for R7RS-large.

Primes­Gauche

cowan
2016-07-31 02:38:11
4history
source

This SRFI provides utilities related to prime numbers.

Generating primes

primes

Returns a fresh SRFI 127 lazy sequence of primes. It is useful when you need primes for a short period of time — if you don’t keep a reference to the returned sequence, it will be garbage collected after you’re done with the primes. (Note that the calculation of a prime number needs the sequence of primes from the beginning, so even if your code only keeps a reference into the middle of the sequence, the entire sequence will be stored — you have to release all references in order to allow the sequence to be garbage collected.)

On the other hand, each sequence returned by primes is computed individually, duplicating computation.

The rule of thumb is: if you use primes repeatedly throughout the program, invoke primes and store its value in a global variable, and you’ll save computation. If you need primes just once, invoke primes at the point they are needed and abandon the result, and you’ll save space.

 
;; show 10 prime numbers from 100-th one.
(lseq-take (lseq-drop (primes) 100) 10)
 ⇒ (547 557 563 569 571 577 587 593 599 601)

Testing primality

small-prime? n

For positive integers less than small-prime-bound, this procedure determines if n is prime or not, quickly and deterministically. If n is greater than or equal to this bound, this procedure returns #f.

This can be used to quickly filter out known primes; it never returns #t on composite numbers, but it may return #f on sufficiently large prime numbers). The Miller-Rabin test below can tell if the input is definitely composite, but it may return #t on some composite numbers.

small-prime-bound [Variable]

For all positive integers below this value small-prime? can determine whether it is a prime or not.

miller-rabin-prime? n [ num-tests ]

Check if an exact integer n is a prime number, using the probabilistic Miller-Rabin algorithm, where n must be greater than 1. If this procedure returns #f, n is a composite number. If this procedure returns #t, n is likely a prime, but there’s a small probability that it is a false positive.

Note that if n is smaller than small-prime-bound, the algorithm is deterministic; if it returns #t, n is certainly a prime.

If n is greater than or equal to small-prime-bound, we use a probabilistic test. We choose a random base integer to perform the Miller-Rabin test up to num-tests (7 times by default). The probability of returning #t for a composite number is at most (expt 4 (- num-tests)).

bpsw-prime? n

Check if an exact integer n is a prime number, using (the Baillie-PSW primality test). It is deterministic, and is known to return a definitive answer for all numbers less than 264. For larger integers this can return #t on a composite number, although no such number has been found yet. This procedure never returns #f on a prime number.

This test is slower than Miller-Rabin but fast enough for casual use, so it is handy when you want a definitive answer below the above range.

Factorization

naive-factorize n [ divisor-limit ]

Factorize a positive integer n by trying to divide it into all primes up to (sqrt n). Returns a list of prime factors, smallest first.

 
(naive-factorize 142857)
  ⇒ (3 3 3 11 13 37)

Although this is a pretty naive method, this works well as long as any of n’s factors are not larger than about 107.

 
(naive-factorize 3644357367494986671013))
  ⇒ (10670053 10670053 32010157)

If n includes any larger prime factors, the performance becomes abysmal.

Alternatively, providing the divisor-limit argument specifies the upper bound of the prime number to be tried. If it is given, naive-factorize returns a factor f unchanged if it can’t be divided by any primes less than or equal to divisor-limit. So, the last element of the returned list may be a composite number. This is useful for excluding trivial factors before applying more sophisticated factorizing algorithms.

 
(naive-factorize 825877877739 1000)
  ⇒ (3 43 6402154091)

;; whereas
(naive-factorize 825877877739)
  ⇒ (3 43 4591 1394501)

The procedure also memoizes the results on smaller values of n to make things faster.

mc-factorize n

Factorize a positive integer n using the algorithm described in R. P. Brent, An improved Monte Carlo factorization algorithm, BIT 20 (1980), 176-184.

This one is capable of handling much larger factors than naive-factorize, somewhere around 1020 or so.

Since this method is probabilistic, the execution time may vary on the same n. But it will always return the definitive results as long as every prime factor of n is smaller than an implementation-specified limit. If n contains a prime factor greater than the limit, the procedure may loop forever.

Miscellaneous

jacobi a n

Calculates the Jacobi symbol (a/n).

totient n

Euler’s totient function of the nonnegative integer n.

The current implementation relies on mc-factorize above, so it may take a very long time if n contains large prime factors.