KEMBAR78
Faster exp calculation by tompng · Pull Request #399 · ruby/bigdecimal · GitHub
Skip to content

Conversation

@tompng
Copy link
Member

@tompng tompng commented Aug 10, 2025

Use exp(x) = exp(x.round(k)) * exp(x - x.round(k)).
exp(x.round(k)) is fast because calculation of x**n is fast.
exp(x-x.round(k) is fast because x**n/n! converges fast.

BigMath.exp(1, 10000);
# 0.062810s → 0.062706s (no difference)

BigMath.exp(BigDecimal(3).div(7, 1000), 1000)
# 0.01463742s → 0.00326753s

BigMath.exp(BigDecimal(3).div(7, 10000), 10000)
# 8.571512s → 0.552467s

Why this optimization?

Currently, exp(x) uses exp(x/10**cnt)**(10**cnt) to make |x|<1.
We can make |x| even smaller, but the computation cost of y**10 is large O(prec**2).
exp(x) = exp(x.round(k)) * exp(x - x.round(k)) might not be optimal for the long run, but considering the simplicity of the change, improvement is significant and worth enough.

- y = _exp_taylor(x, prec2)
+ x_small_prec = x.round(Integer.sqrt(prec2))
+ y = _exp_taylor(x_small_prec, prec2).mult(_exp_taylor(x.sub(x_small_prec, prec2), prec2), prec2)

Use exp(x) = exp(x.round(k)) * exp(x - x.round(k)).
exp(x.round(k)) is fast because calculation of x**n is fast.
exp(x-x.round(k) is fast because x**n/n! converges fast.
@tompng tompng marked this pull request as ready for review September 7, 2025 11:54
@tompng tompng merged commit 69d7641 into ruby:master Sep 11, 2025
81 checks passed
@tompng tompng deleted the faster_exp branch September 11, 2025 13:35
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

1 participant