On
27/5/2003, Peter Macinnis posted:
I had an e-mail today from a 9th grade home-schooler, asking how to
extract cube roots and fifth roots of numbers. Aside from using
logs, I have found one algorithm that works fairly well in a
spreadsheet, but I wondered what methods were used in the days
before calculators and spreadsheets -- or did people just use logs?
I will share the spreadsheet solution later.
David
Maddern responded:
Slide Rules and Ready Reckoners
Toby Fiander added:
That was my recollection, too. I got
my first slydrool in about 1969, and was learning various tricks with it
when.... Messrs Hewlett and Packard got the HP35 to Australia at
the end of 1972. It cost about the same as an old car of the kind
a newly working engineering cadet might want to buy. What a
choice to have to make....
The methods had their
drawbacks. An acquaintance with some survey training recently
told me that the meaning of the universe was 43. She said she had
used Chambers' seven figure log tables in the calculation.
Donald
Lang replied in detail:
It may depend how old you are. I
learned a method of getting square roots in primary school. If you saw
it on a page without focussing much you might think of it as a long
division style.
I have seen an arithmetic text
book that showed a similar sort of structure for a method of extracting
cube roots. Whereas for square roots you took the digits in pairs, for
cube roots you took them in threes. Both were based on a binomial
expansion of the reverse process.
More efficient for even square
roots of longer numbers is Newton's method of improving approximations.
You can use it for most solving many numerical problems, but I had
better not get carried away.
Suppose you want the nth root of x.
To get a simple approximation,
start by finding how many digits there are before the decimal point.
For fifth roots: the fifth root of
any number greater than one and less than 105 has one digit before the decimal point,
etc. So you play around until you find how many digits you will need.
Continuing with fifth roots, 32(1/5) = 2, you proceed through 243, 1024,
3125, 7776, 16807, 32768, 59049 and 100000, being the smallest integers
with 5th roots. So the fifth root of any number between 16807 and 32768
starts with 7. So just suppose we want the fifth root of 24000.
It is obviously 7.something.
I will state that the next
approximation is obtained by first finding the difference 24000 - 16807
= 7293.
The desired approximation is then
7 + 7293 / (5 * 74)
= 7
+ 7293/ 12005
= 7.60
Then 7.605 = 25355, which is too big.
So our next approximation is
7.60 - (25355 - 24000)/ (5 * 7.604)
= 7.60 - 1355 /
16681
= 7.60 - 0.0812
= 7.5188
Now 7.51885 = 24029.4
The next approximation is 7.5170
and 7.51705 = 24000.6
Obviously a calculator helps a
lot. The method does not require your calculator to have logs in the
package, and after a set of small stumbles the process becomes a lot
more efficient.
More details on request, but they
may be in a text book near you in a more transparent form..
Peter Macinnis replied:
OK, I was hoping somebody had done the brain-bending already.
I plan to run with this one, taken from
http://surfboard.surfside.net/prussell/approximations/RootAlgorithms.htm
and converted to a spreadsheet
The approximation is based on the previous value of z as follows:
Z(new) = z - (z^k - N)/(k*z^(k-1))
[or w ~ z - (z^k - N)/(k*z^(k-1))]
where
N is the number for which the kth root is required
k is the power
w is the value of the kth root of N
z is the approximate value.
In a spreadsheet, place these labels:
A1 Target (N)
A2 Power involved
A3 First estimate
Put the appropriate values in B1, 2 and 3.
The B4 is set to =B3-((B3^B$2-B$1)/(B$2*B3^(B$2-1)))
and this is copied down to about row 30, by which time the iteration
has settled.
Those wishing to try should be able to paste in the value for B4
Anthony
Morton commented:
> The
approximation is based on the previous value of z as follows:
>
> Z(new) = z - (z^k - N)/(k*z^(k-1))
Which of course is Newton's
Method. Three centuries old but still giving the best
combination of robustness and fast convergence.
Of interest to the advanced high
school student is that you can generate quite pretty pictures with
these formulae by iterating them in the complex plane for various
(complex) initial values and colouring each initial point according to
which of the k roots it converges to.
Pragmatically of course, if you
have access to a spreadsheet or half-decent calculator you can extract
roots automatically without resorting to an iterative algorithm.
I suggest that to get the full pedagogical benefit of extracting roots
by hand, a student should experience doing it with nothing more than
pencil and paper - perhaps
allowing the use of a calculator
for basic arithmetic operations only.
Another type of calculation
involving powers that is instructive to do 'by hand' (with the
assistance of a calculator for + - * /) is the old compound interest
formula: taking a number very close to 1 and raising it to a large
integer power. The squaring-and-adding approach has come in very
handy on the odd occasion when I haven't had access to a scientific
calculator.
Peter replied:
Thanks, Anthony -- this began with an e-mail from a US home-schooler,
asking how you extract a fifth root, and that set me off on a different
path, as I am creating a set of spreadsheets that do interesting things
as part of my work, and I have done a few that use iteration in various
ways. So far, I have a kludgey algorithm of my own for cube
roots, in a separate worksheet called "Bad attempts", the Newton
version in three implementations as I honed them, and some notes.
Including your comments as they appear above -- may I credit you as the
person to blame?
Ivan
Sayer responded:
It's worth remembering that this
question would have been damn near meaningless to all but the highest
flyers before Simon Stevin invented decimals. Imaging trying to
calculate the fourth root of fifteen if your only notation was Roman
numerals!
I came up with three methods all
of which are "easy". But the calculations are so damn tedious
that you have to have a real reason for doing it.
1) z(new) =
1/2(z+N/(z^(k-1)))
This is a slightly simpler version
of the solution already discussed. It has the minor advantage of
being almost obvious when z, N are positive. It also works with
positive numbers no matter where you start.
2) Briggs-Burgi
Calculate a table of powers of
1.00001 until you find the first such power which is larger than the
target number. Divide the index of this power by k, the number of
the root you wish to find. Round to the nearest whole number and look
back along your table for the number that has the last result as index
and there is your approximate value. If you want greater accuracy
shove a few more zeros in your base e.g. 1.0000000001
Calculating these powers can be
done solely by addition. It's almost the same as calculating rows
of Pascal's triangle, except that you eventually get carry between
digits. However, calculating several thousand rows is *very*
tedious.
This is how Briggs and Burgi built
logarithm tables.
3) Multiply your target by 10(k*(n+1))
where n is the number of digits you want, giving say S. Now build a
table of kth powers of integers until you hit the two closest below and
above S. Divide these two results by 10(n+1) and you
have an upper and lower approximation.
I suspect the solution already
discussed beats all of these for speed but I haven't yet proved it.
