division

[Jason Moxham]

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