forked frompostgres/postgres
- Notifications
You must be signed in to change notification settings - Fork6
Commit4083f44
committed
Improve the performance and accuracy of numeric sqrt() and ln().
Instead of using Newton's method to compute numeric square roots, usethe Karatsuba square root algorithm, which performs better for numbersof all sizes. In practice, this is 3-5 times faster for inputs withjust a few digits and up to around 10 times faster for larger inputs.Also, the new algorithm guarantees that the final digit of the resultis correctly rounded, since it computes an integer square root withtruncation, containing at least 1 extra decimal digit before rounding.The former algorithm would occasionally round the wrong way becauseit rounded both the intermediate and final results.In addition, arrange for sqrt_var() to explicitly support negativerscale values (rounding before the decimal point). This allows theargument reduction phase of ln_var() to be optimised for large inputs,since it only needs to compute square roots with a few more digitsthan the final ln() result, rather than computing all the digitsbefore the decimal point. For very large inputs, this can be manythousands of times faster.In passing, optimise div_var_fast() in a couple of places where it wasdoing unnecessary work.Patch be me, reviewed by Tom Lane and Tels.Discussion:https://postgr.es/m/CAEZATCV1A7+jD3P30Zu31KjaxeSEyOn3v9d6tYegpxcq3cQu-g@mail.gmail.com1 parent8f3ec75 commit4083f44
File tree
3 files changed
+600
-49
lines changed- src
- backend/utils/adt
- test/regress
- expected
- sql
3 files changed
+600
-49
lines changed0 commit comments
Comments
(0)