Re: WIP: rewrite numeric division

"Tom Lane" <tgl(at)sss(dot)pgh(dot)pa(dot)us> writes:

> The bad news is that it's significantly slower than the CVS-HEAD code;
> it appears that for long inputs, div_var is something like 4X slower
> than before, depending on platform.

Where did we get the CVS-HEAD algorithm from anyways? 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.

I'm not sure I see how to apply Newton's Method and get such low complexity
though. It seems to me like you would have to repeatedly multiply so you
should get an additional factor in the complexity representing the number of
iterations necessary.

> Still this is a bit annoying. Anyone see a way to speed it up, or
> have another approach?

What order of complexity is this algorithm? It looks basically like O(n^2)
school-book division or is there something more clever going on?

--
Gregory Stark
EnterpriseDB http://www.enterprisedb.com