Re: 64 bit divide/mod in 2.4.0-test5

[Linus Torvalds]

On Sun, 6 Aug 2000, Jamie Lokier wrote:
> 
> You're aware of the algorithm for printing digits that doesn't use
> any divisions, and decided not to use it, right?

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.

That one only uses simple subtraction to generate the numbers, but would
have been a much bigger change to existing cdoe. The differences for each
base gets moderately ugly too.

Is that the one you're talking about? Basically

	i = MAX_DIGITS;
	do {
		unsigned long long thispower = power_table[--i];
		char c = '0';
		while (thispower < num) {
			num -= thispower;
			c++;
		}
		output(c);
	} while (i);

or is there something more clever that can handle arbitrary bases cleanly
(not that we actually use arbitraty bases: the basic vsprintf routines
could handle them, but we limit the bases to the normal 8, 10 and 16
anyway - and as 8 and 16 can be handled with shifting onl yone really
requires any real computation)?

		Linus