9.1   A Comparison

We begin here by recalling that the function phi(n) counts the number of integers m such that 1 <= m <= n and gcd(m, n) = 1. In the Prelab section of this chapter, you computed phi(n) for a few different values of n by systematically checking each m such that 1 <= m <= n, and counting how many satisfied gcd(m, n) = 1. Clicking on "First phi" in the applet below will automatically do the same thing. Try it out; click on "First phi" to evaluate phi(20).

Your browser does not support java.

The output tells us that phi(20) = 8. It also tells you how long it takes to perform the computation. Let's try out "First phi" on a larger number:

Your browser does not support java.

This one takes a bit longer, which shouldn't be surprising, because there are more values of m to check. The applet has a second built-in function called "Fast phi" that also computes phi(n), but does so using a method different from "First phi". Try out both "First phi" and "Fast phi" below to compare the computation times.

Your browser does not support java.

Clearly "Fast phi" is faster than "First phi". (Could we possibly expect a function called "Fast phi" to be slower?) The reason is that "Fast phi" uses an algorithm that is more efficient than the one used in "First phi". One goal for this chapter is to find this more efficient method for computing phi(n).

Exercise 1

(a) Use the applet to determine the time required to compute phi(104) using "First phi".
(b) On the basis of the results of part (a), extrapolate the number of years required for "First phi" to compute phi(1020). (For simplicity, assume that all years have 365 days.)
(c) Use the applet to determine how long it takes "Fast phi" to compute phi(1020).

Section 9.1 | Section 9.2 | Section 9.3 | Section 9.4

Chapter 9 | DNT Table of Contents

Copyright © 2001 by W. H. Freeman and Company