Linux-kernel mailing list archive 2000-32,: Re: 64 bit divide/mod in 2.4.0-test5

# Re: 64 bit divide/mod in 2.4.0-test5

Jamie Lokier (lk@tantalophile.demon.co.uk)
Tue, 8 Aug 2000 23:24:53 +0200

- Messages sorted by: [ date ][ thread ][ subject ][ author ]
- Next message: Russell King: "Patch: fbcon generic memmove fix"
- Previous message: Josh Huber: "panic/reboot changes (RFC)"

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/

- Next message: Russell King: "Patch: fbcon generic memmove fix"
- Previous message: Josh Huber: "panic/reboot changes (RFC)"