bigdecimal icon indicating copy to clipboard operation
bigdecimal copied to clipboard

BigMath.erf/erfc with Bitburst algorithm

Open tompng opened this issue 3 weeks ago • 0 comments

Attempt to implement bitburst-algorithm version of BigMath.erf and BigMath.erfc

This pull request is a proof of concept, not meant to merge. Considering the complexity of the implementation, (about 1/3 of math.rb code are about erf/erfc), I'm not sure if this improvement is worth maintaining.

Requires #407, #433 and #434

Bit-burst algorithm implementation

Repeatedly apply Taylor expansion at increasing x.

  1. Split x into x0 + x1 + x2 + ...
  2. Calculate f(x0) with Taylor expansion of f at 0
  3. Calculate f(x0 + x1) with Taylor expansion of f at x0
  4. Calculate f(x0 + x1 + x2) with Taylor expansion of f at x0 + x1
  5. So on...

Each Taylor expansion calculation uses binary-splitting method. Details are described in source code comment.

Benchmark

Performance compared with initial implementation of erf/erfc (#357) (multiplication-improvement(#407) exp-improvement(#433) pi-improvement(#434))

# Erf of integer

BigMath.erf(10, 10000)
# processing time: 0.397290s → 0.114477s
BigMath.erf(10, 100000)
# processing time: 18.833298s → 1.272269s

# Erf of full-precision number

BigMath.erf(BigDecimal(2).sqrt(10000), 10000)
# processing time: 0.984326s → 0.442207s
BigMath.erf(BigDecimal(2).sqrt(100000), 100000)
# processing time: 100.310177s → 7.004699s

# Erfc of integer

BigMath.erfc(1234, 10000)
# processing time: 0.240464s → 0.135643s
BigMath.erfc(1234, 100000)
# processing time: 20.379666s → 1.500936s

# Erfc of full-precision number

BigMath.erfc(1234 + BigDecimal(4).div(7, 10000), 10000)
# processing time: 5.780519s → 0.739505s
BigMath.erfc(1234 + BigDecimal(4).div(7, 20000), 20000)
# processing time: 26.253593s → 2.068693s

tompng avatar Dec 01 '25 18:12 tompng