Programming Praxis

Today’s exercise is a delightful little programming puzzle:

Write a function f so that f(f(n)) = -n for all integers n.

When I first saw this puzzle, it took me two days before I had the necessary flash of inspiration, then about two minutes to write. Do yourself a favor and don’t peek at the suggested solution until you figure it out yourself.

Your task is to write function f as 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

We have today another from our never-ending list of interview questions:

Given a linked list, swap the kth node from the head of the list with the kth node from the end of the list.

Your task is to write a function to perform the indicated task; be sure to test it thoroughly. 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 studied the basic quadratic sieve algorithm for factoring integers in two previous exercises. Today we examine the multiple polynomial variant of the quadratic sieve, due to Peter Montgomery, which adds considerable power to the basic algorithm; we will be following Figure 2.2 and the surrounding text from Scott Contini’s thesis.

In the basic quadratic sieve we used a polynomial of the form g(x) = (x + b)² – n where b = ⌈√n⌉. The problem with using a single polynomial is that the values of g(x) increase as x increases, making them less likely to be smooth. Eventually, the algorithm “runs out of gas” when the values of g(x) grow too large.

Montgomery’s suggestion was to use multiple polynomials of the form g_{a, b}(x) = (a x + b)² − n with a, b integers with 0 < b ≤ a. The graph of g_{a, b}(x) is a parabola, and its values will be smallest when a ≈ √(2n) / m. Thus, we choose b so that b² − n is divisible by a, say b² − n = a c for some integer c, and a = q² for some integer q. Then we calculate g_{a, b}(x) / a = a x² + 2 b x + c, and, after sieving over the range −m .. m, when g_{a, b}(x) is smooth over the factor base we record the relation ((a x + b) q⁻¹)² = a x² + 2 b x + c.

Here is our version of Contini’s algorithm:

Compute startup data: Choose f, the upper bound for factor base primes, and m, which is half the size of the sieve. Determine the factor base primes p < f such that the jacobi symbol (n/p) is 1 indicating that there is a solution to t² ≡ n (mod p); also include 2 in the factor base. For each factor base prime p, compute and store t, a modular square root of n (mod p). Also compute and store the base-2 logarithm of each prime l = ⌊log₂ p⌉ (the floor and ceiling brackets indicate rounding).

Initialize a new polynomial: Find a prime q ≈ √( √(2n) / m) such that the jacobi symbol (n/q) is 1, indicating that n is a quadratic residue mod q, and let a = q² (mod n). Compute b, a modular square root of n mod a; you will have to compute the square root of n mod q then “lift” the root mod q² using Hensel’s Lemma. For each odd prime p in the factor base, compute soln1_p = a⁻¹ (tmem_p − b) and soln2_p = a⁻¹ (−tmem_p − b).

Perform sieving: Initialize a sieve array of length 2 m + 1 to zeros, with indices from −m to m. For each odd prime p in the factor base, add l_p to the locations soln1_p + i p for all integers i that satisfy −m ≤ soln1_p + i p ≤ m, and likewise for soln2_p. For the prime p = 2, sieve only with soln1_p.

Trial division: Scan sieve array for locations x that have accumulated a value of a least log(m √n) minus a small error term. Trial divide g_{a, b}(x) by the primes in the factor base. If g_{a, b}(x) factors into primes less than f, then save smooth relation as indicated above. After scanning entire sieve array, if there are more smooth relations than primes in the factor base, then go to linear algebra step. Otherwise, go to initialization step to select a new polynomial.

Linear algebra: Solve the matrix as in Dixon’s method and the continued fraction method. For each null vector, construct relation of form x² ≡ y² (mod n) and attempt to factor n by computing gcd(x − y, n). If all null vectors fail to give a non-trivial factorization, go to initialization step to select a new polynomial.

Your task is to write a program to factor integers using the multiple polynomial quadratic sieve as 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 3

Today’s exercise is a classic problem of computer science: given an array of positive and negative integers, find three that sum to zero, or indicate that no such triple exists. This is similar to the subset sum problem, which we solved in a previous exercise, but simpler because of the limit to three items. A brute force solution that operates in O(n³) time uses three nested loops to select items from the array and test their sum, but an O(n²) solution exists. For instance, in the array [8, -25, 4, 10, -10, -7, 2, -3], the numbers -10, 2 and 8 sum to zero, as do the numbers -7, -3, and 10.

Your task is to write a program that solves the 3SUM problem in O(n²) time. 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 ratio of the circumference to the diameter of a circle, known as π, is constant regardless of the size of the circle; that fact has been known to mathematicians for about five thousand years; much of the history of mathematics is intertwined in the history of πi, as approximations of the ratio have improved over time. Much of the history of this blog is also intertwined in the calculation of π; one of the original ten exercises used a bounded spigot algorithm of Jeremy Gibbons to calculate π, and later we used an unbounded spigot algorithm also due to Gibbons; we studied the ancient approximation of 355/113 calculated by Archimedes; we studied two different Monte Carlo simulations of π; and we even had the Brent-Salamin approximation contributed by a reader in a comment.

The development of computers allows us to compute the digits of π to an astonishing accuracy; the current record, unless somebody has bettered it recently, is ten trillion digits. That record was set by the Chudnovsky brothers, two Russian mathematicians living in New York, using an algorithm they developed in 1987. The algorithm is based on a definition of π developed by Ramanujan, and is beautifully described by the two brothers.

