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 =
> there is a large speed up (upto 5000x) ,though I thought gmp allready h=
> code for this special case?
I see at=20
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=
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=
Another way to do this would be to multiply the numerator by say 256 , th=
calculate just the quotient , then this quotient is 8 bits too big , and =
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=