Division degeneration

Torbjorn Granlund tege@swox.com
01 Nov 2002 19:45:42 +0100


When dividing a (3n-s)-limb number by a n-limbs number, for
a small s, GMP degenerates to quadratic behaviour.  This
problem was discovered by Kalle Hasselström, who works on
divison optimizations for GMP 4.2.

The result of this flaw is that a division of a number with 150000
limbs by a divisor of 100000 limbs runs fast at a few seconds,
while a division of a 149999 limb number by the same divisor
takes several minutes...

I just checked in a fix for GMP 4.2.  The silly code was in
mpn/generic/tdiv_qr.c.

-- 
Torbjörn