Your task is to compute many digits of π using the Chudnovsky algorithm. 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

Today’s exercise comes from our unending list of interview questions:

Find the longest run of consecutive characters in a string that contains only two unique characters; if there is a tie, return the rightmost. For instance, given input string abcabcabcbcbc, the longest run of two characters is the 6-character run of bcbcbc that ends the string.

Your task is to write the requested program. 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

Sets are ubiquitous in programming; we’ve used sets in several of our exercises. In most cases we made the sets from lists, which is good enough when the sets are small but quickly slows down when the sets get large. In today’s exercise we will write a generic library for sets.

The sets that we will consider are collections of items without duplicates. We will provide an adjoin function to add an item to a set if it is not already present and a delete function to remove an item from a set if it is present. A member function determines if a particular item is present in a set. The three set operations that are provided are intersection, union and difference; we will consider that the universe from which items are drawn is infinite, or at least too large to conveniently enumerate, so we will not provide a complement operation. For convenience, we will also provide functions to calculate the cardinality of a set and to create a list from the items present in the set.

Your task is to write a library for handling sets, based on the description 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

One topic that has always fascinated me is the mathematical sophistication of the ancients. The Pythagorean theorem is twenty-five hundred years old. Euclid’s Elements of 300BC remained in use as a geometry textbook for over two millenia, and is still in print today (you can buy the Dover edition for $1). Eratosthenes was sieving prime numbers two centuries before Christ.

Today’s topic is Egyptian fractions, which were mentioned in the Rhind Papyrus of 500BC as an “ancient method” and are thought to date to the time of the pyramids; they survived in use until the 17th or 18th century. Leonardo de Pisa’s famous book Liber Abaci of 1215AD, which introduced to European mathematicians the concept of zero, the Hindu-Arabic system of numeration, and the famous rabbit sequence (Leonardo’s nickname was Fibonacci).

An Egyptian fraction was written as a sum of unit fractions, meaning the numerator is always 1; further, no two denominators can be the same. As easy way to create an Egyptian fraction is to repeatedly take the largest unit fraction that will fit, subtract to find what remains, and repeat until the remainder is a unit fraction. For instance, 7 divided by 15 is less than 1/2 but more than 1/3, so the first unit fraction is 1/3 and the first remainder is 2/15. Then 2/15 is less than 1/7 but more than 1/8, so the second unit fraction is 1/8 and the second remainder is 1/120. That’s in unit form, so we are finished: 7 ÷ 15 = 1/3 + 1/8 + 1/120. There are other algorithms for finding Egyptian fractions, but there is no algorithm that guarantees a maximum number of terms or a minimum largest denominator; for instance, the greedy algorithm leads to 5 ÷ 121 = 1/25 + 1/757 + 1/763309 + 1/873960180913 + 1/1527612795642093418846225, but a simpler rendering of the same number is 1/33 + 1/121 + 1/363.

Your task is to write a program that calculates the ratio of two numbers as an Egyptian fraction. 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

Our exercise today studies a famous problem solved by the great Swiss mathematician Leonhard Euler in 1735, which marked the beginning of what is now the “graph theory” branch of mathematics. Euler proved that it was impossible to cross all seven bridges once without retracing your path. He proved that a complete circuit, returning to the starting point, is possible only if all vertices connect to an even number of neighbors, and a complete path that doesn’t return to the starting point is possible if exactly two of the vertices have an odd number of neighbors, the rest being even, in which case the two odd-count vertices are the starting and ending points of the path.

The following algorithm to determine a eulerian path in a graph, if it exists, is ancient; I would be happy if anybody can provide a pointer to the source of the algorithm:

1) If a complete circuit is possible, choose any vertex at random as the current vertex. If a complete path but not a circuit is possible, choose either of the two odd-degree vertices at random. Otherwise, quit.

2a) If the current vertex has neighbors, add it to the stack, choose any of its neighbors as the new current vertex, and remove the edge between the two vertices.

2b) If the current vertex has no neighbors, add it to the path, remove the last vertex from the stack and make it the current vertex.

3) Repeat step 2 until the current vertex has no neighbors and the stack is empty.

4) Add the current vertex to the path and quit.

Your task is to write programs that determine if a graph is an eulerian circuit or eulerian path and, if it is, determine the path. 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 discussed modular arithmetic in a previous exercise. In a comment on that exercise, Matthew asked what you can do when you have a fixed size integer datatype (say 64-bit unsigned integers) and a modulus that is close to the maximum. That’s a good question, which we will answer today. The answer is straight forward if the modulus is at least one bit less than the maximum, and rather trickier if it’s not. We’ll look at multiplication, but the other operations are all similar.

As long as the modulus is at least one bit less than the maximum, the solution is to split the numbers in low-bit and high-bit halves, then perform the arithmetic piecemeal, kind of like grade-school multiplication where you multiply by the one’s digit, then shift the sum and multiply by the ten’s digit, and so on, except that the “digits” are the size of the square root of the maximum number than can be represented in the integer datatype.

If m is within one bit of the maximum for the integer data type, things get messier; the basic answer is to split into three parts, compute the intermediate products, and recombine. But we won’t bother with that.

Your task is to write a function that performs modular multiplication without overflow. 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