ljdickey@watmath.UUCP (Lee Dickey) (09/21/84)
Some hand held calculators have logarithm and exponent keys. But some less expensive ones have only "square roots" and "squares". Here is what I think: these two functions can be used to calculate an approximation to x^y. Here is the algorithm that I use: Enter the number x. Press the "square root" key N times. Subtract 1. Multiply by y. Add 1. Press the "square" key N times. Can you explain why the algorithm works? How do you tell, for a given "x", what "N" should be?
rwh@exodus.UUCP (Roy Haas) (09/21/84)
Since the limit lim [ y( x^(1/2n) + 1 ]^2n = x^y n-> inf holds (use L'Hospital's Rule), your algorithm works for "large n". The rate of convergence depends on how large x is, since repeated rooting drives x^1/2n to 1. It also depends on how large y is, since y(x^1/2n - 1) must approach 0. Note that the algorithm is only useful as an approximatiion for y where the fractional part has an infinite binary expansion (otherwise you can compute x^y exactly in a finite number of steps).
ljdickey@watmath.UUCP (Lee Dickey) (09/26/84)
Six people responded to my article "Square Roots give Powers".
They are:
Mark Manasse = ihnp4!gargoyle!msm
Dave Clark = ihnp4!houxm!homxa!wdc
Albert Algava = ihnp4!houxm!hound!5143ama
Kevin Martin = kpmartin
= allegra!hplabs!hplabsb!ayanoglu
Roy Haas = allegra!ulysses!gamma!exodus!rwh
All of them had correct methods of justifying the result I mentioned.
Kevin even suggested an improvement. A proof was mentioned by Roy,
and one is included below. Several of the arguments are summarized
here:
=================================================================
We want to show that
(1+y*(x^(1/(2^n))-1))^(2^n) ~= x^y
Let M=2^n. What we want to show is:
(1+y*(x^(1/M)-1))^M ~= x^y
Now, let a = x^(1/M)-1. Then what we are looking at is:
(1+y*a)^M ~= ((1+a)^M)^y
But, ((1+a)^M)^y = ((1+a)^y)^M. So, taking power 1/M, we get:
(1+y*a) ~= (1+a)^y
This last approximation is well known as a generalation of the
binomial expansion. Accuracy improves for "a" small, and here,
"a" gets small quickly as "n" gets large. Kevin Martin points
out that the identity can be sharpened by taking three (or more)
terms on the left side instead of just two. For instance,
(1+ y*a + .5*y*(y-1)*a^2) ~= (1+a)^y
is an improvement.
=================================================================
Here is a short proof that the process really does converge:
The proof is one that uses limits, along the lines of those proofs
that are used in elementary calculus. Recall the algorithm:
Enter the number x.
Press the "square root" key N times.
Subtract 1.
Multiply by y.
Add 1.
Press the "square" key N times.
Pressing the SQRT key N times gives
(((x^.5)^.5)...)^.5 = x^(1/(2^N)).
To simplify, I write M=2^N.
Thus
(((x^.5)^.5)...)^.5 = x^(1/(2^N)) = x^(1/M).
Combining the rest of the steps, and calling the result Z, we get:
Z = (1+y*(x^(1/M) - 1))^M.
The problem is to show that for N (and hence M) large enough, this
expression is approximately x^y. That is, that
Z --> x^y, as M --> infinity.
Now,
ln Z = M * ln ( 1+y*(x^(1/M) - 1) )
ln ( 1+y*(x^(1/M) - 1) )
= --------------------------------------
1/M
The above quotient satisfies the conditions of one version
of L'Hospital's rule. Thus, differentiating both numerator
and denominator with respect to M gives
limit ln Z = limit W
where
(1 / ( 1+y*(x^(1/M) - 1) )) * y * (ln x) * (x^(1/M)) * (-1/M^2)
W = -----------------------------------------------------------------
(-1/M^2)
= (ln x^y) * (x^(1/M)) / ( 1+y*(x^(1/M) - 1) )
But, as M-->infinity, (1/M)-->0, and x^(1/M)-->1. And thus,
W-->(ln x^y) * (1) / (1+y*(1 - 1) )
= ln x^y.
Hence,
limit ln Z = ln x^y, and
limit Z = x^y.
Q.E.D.
=================================================================
How many times should I press the SQRT key? Here is a simple
heuristic: For numbers "x" bigger than "1", successive square roots
get closer and closer to 1. Because the machine truncates, you do not
want to press too many times, because eventually the some successor
could become 1. So watch the display. The numbers become the form
1.0000xxxx
A good time to stop is when there are about as many zeros as there are
digits "x" to the right of the zeros.ecl@hocsj.UUCP (09/30/84)
Subject: Re: Square Roots give Powers
An interesting sidelight of this problem is that x^(1/c)-1 is very
nearly a logarithm.
For large c
x^(1/c) ~= 1
x^((1/c) - 1) ~= 1/x
integrating both sides and approximating the integration constant we get
c*(x^(1/c) - 1) ~= ln(x)
x^(1/c) - 1 ~= ln(x)/ln(exp(c)) = log x
exp(c)
That is "log to the base exp(c) of x"
My TI calculator said to take the square root 11 times. That says that
c = 2^11 = 2048. This means that when you take the square root of a
number 11 times and subtract 1 you are really getting a close
approximation of log base (exp(2048)) of that number. You are dealing
with logarithms of base approximately 1.7E38. Who would have thought
that a logarit with such a humungous base would be so easy to
calculate? Usually the algorithms I have see always have you perform
the inverse operation at the end. Nobody usually deals with logarithms
of giant bases. However if what I have found useful on my pocket CASIO
is to take square roots 11 times, subtract one, and divide by the easy
to remember constant 0.0011248. This gives you the common logarithm to
about three decimal place accuracy. Dividing by 0.0004883 gives you
the natural logarithm. Where do these numbers come from? Take 10,
take its square root 11 times and subtract 1 and you get 0.0011248.
(Evelyn C. Leeper for)
Mark R. Leeper
...ihnp4!lznv!mrl