Re: 64 bit divide/mod in 2.4.0-test5

[Jamie Lokier]

Oliver Xymoron wrote:
> > Yes, except instead of precomputing, you can generate power_table each
> > time by doing successive multiplications with the power.  You only need
> > to generate as many entries as digits in the current value.  The
> > multiplications are trivial if it's a constant power.
> > 
> > Of course 10 is the only significant non-power-of-two base anyway.
> > 
> > I've never tried that algorithm but I would guess it's faster than long
> > division.
> 
> That _is_ long division.

True, but it is one long division overall, not one per digit.

I just thought of a better algorithm.

  (a) Find nr. digits, i.e. smallest N s.t. base^(N+1) > number.
      Let k = base^N.  Can use a constant here if preferred.

  (b) Do N times:

          1. Subtract k repeatedly from number: count = digit.
             (Or use a faster method for a constant base, such as
             successive approximation).

          2. Multiply number by base.

It's better than the one I proposed before (and the one Linus outlined):
no table is required, no divisions, just multiplication by the base.

But this is getting silly :-)

-- Jamie