Toluu

Programming Praxis

A collection of etudes, updated weekly, for the education and enjoyment of the savvy programmer

Numerical IntegrationToday

Computing the definite integral of a function is fundamental to many computations. In many cases, the integral of a function can be determined symbolically and the definite integral computed directly. Another approach, which we shall examine in today’s exercise, is to compute the definite integral numerically, an operation that numerical analysts call quadrature. We will consider a function f for which we are to find the definite integral over the range a to b, with a < b.

Recall from your study of calculus that the definite integral is the area under a curve. If we slice the curve into hundreds or thousands or millions of vertical strips, we can approximate the area under the curve by summing the areas of the individual strips, assuming that each is a rectangle with height equal to the value of the curve at the midpoint of the strip; this is, obviously, the rectangular method of quadrature. The trapezoidal method is similar, but uses the average of the value of the curve at the two ends of the strip; the strip then forms a trapezoid with parallel sides, a flat bottom on the horizontal axis, and a slanted top that follows the curve. A final method, called Simpson’s method, fits a parabola to the top of the strip by taking the height of the curve as its value at the left side of the strip plus its value at the right sid

Segmented Sieve Of EratosthenesFebruary 5

We examined the Sieve of Eratosthenes for computing prime numbers less than n in our second exercise nearly a year ago. In today’s exercise, we update that algorithm to compute the prime numbers in a range L to R, where the range doesn’t start at zero and is too large to fit in memory all at once. Specifically, we discuss a function that takes parameters L, for the left end of the range, and R, for the right end of the range, and a parameter B that divides R – L; we also assume that the primes less than the square root of R are known. In practice, L and R will be large, maybe 1016 or 1018, and B will be somewhat smaller, maybe 108 or 1010.

We will explain the algorithm by computing the primes in the range 100 to 200, with B = 10; since we don’t look at even numbers, the algorithm will make five passes, each time sieving twenty numbers.

There are six primes less than the square root of 200: 2, 3, 5, 7, 11, and 13; we will ignore 2, since it is even. Associated with each prime Pk is a number we will call Qk that is the offset within B of the first prime in the current sieving block that is divisible by Pk. For instance, when sieving from 100 to 120, the primes are 3, 5, 7, 11, and 13 and the associated Qs are 2, 2, 2, 10, and 8. Each Qk can be initialized by computing Qk = (-1/2 × (L + 1 + Pk)) mod Pk and re-initialized for the next 2B block by computing Qk = (Qk �

Proving PrimalityFebruary 2

We examined algorithms for checking the primality of a number in two previous exercises. Both algorithms are probabilistic; the Rabin-Miller algorithm has known false positives, and Carl Pomerance proved that the Baillie-Wagstaff algorithm has an infinite number of false positives, even though none are known.

Today’s exercise describes an algorithm for proving that a number is prime, not probably but certainly. The algorithm works by a theorem of Edouard Lucas, which is based on Fermat’s Little Theorem (if n is prime then bn-1 ≡ 1 (mod n) for every integer b coprime to n):

If, for some integer b, bn-1 ≡ 1 (mod n), and if b(n-1)/q ≢ 1 (mod n) for any prime divisor q of n-1, then n is a prime number.

Thus, if the factors of n-1 are known, it is easy to determine the primality of n.

Your task is to write a function that determines the primality of an integer using Lucas’ primality test; use it to prove the primality of 289-1. When you are finished, you are welcome to read or run a suggested solution , or to pos

Straddling CheckerboardJanuary 29

We examined the bifid cipher, which uses a polybius square to convert letters to digits and back again, in a previous exercise. Today we will look at another tool for converting between letters and digits known as a straddling checkerboard. A sample straddling checkerboard, based on the key SHARPEN YOUR SAW with spaces at 2, 5, and 9, is shown below (the three underscores in the first row make the space character visible):

  0 1 2 3 4 5 6 7 8 9
  S H _ 8 A _ 1 R P _
2 E 5 N * Y O U W B 2
5 C 3 D 4 F 6 G 7 I 9
9 J 0 K L M Q T V X Z

The checkerboard has four rows and ten columns. Three of the positions in the first row are spaces, leaving twenty-six letters, ten digits, and an asterisk to represent the space character. The row numbers correspond to the positions of the three first-row spaces. Our method is traditional: the pass phrase followed by the alphabet, with duplicates removed and digits paired with the first ten letters of the alphabet (A=1, B=2, …, J=0). But any other method of filling out the key may be used.

To use the checkerboard, simply write one digit for letters that appear in the first row and two digits for letters in the subsequent rows, row digit first then column digit. For instance, the plain-text PROGRAMMING PRAXIS is converted to digits like this:

P R O   G   R A M   M   I   N   G   *   P R A

Primality Checking, RevisitedJanuary 26

We examined the Miller-Rabin probabilistic primality checker in a previous exercise. Today, we examine a primality checker that combines the Miller-Rabin test with a test on Lucas pseudoprimes, devised by Robert Baillie and described by Baillie and Wagstaff in their article “Lucas Pseudoprimes” in Mathematics of Computation, Volume 35, Number 152, pages 1391-1417, October 1980; see also Thomas Nicely’s web page devoted to Baillie’s test. This is the same algorithm used in the PrimeQ function in Mathematica.

Lucas numbers are defined by a recurrence formula similar to Fibonacci numbers, where with and ; the Lucas numbers are 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, … (Sloane’s