O(n^2) is bad - can it be fixed?

[Tim Peters]

[Bruce Dawson]
> For what it's worth - this might actually be one point in MS's
> favour. If I remember correctly the divides in the roundup()
> routine are all dividing by integer constants.

They used to, yes.  Not anymore.

> VC++ deals with those very nicely. In optimized builds (optimized
> for speed anyway) it is impossible to get it to emit a divide
> instruction - it always replaces it with bit shifts.

Not quite.  This is well-known technology in the compiler biz, and shifts
only suffice for very special divisors.  Here's what it generates for an int
divide by 100 (with numerator in ecx), which is more typical:

	mov	eax, 1374389535
	imul	ecx
	mov	eax, edx
	sar	eax, 5
	mov	ecx, eax
	shr	ecx, 31
	add	eax, ecx

The expensive part is the IMUL, and the cost of that varies widely across
Pentium flavors.  It's certainly faster than a division, but still much
costlier than a simple shift.

> It does a particularly efficient job if the number you are dividing
> is unsigned.
>
> It doesn't matter what number you divide by - it knows how to simulate
> dividing by every integer I've ever tested with.

If you're curious about how this works, search Google for "Integer Division
Using Reciprocals" (1991), by Robert Alverson.  That even covers how to do
it with multiplies and shifts if you *don't* know the divisor at
compile-time (and, e.g., the Itanium has no division instruction, so on that
chip these tricks are essential).

For a known divisor c, in effect you treat x/c as x*(2**i/c)/2**i for a
suitable i, compute 2**i/c at compile-time, multiply x by that at runtime,
"/2**i" is a right shift, and so multiply and a right shift gets an
excellent guess.  Then you carefully adjust for all possible endcase errors.
It's not simple, but it does work <wink>.

> So, you may have improved on a Win32-only problem, and also improved
> on a non-Win32-only problem also. The symmetry appeals to me.

Yup.  I was much keener to get rid of the division than to do the resizing
bit, in fact.