# division

**Jason Moxham
**
J.L.Moxham@maths.soton.ac.uk

*Thu, 7 Nov 2002 09:43:28 +0000*

On Wednesday 06 Nov 2002 8:41 pm, Jason Moxham wrote:
>*
*>* The runtime is proportional to the quotient , so for large n and small =
*q
>* there is a large speed up (upto 5000x) ,though I thought gmp allready h=
*ad
>* code for this special case?
*>*
*
I see at=20
http://www.swox.com/gmp/projects.html
under Quotient only division
that gmp doesn't yet have it.
I can't see how that method described would work , the quoitient is uncer=
tain=20
in the lowest couple of bits ( on average) , so on average the remainder=20
needs to be calculated all except lowest couple of bits, not much of savi=
ng.
Another way to do this would be to multiply the numerator by say 256 , th=
en=20
calculate just the quotient , then this quotient is 8 bits too big , and =
has=20
an uncertain low few bits which can be shifted into nothing , on average.
So you end up only needing to do the remainder 3/256 times (as uncertaint=
y is=20
0,1,2)=20
jason