This problem deals with the harmonic function
H defined by:
In calculus you learn that the series above diverges
(gets arbitrarily large as n tends to infinity).
The harmonic function comes up much more frequently in
computer science than it does in mathematics.
It turns out that H(n) is closely approximated
by loge(n). In fact, the difference
H(n) - loge(n) tends, as n tends to infinity,
to a weird constant, denoted by γ
(a lower-case Greek letter "Gamma")
and known as Euler's constant.
All calculations below should be done with doubles.
Write a function H with a loop in Java or C
with one parameter n
that will calculate and return H(n).
[As a check, the value of H(10)
should be 2.9289682539682538.]
Calculate approximate values for γ
by calculating H(n) - loge(n) for
n = 10, 100, 1000, ..., successive powers of 10.
See how large a power of 10 your machine will handle.
In the end say what keeps you from going to the next higher power
of 10. Does the highest power of 10 give you the best
approximation? If not, why not?
[It might seem like 109 is the biggest you can
go, since the int type has maximum 231 - 1, which
is less than 1010, but in Java you can use
the long type to get 64-bit integers. In C you can store
integers in doubles, to get roughtly 51-bit integers.]
Write a second function H2 in Java or C
without using a loop, but using recursion
that will also calculate and return H(n).
Now carry out the same calculation as in part ii for
this recursive version of H.
As before, what limits the size of n that you can get up to?
[Note: H(n) - loge(n) = γ +
O(1/n). The constant γ
has been studied for almost 400 years.
In spite of all the work, no one has proved that
γ is not a rational number
(a fraction), although everyone believes that it is
transcendental (not a root of any polynomial equation).]
Lesson:H(n) = Θ(log n).
Revision date:2012-09-03.
(Please use ISO
8601, the International Standard.)
