Quote:
Originally Posted by SPWorley
It seems as if it computes an (approximate!) floating point reciprocal to q, then uses that to compute how many multiples of q to subtract off. So this may be doing classic division and subtraction to compute its mods, boosted by using a floating point initial approximation step.

Compare that to Algorithm D in section 4.3.1 of Knuth's
The Art of Computer Programming. I haven't done that myself, but I'd bet that there's some similarity.