Saturday, December 26, 2009

Math visualization: (x + 1)2

You may remember this from high-school algebra (or perhaps earlier for some). Expand (x + 1)2 using the FOIL method.

(x + 1)2 = (x + 1)(x + 1)
= x2 + x + x + 1
= x2 + 2x + 1

A neat way to visualize this equality, and hopefully help remember the factorization of the resulting polynomial, is to look at how the pieces fit together.

When they're arranged in this way, it's easy to see that the pieces squeeze together to form a larger square that has a length of (x + 1) on a side, proving the equality.

Related posts:

Six Visual Proofs
Multiplying Two Binomials

Thursday, December 24, 2009

SICP Exercise 1.15: Calculating sines

From SICP section 1.2.3 Orders of Growth

Exercise 1.15 shows an interesting procedure for computing the sine of an angle (in radians) by combined use of the approximation sin x ~ x (if x is sufficiently small) and the trigonometric identity

sin r = 3 * sin(r/3) - 4 * sin3(r/3)

which is used to reduce the argument of sin. The code provided implements the computation:
(define (cube x) (* x x x))(define (p x) (- (* 3 x) (* 4 (cube x))))(define (sine angle)   (if (not (> (abs angle) 0.1))       angle       (p (sine (/ angle 3.0)))))

The exercise goes on to ask the following two questions:

a. How many times is the procedure p applied when (sine 12.15) is evaluated?

b. What is the order of growth in space and number of steps (as a function of a) used by the process generated by the sine procedure when (sine a) is evaluated?

Looking at how the process executes will help us answer both questions.
(sine 12.15)(p (sine 4.05))(p (p (sine 1.35)))(p (p (p (sine 0.45))))(p (p (p (p (sine 0.15)))))(p (p (p (p (p (sine 0.05))))))(p (p (p (p (p 0.05)))))(p (p (p (p 0.1495))))(p (p (p 0.4351345505)))(p (p 0.9758465331678772))(p -0.7895631144708228)-0.39980345741334

As long as the angle stays greater than 0.1, the process keeps recursing. There are five calls to the procedure p before that happens.

Complexity

The sine procedure is recursive, but it makes only a single call to itself, so it isn't tree recursive and its complexity isn't nearly as bad as some of the procedures we've seen in previous exercises. The complexity for this procedure in both space and number of steps is actually better than linear.

Space - The amount of space required by this procedure would increase linearly as the input size is tripled. Only the calls to procedure p are deferred, and we can triple the size of the input before an additional call would be made.

Number of steps - It's also easy to see that we can triple the value of the starting input angle and only one more step would be required by this procedure.

The complexity of both the space and the number of steps required by this procedure can be described as O(log n).

Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.

Tuesday, December 22, 2009

SICP Exercise 1.14: Counting change

From SICP section 1.2.3 Orders of Growth

Exercise 1.14 asks us to draw the tree illustrating the process generated by the count-change procedure presented in section 1.2.2 in making change for 11 cents.
(define (count-change amount)   (cc amount 5))(define (cc amount kinds-of-coins)   (cond ((= amount 0) 1)         ((or (< amount 0) (= kinds-of-coins 0)) 0)         (else (+ (cc amount                      (- kinds-of-coins 1))                  (cc (- amount                         (first-denomination kinds-of-coins))                      kinds-of-coins)))))(define (first-denomination kinds-of-coins)   (cond ((= kinds-of-coins 1) 1)         ((= kinds-of-coins 2) 5)         ((= kinds-of-coins 3) 10)         ((= kinds-of-coins 4) 25)         ((= kinds-of-coins 5) 50)))

Running the code with the specified input shows us how many ways there are to make change for 11 cents with five coins.
> (count-change 11)4>

A quick scan of the code shows that the cc procedure contains two recursive calls to itself, resulting in the tree-shaped process structure mentioned in the question. Leaf nodes of the tree are reached when the base cases are met, that is when the amount is less than or equal to zero, or when the kinds of coins remaining reaches zero.

When a node splits, its left-hand child is passed the same amount and one fewer kinds of coins. The right-hand child is passed an amount that is reduced by the highest-denomination coin available to its parent node, and the same number of kinds of coins. (Click the images enlarge.)

I've color-coded the nodes of the tree. White nodes are those leaf nodes that evaluate to 0, blue nodes are those leaf nodes that evaluate to 1 and contribute to the final answer. The yellow nodes are those that branch recursively.

Orders of growth

The exercise also asks us to find the orders of growth of the space and number of steps used by the count-change process as the amount to be changed increases. (Note that we are not really concerned with the orders of growth as the number of kinds of coins grows, only the amount to be changed.)

Space - As we saw in the Fibonacci procedure in section 1.2.2, the space required by the count-change procedure grows linearly with the input. The space required is proportional to the maximum depth of the tree. At any point in the computation we only need to keep track of the nodes above the current node.

