Re: 64 bit divide/mod in 2.4.0-test5

[Jamie Lokier]

Linus Torvalds wrote:
> I'm aware of at least one such algorithm, yes. However, that one is
> designed for a single base (or a small number of bases) and basically just
> creates a nice table in memory of the powers-of-base or uses pre-computed
> tables.
> [...]
> Is that the one you're talking about? 

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.

-- Jamie