| Problem a)
Follows from the solution to problem b.
Problem b)
We are trying to approximate a value X to within an error of eps1,
i.e.,
X ~eps1= 2^r / 5^n r, n non-negative integers
We can "take the log of both sides", that is, we can find a value
eps2 such that:
log(X) ~eps2= log(2^r / 5^n)
will guarantee that the previous condition will also be met. In
particular I will let the log be to the base 2 (lg), so
lg(X) ~eps2= r - n*lg5
CASE 1: X = 1; lg(X)=0
r=n=0
CASE 2: X > 1; lg(X)>0
The following procedure will find the necessary values:
Let X' be 1 - decimal_part(X).
We want to find an "n" such that
X' ~eps2= decimal_part(n*lg5)
Note that lg5 is irrational (easily proven) and that this implies (I
have not yet proven this, but I am quite confident about it, and I
think that I have seen such a proof) that such an n can always be
found.
Now choose r = floor(X) + floor(n*lg5) + 1, and we are done.
CASE 3: X < 1; lg(X)<0
Let:
n1 = ceiling(|X|/lg5) (note: n1>0)
and let
Y = lg(X) + n1*lg5
Note that Y is non-negative and the logrithm of some positive
value. We may thus use the previous two cases to find an r and
an n2 such that,
Y ~eps2= r - n2*lg5
But since
lg(X) = Y - n1*lg5
we get that:
lg(X) ~eps2= r - n2*lg5 - n1*lg5 = r - (n1+n2)*lg5
Since r, n1 and n2 are all non-negative integers and thus n = n1+n2
is also, we have solved this case as well. QED
I'll see if I can come up with a proof or a pointer to a proof for the
unproven lemma this lunch hour. Contributions on this welcome.
Topher
|
| To finish up, we need (to outline) a proof for the following lemma:
Let p be an irrational number. Then we can find a positive integer
N such that decimal-part(N*p) will be less than eps (0<eps<1) of
any arbitrary value t (0<t<1).
Lets first examine the behavior of a rational value a/b (assumed
reduced, i.e., a r.p. b) under successive multiplication by the integers
1 through b. The decimal parts of the results will form the set:
{1/b, 2/b, 3/b, ... , (b-1)/b, 1}
So any t (0<t<1) may be approximated within eps = 1/b by the decimal
part of some multiple of a/b between 1 and b.
So we need only find a rational approximation to p (our irrational),
a/b, such that:
1) a/b is in fully reduced form,
2) 1/b < eps/2
3) b*p ~eps/4= a (= (a/b)*b)
4) a/b > p
This means that each of the multiples of p between 1*p and b*p will be
within eps/4 of one of the multiples of a/b between 1*a/b and b*a/b.
(Condition 4, will make each irrational multiple slightly smaller than
its corresponding rational multiple). This in turn means that the
decimal part of each multiple of p will be within eps/4 of each of
the decimal part of the corresponding multiple of a/b. (Condition 4
avoids "wrap around" for the value near 1). One of those decimal
parts of a multiple of p will therefore be within eps/4 of a value
within eps/2 of t, which means that it is within eps of t. QED.
Topher
|