Skip to content

Commit 9428c00

Browse files
deanrasheeddeanrasheed
committed
Speed up numeric division by always using the "fast" algorithm.
Formerly there were two internal functions in numeric.c to perform numeric division, div_var() and div_var_fast(). div_var() performed division exactly to a specified rscale using Knuth's long division algorithm, while div_var_fast() used the algorithm from the "FM" library, which approximates each quotient digit using floating-point arithmetic, and computes a truncated quotient with DIV_GUARD_DIGITS extra digits. div_var_fast() could be many times faster than div_var(), but did not guarantee correct results in all cases, and was therefore only suitable for use in transcendental functions, where small errors are acceptable. This commit merges div_var() and div_var_fast() together into a single function with an extra "exact" boolean parameter, which can be set to false if the caller is OK with an approximate result. The new function uses the faster algorithm from the "FM" library, except that when "exact" is true, it does not truncate the computation with DIV_GUARD_DIGITS extra digits, but instead performs the full-precision computation, subtracting off complete multiples of the divisor for each quotient digit. However, it is able to retain most of the performance benefits of div_var_fast(), by delaying the propagation of carries, allowing the inner loop to be auto-vectorized. Since this may still lead to an inaccurate result, when "exact" is true, it then inspects the remainder and uses that to adjust the quotient, if necessary, to make it correct. In practice, the quotient rarely needs to be adjusted, and never by more than one in the final digit, though it's difficult to prove that, so the code allows for larger adjustments, just in case. In addition, use base-NBASE^2 arithmetic and a 64-bit dividend array, similar to mul_var(), so that the number of iterations of the outer loop is roughly halved. Together with the faster algorithm, this makes div_var() up to around 20 times as fast as the old Knuth algorithm when "exact" is true, and up to 2 or 3 times as fast as the old div_var_fast() function when "exact" is false. Dean Rasheed, reviewed by Joel Jacobson. Discussion: https://postgr.es/m/CAEZATCVHR10BPDJSANh0u2+Sg6atO3mD0G+CjKDNRMD-C8hKzQ@mail.gmail.com
1 parent 4dd3087 commit 9428c00

File tree

3 files changed

+371
-474
lines changed

3 files changed

+371
-474
lines changed

0 commit comments

Comments
 (0)