We begin here by recalling that the function
(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
(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
(20).
The output tells us that
(20) = 8. It also tells
you how long it takes to perform the computation.
Let's try out "First phi" on a larger number:
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
(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.
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
(n).
Exercise 1
(a) Use the applet to determine the time required to compute
|