Re: [HACKERS] About numeric division again
Gregory Stark <[EMAIL PROTECTED]> writes: > "Tom Lane" <[EMAIL PROTECTED]> writes: >> The code that's currently in there sometimes has to propagate rounding >> to the left, meaning that you can never be certain whether all of the >> digits you have so far are good, and that means that it can sometimes >> generate an incorrect truncated output. This leads to the bugs cited >> in the above message. > The case I looked into could be traced specifically to the fact that it > calculates an intermediate value which is the reciprocal of the divisor and > multiplies by that. Perhaps, but no matter how you slice it, that algorithm sometimes needs to go back and "fix" digits it previously emitted. That's okay for approximate answers and not okay for exact ones, because you never know if you're done fixing the last digit you need to return. I fooled around with the idea of using the existing fast division code in the sqrt/exp/log/power functions, and got these timings for the numeric_big regression test: XeonHPPA CVS HEAD5.446s 2m10.97s Knuth division only 11.574s 3m9.29s old code for trans. fns 5.477s 2m15.97s The HPPA is an old machine with excruciatingly slow integer division, so it's probably about the worst case for the Knuth-based code. Now you can certainly object that numeric_big might not be representative of real-world applications, but these results seem to me to justify implementing both functions. wc says that numeric.c is 5457 15914 122662 CVS HEAD 5466 16050 123401 Knuth only 5732 17202 130764 both A couple hundred more lines seems like an acceptable price. Also, I remembered the reason for proposing an explicit "integer division" function: you can't always get the right answer from trunc(x/y). The / operator will round its output at some number of fractional digits chosen by itself, and it's possible that it rounds .999... up to the next integer, whereupon your trunc() result is simply wrong. (Indeed this is just the same problem at the SQL level as mod was facing at the C level in one of the bugs that started this discussion.) So if you want to do any high-precision integer math, this is really not a negotiable feature. So IMHO the only question left is what to call it at the SQL level. A few options: Expose it as a function: div(x, y) quotient(x, y) Expose it as an operator: x // y There are probably better ideas I haven't thought of. Comments? regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] About numeric division again
"Tom Lane" <[EMAIL PROTECTED]> writes: > One of the items on the commit-fest list is my patch from last year > to rewrite the numeric division operator using "schoolbook division": > http://archives.postgresql.org/pgsql-patches/2007-06/msg00173.php > > The code that's currently in there sometimes has to propagate rounding > to the left, meaning that you can never be certain whether all of the > digits you have so far are good, and that means that it can sometimes > generate an incorrect truncated output. This leads to the bugs cited > in the above message. The case I looked into could be traced specifically to the fact that it calculates an intermediate value which is the reciprocal of the divisor and multiplies by that. The case where the digits were inaccurate was a case where there reciprocal wasn't representable and multiplying by the reciprocal didn't produce the same value as dividing. I assume you're right about there being bigger problems but I don't follow how the division is actually being done in enough detail to judge that for my self. -- Gregory Stark EnterpriseDB http://www.enterprisedb.com Ask me about EnterpriseDB's 24x7 Postgres support! -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
[HACKERS] About numeric division again
One of the items on the commit-fest list is my patch from last year to rewrite the numeric division operator using "schoolbook division": http://archives.postgresql.org/pgsql-patches/2007-06/msg00173.php The code that's currently in there sometimes has to propagate rounding to the left, meaning that you can never be certain whether all of the digits you have so far are good, and that means that it can sometimes generate an incorrect truncated output. This leads to the bugs cited in the above message. The reason I didn't just commit it last year is that I was dissatisfied with the speed penalty --- on very long inputs (dozens or hundreds of digits) division is about 4X slower than with our existing code. However, no one has come up with a better answer; and as a wise man once said, "I can make this program arbitrarily fast, if it doesn't have to give the right answer". Correctness has to trump speed. One thing that occurs to me is that we could keep the existing "approximate division" code in there too, and use it internally in the transcendental function implementations. Those are not particularly interested in getting exact truncated results, and they are the worst case for the speed penalty because they do lots of divisions on values that are likely to be long. However this idea could fairly be charged with being code bloat. Comments? Also, there was some discussion of providing a SQL-level numeric "integer division" operator or function, that is the equivalent of trunc(x/y) except faster (since it'd not need to compute fractional digits that would then be thrown away). Is this worth doing, and if so what should we call it exactly? The amount of new code needed should be pretty small (just an interface function), so I'm willing to take care of it if we want one. regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
