bigdecimal
bigdecimal copied to clipboard
BigMath.erf/erfc with Bitburst algorithm
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.
- Split x into
x0 + x1 + x2 + ... - Calculate
f(x0)with Taylor expansion offat0 - Calculate
f(x0 + x1)with Taylor expansion offatx0 - Calculate
f(x0 + x1 + x2)with Taylor expansion offatx0 + x1 - 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