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