Dirk Laurie on Fri, 24 Aug 2012 13:31:35 +0200

 How to do fast integer division

• To: pari-users@pari.math.u-bordeaux.fr
• Subject: How to do fast integer division
• From: Dirk Laurie <dirk.laurie@gmail.com>
• Date: Fri, 24 Aug 2012 13:31:27 +0200
• Delivery-date: Fri, 24 Aug 2012 13:31:35 +0200
• Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:date:message-id:subject:from:to:content-type; bh=iKqnNwviMdnvk8UHcK7NjP9jwiJIsH26y5KDJ31+i8U=; b=IPAP1zTieM4AS2xX+LDtAfPVVYa39lQjtUNuPIwmlgOQhS3wTzz7y10xf9EiTqtw87 qYsYdEATBvyYV+z+ncuGVXgn6ssSfRac4jsN+Qf+lfSxI1enYgFo0v6D7Rj4gG9Mklew fmcHlFQtwCHmMD4i3YpTfLbpvQOGFH5y/m/sTeFpRaZoNqZ/B0sKk0x4qTplorOVCdJT tSfkqDvlyDzN/l9jBDHJgkq79IzF1u0E59bqOm/h/UQNf7qis/K6fJbhcSZsWqPv+24f MlK8/U6gCB3Awy5S39YiJrOAK8AAWfGR2t2a2JLRsyDAoVrYUUhuUMbM60/tkN0i0F4a GPgA==

```I have an application that does lots of integer divisions with
large operands but small quotients.  As a model for that,
I handcoded the extended Euclidean algorithm as follows:

{mbezout(a,b)= my(X); X=[1,0,a;0,1,b]; if(a<b, i=2;j=1, j=2;i=1);
while(X[j,3]>0, X[i,] -= truncate(X[i,3]/X[j,3])*X[j,];
i=j; j=3-i);
X[i,]
}

This code is pretty standard, so I was astounded to see how
slow it is.  Timing on 10000-digit numbers:

? b1=bezout(a1,a2);
time = 16 ms.

? b3=mybezout(a1,a2);
time = 38,622 ms.

That's a factor of over 2000 slower, not to be explained