fast special case of division?

[keith.briggs at bt.com]

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?

Keith

	Dr. Keith M. Briggs
	Senior Mathematician, Complexity Research
	Mobility Research Centre, BT
	http://keithbriggs.info
	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