Modern Electronics (was Re: List charter mods & headcount... ;

From: der Mouse <mouse_at_Rodents.Montreal.QC.CA>
Date: Wed Jun 23 18:58:38 2004

>> I've had many an argument with my father over this. He insists on
>> using the binomial expansion. I prefer the Newton iteration, which
>> converges very quickly

So, you use Newton-Raphson; he uses binomial. Nothing wrong with
either one. (Though I'm not familiar with how to use binomial
expansions to find square roots.)

> There's also a method I learnt long ago that is laid out in the same
> way as a long division. I've forgotten it because it seemed
> moderately pointless!

Today, it is, when a computer can cough up several thousand digits in
the time it takes you to work out three by hand.

Knowing how to do it, though, involves learning enough of the theory
behind it to stand you in good stead in other cases, though. (Assuming
you actually understand it. Learning how to do it by rote, without
understanding why, _is_ pretty pointless.)

> I expect that there may well be a similar method for the cube root.

There is, but it is significantly more elaborate to perform.

Longhand square root extraction is based on (X+d)^2 = X^2 + 2Xd + d^2.
For example, to work out sqrt(15.5) (in decimal), we start with the
first digit. (If you can't get the first digit right without
assistance, you have no business trying something this elaborate! :-)

___3.___________
) 15.50 00 00 00
   9 6
  --
   6 50

Now, we have written 15.5 = (3^2 + 2?3?d + d^2), with d to be
determined. The 6.50 is 2?3?d + d^2. The 6 sitting off at the right
is what I saw described as the memorandum column; it's twice the
root-so-far. Now, we look for a digit X such that 6X * X <= 650 (this
is 2?3?d+d^2). We want the largest digit that fits; 9 works, so we
fill it in, and write in and subtract off 69*9:

___3._9_________
) 15.50 00 00 00
   9 6
  --
   6 50
   6 21 78
   ----
     29 00

This gives us 15.5 = 3.9^2 + .29, and we need to write .29 as
2*3.9*d+d^2, for some value of d in [0,.1).

The mechanics of this is that we find X such that 78X * X < 2900.
783*3=2349, but 784*4=3136, so we use 3 (that is, we've decided d is in
[0.3,0.4)):

___3._9__3______
) 15.50 00 00 00
   9 6
  --
   6 50
   6 21 78
   ----
     29 00
     23 49 786
     -----
      5 51 00

Et cetera. Und so weiter. Og s? videre.

Usually, you can get the next digit right by looking at just the high
digit or two of the memorandum column; only when it's close to the edge
may you have to try multiplying out different choices in full. In the
next position, for example, I'd look and say "55/7 = 7+, let's try 7",
and indeed, 7 works (barely - the remainder is so low the next two
digits of the root are zero).

You can do the same thing for cube roots, writing
(N+d)^3=N^3+3N^2d+3Nd^2+d^3, but the arithmetic with the memorandum
column becomes a good deal messier.

> If push came to shove (i.e. no calculator, no computer, no slide
> rule, no log tables) I'd go for Newton Raphson too.

Well...for the first few digits, I'd probably do something ad-hoc,
bisection and/or cut-and-try. If I needed more precision, I'd likely
use Newton-Raphson, but I'd truncate the quotient to about the number
of places that I know are good, since I also know that N-R is fully
capable of recovering from a more or less arbitrary guess, so the lost
digits will, at most, slow convergence - and I care less about the
number of N-R steps required than I do about the amount of work I need
to do during them.

If I needed a high-precision root, of course the last steps would be
N-R. But under no-tools circumstances, it's unlikely the root is
needed to more than about three significant digits anyway.

/~\ The ASCII der Mouse
\ / Ribbon Campaign
 X Against HTML mouse_at_rodents.montreal.qc.ca
/ \ Email! 7D C8 61 52 5D E7 2D 39 4E F1 31 3E E8 B3 27 4B
Received on Wed Jun 23 2004 - 18:58:38 BST