fast special case of division?

keith.briggs at keith.briggs at
Tue Mar 6 15:37:29 CET 2007

Suppose we want to do a truncated division n/d (n and d are mpz_t), where we know in advance that:

1.  n>d>0
2.  q=floor(n/d) is a small integer, most likely 1, and almost certainly it will fit in a limb.

How can we get q as fast as possible?    Is it best to just divide the most significant limbs of n and d, and correct q when it is wrong?


	Dr. Keith M. Briggs
	Senior Mathematician, Complexity Research
	Mobility Research Centre, BT
	phone: +44(0)1473  work: 641 911 home: 610 517  fax: 642 161
	mail: Keith Briggs, Polaris 134, Adastral Park, Martlesham, Suffolk IP5 3RE, UK

More information about the gmp-discuss mailing list