Since the height of the tree is proportional to the amount to be changed, the order of growth of the space required by the count-change procedure is O(n).

Number of steps - The diagram illustrates that this procedure, much like the recursive procedure for computing Fibonacci numbers that we saw before, in not very efficient. Much of the computation being done is repeated.

If we look closely at a call to cc where kinds-of-coins is equal to one, we can see each call generates two more calls until we reach a terminal node.

If we define the function T(a, k) to be the number of calls to cc generated by calling (cc n k), where n is the amount and k is the number of kinds of coins, then

T(n, 1) = 2n + 1

or in Big-O notation,

T(n, 1) = O(n)

Now let's take a look at a partial graph of a call to (cc 50 2).

There are two interesting things to point out here. First, there are n/5 calls to cc made where k = 2 kinds of coins (look down the right hand side of the diagram above). This is because each call is made with 5 cents less in the amount argument until a terminal node is reached. The second interesting thing is that each of these n/5 calls to (cc n 2) generates an entire (cc n 1) subtree.

That means that

T(n, 2) = (n/5) * 2n + 1

and because of the multiplication of terms

T(n, 2) = O(n2)

Similarly, if we look at the graph of (cc 50 3) we can see n/10 calls to cc where k = 3, each of which generates its own (cc n 2) subtree.

From this we find that

T(n, 3) = O(n3)

Finally, it's easy enough to show that we'll get the same pattern when k = 4 and k = 5. The n/50 nodes generated when k = 5 each generate n/25 nodes with k = 4, each of which generates a node where k = 3.

And so the final answer we arrive at for the time complexity of the count-change procedure with five kinds of coins is

T(n, 5) = O(n5)

Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.

Friday, December 11, 2009

Unsolved: Goldbach conjecture

The Goldbach conjecture is one of the oldest and easiest-to-understand math problems that remains unsolved. The problem was originally posed to Leonhard Euler in a letter from amateur mathematician Christian Goldbach in 1742. The original form of the conjecture, now known as the weak Goldbach conjecture says:
Every whole number greater than five is the sum of three prime numbers.

Euler restated the problem in an equivalent form, the strong Goldbach conjecture (or just the Goldbach conjecture):
Every even number greater than two is the sum of two primes.

So,
4 = 2 + 2
6 = 3 + 3
8 = 3 + 5
10 = 5 + 5
12 = 5 + 7
...
100 = 47 + 53
...

Progress

In 1966, Chinese mathematician Chén Jǐngrùn showed that every sufficiently large even integer is the sum of a prime and semiprime (a number that has at most two prime factors).

Brute force methods have been used to show that the Goldbach conjecture is true for even integers up to about 1.5 * 1018* (1,500,000,000,000,000,000 or 1.5 billion billion).

Notes:

* Brute force results are as of July 24, 2009. See Goldbach conjecture verification for up-to-date results.

Wednesday, December 9, 2009

SICP Exercise 1.13: Fibonacci and the Golden ratio

From SICP section 1.2.2 Tree Recursion

Exercise 1.13 asks us to prove that Fib(n) is the closest integer to φn/√5, where

φ = (1 + √5)/2.

The exercise also gives us the following hint:
Let ψ = (1 - √5)/2. Use induction and the definition of Fibonacci numbers to prove that

Fib(n) = (φn - ψn) / √5

Some may recognize that this question is closely related to the closed form expression for Fibonacci numbers, also known as Binet's formula.

You may also recognize the quantity (1 + √5)/2, denoted by the Greek letter φ (phi), as the Golden ratio.

This mathematical constant has many interesting properties, a couple of which will be useful in our proof.
φ2 = φ + 1
1/φ + 1 = φ

The second constant introduced in the hint (1 - √5)/2, denoted by the Greek letter ψ (psi), shares the same properties.

ψ2 = ψ + 1
1/ψ + 1 = ψ

Before tackling the problem, let's take a look at the sequences in question to try and get a feel for what we're trying to prove. It's safe to assume that everyone is familiar with the Fibonacci sequence:

0, 1, 1, 2, 3, 5, 8, 13, 21, ...

Each number is the sum of the preceding two.

We can use the following procedures to quantify φn/√5 for several values of n.
(define phi   (/ (+ 1 (sqrt 5)) 2))(define (^ base exponent)   (define (*^ exponent acc)       (if (= exponent 0)           acc           (*^ (- exponent 1) (* acc base))))   (*^ exponent 1))(define (f n)   (/ (^ phi n) (sqrt 5)))

The following output shows that this function does track closely with the Fibonacci sequence.
> (f 0)0.4472135954999579> (f 1)0.7236067977499789> (f 2)1.1708203932499368> (f 3)1.8944271909999157> (f 4)3.0652475842498528> (f 5)4.959674775249769> (f 6)8.024922359499621> (f 7)12.984597134749391> (f 8)21.009519494249012

