View Single Post
Old 2009-08-24, 20:25   #4
cheesehead's Avatar
"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts

Originally Posted by SPWorley View Post
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.
cheesehead is offline   Reply With Quote