Re:Percy Ludgate
by perihelions on Saturday September 16, 2023 @07:17AM
(#37533801)
- "...and was the first to exploit a multiplier-accumulator to perform division, using multiplication seeded by reciprocal, via the convergent series 1/(1 + x)".
Am I overlooking it, or is this method missing from Wikipedia's "Division Algorithm" entry?
How it works is easy enough to figure from that description. You rescale your divisor to fit in the range (0.5, 1.0], then expand it as the series 1/(1 - x) = 1 + x + x^2..., which converges, and does so linearly at >1 bit per term (since x < 1/2). What's useful about this, is you can calculate the finite sums with a circuit that's logarithmic depth, or maybe better. You could do the repeated squarings to get: x, x^2, x^4, x^8...; then you have a bunch of parallel hardware multipliers filling out all the intermediate terms, which are products of zero- or one- of each of these basic terms; then you just find the sum with a logarithmic-sized tree of adders.
I haven't thought about it at all, but isn't it somewhat similar to Newton Raphson, in how it approximates a first reciprocal (here with a table), and then converges on better estimates in a few iterations?
Arguably the method for converging looks like it could be different at first glance. You could add it per WP:BOLD and see if anyone objects, the descriptions above are good enough to cite, such that there's no original work in describing the algorithm
Re:Percy Ludgate
by bsteinbach on Sunday September 17, 2023 @02:02AM
(#37541971)
Not only similar, it's identical to Newton Raphson in ideal arithmetic!
The nth order product approximation for the reciprocal of d = 1 - x is
y_n = product_{i=1}{n} (1 + x^{2^(i-1)}) = sum_{i=0}^{2^n - 1} x^i = (1 - x^(2 n)) / (1 - x).
The Newton-Raphson iteration for the reciprocal of d is
z_{n+1} = z_n * (2 - (1-x) * z_n).
Induction with the base case z_0 = 1 = y_0 shows the sequences are equal by inserting y_n for z_n in the Newton Raphson iteration:
z_{n+1} = (1 - x^(2 n)) * (2 - (1 - x^(2 n))) / (1 - x) = ( 1 - x^(4 n) ) / ( 1 - x) = y_{n+1}.
So I guess you could call it an explicit product formula for the Newton Raphson reciprocal.
Re:Percy Ludgate
by perihelions on Sunday September 17, 2023 @07:05AM
(#37543723)
This 100% checks out! I didn't recognize this at all.
- "...in ideal arithmetic!"
Comparing the two, Newton-Raphson seems rather better conditioned. I guess it's the (1.0 + x^(2^i)) part that holds back the explicit-product version (adding a large float with a small one).
Re:Percy Ludgate
by itigtohft on Sunday September 17, 2023 @11:11AM
(#37545865)
I don't know where you got the idea that there is a first guess that comes from a table. The table lookup just brings x into a suitable range, given A.
Shades of "Pray, Mr. Babbage, if you put into the machine wrong figures, will the right answers come out?"— a Taylor series can only do so much!
Re:Percy Ludgate
by aristus on Saturday September 16, 2023 @04:00PM
(#37538135)
This is basically how division on slide rules works.
"If we want to calculate a/b we can also calculate it as a * (1/b); that is the division of two numbers is the equivalent of the first number multiplied by its reciprocal."
Re:Percy Ludgate
by colanderman on Sunday September 17, 2023 @08:33AM
(#37544383)
Multiplication by the reciprocal isn't the interesting part. Computing the reciprocal using a convergent series is. (Which is not a process that is useful or even feasible on a slide rule, owing to the addition steps required, and the fact that slide rules can trivially perform division as you point out.)
Yeah. The "day job" has always been nothing more than a means to
better ends. Everything worthwhile, exciting, and satisfying I've
achieved in life was in the gaps between doing something I could use
my time better for. Like Twain said - "don't let schooling get in the
way of your education", similarly I think ones "work" happens despite
employment, rarely through it. In this way "capitalism" is a horrible
waste of human capital. Imagine what Ludgate might have achieved if
not counting penny corns. I hope for a world for children who'll get a
UBI, and space in life to develop their true selves.
Re:Percy Ludgate
by anon____ on Saturday September 16, 2023 @11:41AM
(#37535770)
He worked as a clerk while he designed his machine. It was 8 years after that, in his 30s, that he went to school again, and he chose to study accounting, not math, science or engineering. I think he knew exactly what he wanted and did exactly that. Except maybe dying of pneumonia at 39.
Re:Percy Ludgate
by rashkov on Saturday September 16, 2023 @12:47PM
(#37536402)
Maybe the habits of discipline that come from formal schooling and work are necessary for a man like Ludgate, or maybe not. We are products of our constraints to some extent
Re:Percy Ludgate
by thriftwy on Saturday September 16, 2023 @11:32AM
(#37535667)
However, it also means we do not know how many hobbyists has tinkered with analytical engines between Babbage and WWII, and whether any of these attempts were earlier or more advanced.
Am I overlooking it, or is this method missing from Wikipedia's "Division Algorithm" entry?
https://en.wikipedia.org/wiki/Division_algorithm?useskin=vec...
How it works is easy enough to figure from that description. You rescale your divisor to fit in the range (0.5, 1.0], then expand it as the series 1/(1 - x) = 1 + x + x^2..., which converges, and does so linearly at >1 bit per term (since x < 1/2). What's useful about this, is you can calculate the finite sums with a circuit that's logarithmic depth, or maybe better. You could do the repeated squarings to get: x, x^2, x^4, x^8...; then you have a bunch of parallel hardware multipliers filling out all the intermediate terms, which are products of zero- or one- of each of these basic terms; then you just find the sum with a logarithmic-sized tree of adders.
Somehow, I can't find the name of this algorithm.
I haven't thought about it at all, but isn't it somewhat similar to Newton Raphson, in how it approximates a first reciprocal (here with a table), and then converges on better estimates in a few iterations?
Arguably the method for converging looks like it could be different at first glance. You could add it per WP:BOLD and see if anyone objects, the descriptions above are good enough to cite, such that there's no original work in describing the algorithm
The nth order product approximation for the reciprocal of d = 1 - x is y_n = product_{i=1}{n} (1 + x^{2^(i-1)}) = sum_{i=0}^{2^n - 1} x^i = (1 - x^(2 n)) / (1 - x).
The Newton-Raphson iteration for the reciprocal of d is z_{n+1} = z_n * (2 - (1-x) * z_n).
Induction with the base case z_0 = 1 = y_0 shows the sequences are equal by inserting y_n for z_n in the Newton Raphson iteration: z_{n+1} = (1 - x^(2 n)) * (2 - (1 - x^(2 n))) / (1 - x) = ( 1 - x^(4 n) ) / ( 1 - x) = y_{n+1}.
So I guess you could call it an explicit product formula for the Newton Raphson reciprocal.
- "...in ideal arithmetic!"
Comparing the two, Newton-Raphson seems rather better conditioned. I guess it's the (1.0 + x^(2^i)) part that holds back the explicit-product version (adding a large float with a small one).
Shades of "Pray, Mr. Babbage, if you put into the machine wrong figures, will the right answers come out?"— a Taylor series can only do so much!
"If we want to calculate a/b we can also calculate it as a * (1/b); that is the division of two numbers is the equivalent of the first number multiplied by its reciprocal."
http://www.sliderules.info/a-to-z/mul-div.htm
https://www.ludgate.ie/percy-ludgate/