Each term is within 1/2 of the corresponding term of Fib(n), which is what we're asked to prove. This is only a small amount of empirical evidence, though, which is a far cry from proof. It does show that what we're asked to prove is at least reasonable, though. (It's always a good idea to show that an assertion is at least reasonable before you go about trying to prove it.)

The inductive proof

As the hint recommends, let's start by proving inductively that

Fib(n) = (φn - ψn) / √5

For the base cases we'll show that the left-hand side of the equation above is equal to the right-hand side for n = 0, n = 1, and n = 2.

On the Left-hand side we have:

Fib(0) = 0
Fib(1) = 1
Fib(2) = Fib(1) + Fib(0)
= 1 + 0
= 1

On the Right-hand side we have:

for n = 0
n - ψn) / √5 = (φ0 - ψ0) / √5
= (1 - 1) / √5
= 0 / √5
= 0

for n = 1
n - ψn) / √5 = (φ1 - ψ1) / √5
= ((1 + √5)/2) - ((1 - √5)/2) / √5
= (1/2 + √5/2) - (1/2 - √5/2) / √5
= (1/2 + √5/2 - 1/2 + √5/2) / √5
= (√5/2 + √5/2) / √5
= (2 * √5/2) / √5
= √5 / √5
= 1

for n = 2
n - ψn) / √5 = (φ2 - ψ2) / √5
= ((φ + 1) - (ψ + 1)) / √5
= (((1 + √5)/2 + 1) - ((1 - √5)/2 + 1)) / √5
= ((1 + √5)/2 + 1 - (1 - √5)/2 - 1) / √5
= ((1 + √5)/2 - (1 - √5)/2) / √5
= ((1 + √5) - (1 - √5)) / 2 / √5
= (1 + √5 - 1 + √5) / 2 / √5
= (√5 + √5) / 2 / √5
= (2 * √5) / 2 / √5
= √5 / √5
= 1

So far, so good. Now for the inductive step. If we assume that both of the following are true:

Fib(n) = (φn - ψn) / √5
Fib(n-1) = (φn-1 - ψn-1) / √5

Fib(n+1) = (φn+1 - ψn+1) / √5

is true also? Let's find out!

We'll start from the defining recurrence relation of the Fibonacci sequence and see if the two assumptions above can lead us to the correct conclusion. Remember that we also have the properties of φ and ψ that were introduced at the beginning at our disposal.

Fib(n+1) = Fib(n) + Fib(n-1)
= (φn - ψn) / √5 + (φn-1 - ψn-1) / √5
= ((φn - ψn) + (φn-1 - ψn-1)) / √5
= (φn - ψn + φn-1 - ψn-1) / √5
= (φn + φn-1 - ψn - ψn-1) / √5
= ((φn + φn-1) - (ψn + ψn-1)) / √5
= (φn+1 * (φ-1 + φ-2) - ψn+1 * (ψ-1 + ψ-2)) / √5
= (φn+1 * φ-1 * (1 + φ-1) - ψn+1 * ψ-1 * (1 + ψ-1)) / √5
= (φn+1 * 1/φ * (1 + 1/φ) - ψn+1 * 1/ψ * (1 + 1/ψ)) / √5
= (φn+1 * 1/φ * (φ) - ψn+1 * 1/ψ * (ψ)) / √5
= n+1 - ψn+1) / √5

In the 10th step of the transformation above I used the following properties of φ and ψ to do substitutions:

1/φ + 1 = φ
1/ψ + 1 = ψ

This concludes the inductive proof from the hint, but where does that leave us? How does that help us prove that Fib(n) is the closest integer to φn/√5?

Let's rearrange the equation just a bit before continuing on.

Fib(n) = (φn - ψn) / √5
Fib(n) = φn/√5 - ψn/√5
Fib(n) - φn/√5 = ψn/√5

I did this bit of manipulation because we're trying to prove something about the relationship between Fib(n) and φn/√5. Specifically, we're trying to prove that the difference between them is always less than 1/2. In its current form, all that we have left to prove is that

ψn/√5 ≤ 1/2
or
ψn ≤ √5/2

Since ψ is defined to be (1 - √5)/2, we can simply evaluate it to find that

ψ = -0.618304...

Since the n in Fib(n) is always going to be an integer and

n ≥ 0

will always be true, and
ψ < 1

we know that
ψn ≤ 1

for all non-negative integer values of n.

We can also simply evaluate √5/2.

√5/2 = 1.118...

Since
ψn ≤ 1
and
√5/2 > 1

it's pretty clear that

ψn ≤ √5/2

and therefore

Fib(n) is the closest integer to φn/√5.

QED

Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.