Re: WIP: rewrite numeric division

Gregory Stark <stark(at)enterprisedb(dot)com> writes:
> Where did we get the CVS-HEAD algorithm from anyways?

IIRC it's from Smith's "FM" library cited in numeric.c, which is also
where most of numeric.c's higher-order-function algorithms came from.
It's good code but oriented to scientific computing, which means it
thinks that a close approximation to the right answer is good enough.
In hindsight, there are too many people out there who expect div and mod
to be exact for us to go with that approach.

> wikipedia lists a whole
> bunch of multiplication algorithms -- none of which sound like this -- but
> only two division algorithms, "school-book" which is O(n^2) and Newton's
> Method which has complexity equal to the multiplication method used.

Yeah, my proposed patch is schoolbook division. I don't think I'd trust
Newton's method to give anything but a close approximation, which is
what we have in HEAD already.

regards, tom lane