Discrete Mathematics for Computer Science

Strong Form of Mathematical Induction 75

arithmetic of numbers up to approximately 300 digits. These chips essentially compute

powers this way, with one modification: FastPower, as written, makes a recursive call-it

invokes (another copy of) itself. To calculate 25, for example, the procedure was called

four times (the original call and three recursive calls). There is computer overhead in each

of these calls. It turns out that the special chips have had the recursive calls replaced with

a loop, producing the program actually used. Interested readers should try writing this

algorithm nonrecursively.

1.10.3 Application: Finding Factorizations

The Fundamental Theorem of Arithmetic was proved at the beginning of this section. As

important as the result is, however, it does not provide any insight regarding how one goes

about finding such a factorization. The two algorithms here explore factoring integers. The

first looks for the largest odd divisor. In a theorem we will prove later, the proof does

not provide a method for finding the largest odd divisor but, instead, uses the Fundamental

Theorem of Arithmetic to guarantee the existence of such a factor. When you actually want

to find the elements that the theorem only says will exist, you can use the first algorithm as

a method for doing this step of the proof. The second algorithm takes the guarantee of the

Fundamental Theorem of Arithmetic that a factorization exists and actually finds it. Later,

you will be asked to prove that these algorithms are correct. At this point it, however, is

important to understand what the algorithms are doing.

Largest Odd Divisor

A while loop controls the iterations in Largest Odd Divisor algorithm, because each it-

eration reduces the number being considered by a factor of 2 until only an odd number

remains.

INPUT: Integer value N > 0

OUTPUT: Largest odd divisor of N

LargeOdd (N)

while (Mod(N, 2) = 0)

N= N/2

print N

In this code, the condition mod(N, 2) = 0 returns TRUE when N is divisible by 2 (N
is even). The code returns FALSE when N is not divisible by 2 (N is odd). The first test of
the condition simply asks if the original number is odd. If the number is odd, it is certainly
the largest odd factor, and N is printed. If the condition is TRUE and N is even, then the
code controlled by the while loop divides N by a factor of 2. The resulting value (N/2)
is used in the condition the next time the while statement is executed. If the condition is
TRUE, the division by 2 is repeated. Eventually, the condition in the while statement with