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
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/
This archive was generated by hypermail 2b29 : Tue Aug 15 2000 - 21:00:16 EST