Programming Praxis

Sometimes you need to have a large prime, for testing, cryptography, or some other purpose. I’m talking about primes of several hundred to a few thousand digits that are certified — proven to be prime — rather than probable primes according to a Miller-Rabin or other probabilistic test. Henry Pocklington’s Criterion, which dates to 1914, gives us a way to find such primes quickly. Paulo Ribenboim explains it thus:

Let p be an odd prime, and let k be a positive integer, such that p does not divide k and 1 < k < 2(p + 1). Let N = 2kp + 1. Then the following conditions are equivalent:

1. N is a prime.
2. There exists an integer a, 1 < a < N, such that a^(N−1)/2 ≡ −1 (mod N) and gcd(a^k + 1, N) = 1.

This gives us an algorithm for generating large certified primes. Choose p a certified prime. Choose 1 ≤ k < 2 × p at random; we ignore the last two possibilities for k, so we don’t have to worry about k being a multiple of p. Compute N. For each a ∈ {2, 3}, test the conditions for primality. If you don’t find a prime, go back and choose a different random k. Once you have a prime N, “ratchet up” and restart the process with the new certified prime N as the p of the next step. Continue until N is big enough.

Your task is to write a program that generates random large primes. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

We have looked at random number generators in several previous exercises, but most of them returned integers. In today’s exercise we look at a simple random number generator that returns floating-point numbers. The generator is simple: Given a seed between zero and one, the next number in the sequence is the fractional portion of 147 times the seed.

Your task is to implement the random number generator described above, and to assess its suitability. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

One of the original motivations for the Lisp language was to write a program that performed symbolic differentiation. In this exercise we look at the symbolic differentiator in Section 2.3.2 of SICP, which handles expressions containing only addition and multiplication according to the following rules:

, with ,

,

, and

.

Your task is to write a program that performs symbolic differentiation according to the rules given above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

I completed the solution to the previous exercise, which you can look at if you wish. We’ll have a new exercise on Friday.

Today’s exercise is an interview question;

Given a list of words and a set of characters, determine which words in the list can be formed from the given characters. For instance, given the characters a, c and t, the words act and cat can be formed, but not the word stop.

Your task is to write the word classified described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Cannonballs are traditionally stacked in a pyramid with a square base. A stack with a square base of 15 cannonballs has 15 × 15 = 225 on the bottom level, 14 × 14 = 196 on the level above that, and so on, a total of 1240 cannonballs.

Your task is to write a program to compute the number of cannonballs in a stack; use it to compute the number of cannonballs in a stack with a base of 1,000,000 cannonballs on a side. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

In a recent exercise we wrote a program to determine if a binary tree was balanced. Today’s exercise is similar:

Write a program to determine if a binary tree satisfies the binary search tree property that all left children are less than their parent and all right children are greater than their parent.

Your task is to write a program to determine if a binary tree is a binary search tree. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

We examined the Solitaire Cipher of Bruce Schneier in a previous exercise. In an article on his blog, Ted Unangst complains that the cipher is too complicated for manual use, and proposes instead RC40, a variant of RC4 that uses only 40 characters instead of 256. Unangst’s alphabet is the 26 lower-case letters, the ten digits 0 through 9, the characters period, question mark, and space, and a “shift” character that gives an upper-case version of those 39 characters; two consecutive shift characters enter or leave caps-lock mode. Otherwise, RC40 is exactly the same as RC4, except that all references to 256 are changed to 40.

Your task is to write a program that enciphers and deciphers strings based on the RC40 cipher; use that program to decipher the string “5cxaxlfrfhy6kh38fbplm0mDko58xs.l9Hkz8” with key “tedunangst”. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

The story exploded across the intertubes a few days ago: A software engineer trying to enter the United States on a work visa was asked to prove his occupation by writing a program for the Customs and Border Protection agent:

Write a function to check if a Binary Search Tree is balanced.

Let’s help him.

Your task is to write a function to check if a binary search tree is balanced. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2