[HN Gopher] Percy Ludgate
       ___________________________________________________________________
        
       Percy Ludgate
        
       Author : fidotron
       Score  : 94 points
       Date   : 2023-09-16 10:10 UTC (12 hours ago)
        
 (HTM) web link (en.wikipedia.org)
 (TXT) w3m dump (en.wikipedia.org)
        
       | perihelions wrote:
       | - _"...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?
       | 
       | 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 (?)
        
         | aristus wrote:
         | 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."
         | 
         | http://www.sliderules.info/a-to-z/mul-div.htm
        
         | tux3 wrote:
         | The algorithm is described in more details in
         | https://academic.oup.com/comjnl/article/14/3/317/420539?logi...
         | (around page 323, page 318, ..)
         | 
         | 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
        
           | perihelions wrote:
           | That representation's even nicer - the logarithmic complexity
           | is immediately evident:                   1/(1 + x) = 1 - x +
           | x^2 - x^3 ...                    = (1 - x) (1 + x^2) (1 +
           | x^4) (1 + x^8) ...
           | 
           | late edit: I've tested and confirmed that the naive
           | implementation does in fact work. This C snippet is within at
           | most 1 ULP for most double floats in the range (0.5, 1.0]: I
           | tested a few billion and found no counterexamples.
           | double recip(double y) {            long double x = ((long
           | double) y) - 1.0;            long double u = 1.0 - x;
           | long double v = x;            for (int j=1; j<=5; ++j) {
           | v = v * v; // v = x^(2^j)               u = u * (1.0 + v);
           | }            return (double)u;  // approx. 1.0/y         }
        
       | molly0 wrote:
       | Working a day job and then spending your nights working on an
       | engineering project (like Ludgate did) will always be the most
       | inspiring part for me.
        
         | thriftwy wrote:
         | 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.
        
         | nonrandomstring wrote:
         | 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.
        
           | [deleted]
        
           | rashkov wrote:
           | 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
        
       | dang wrote:
       | https://history.computer.org/pioneers/ludgate.html
       | 
       | https://www.ludgate.ie/percy-ludgate/
        
       ___________________________________________________________________
       (page generated 2023-09-16 23:01 UTC)