Development plan

[mrkn]

I opened this issue to outline the development plan for bigdecimal, especially for our new co-maintainer, @tompng. Thank you, @tompng, for joining the project.

Over the past several years, I have been largely inactive in bigdecimal development because I rarely have more than 30 minutes of free time each day for open-source work as hobby. Two years ago, I expected to resume development within 2-3 years, but the current constraints are likely persist for at least another three years. Consequently, I have decided to share my thoughts on bigdecimal's roadmap here.

The roadmap below is compiled from my notes and memory. Because there are many tasks I wanted to do and I want to record them accurately here, I will continue refining this issue over the coming days.

In the first iteration, I describe only the highest-priority items; the others are merely listed for reference. I will update this issue several times as I flesh out the remaining topics.

Basic policy

Development must follow these principles:

• Avoid converting values to base-2 representations for computation whenever possible.
• Minimize CPU time and memory usage.
• Keep external dependencies to an absolute minimum.

High-priority tasks

Tests for high-precision values

Verify each high-precision result with either assert_in_delta or assert_in_epsilon, explicitly passing an appropriate BigDecimal to the delta or epsilon parameter to avoid converting to Float and maintain accuracy.

✅ Improve division performance

Resolve issue #222 (details on the current slowdown will be added later).

TODOs

Improve multiplication performance

• Implement Karatsuba multiplication.
• Implement Toom-3 multiplication.
• Implement NTT-based multiplication with 2 or 3 primes.

Further improve division performance

• Implement Karatsuba division.

Improve sqrt performance

• Implement Karatsuba sqrt.

Trigonometric functions

• Increase the accuracy of cos and eliminate unnecessary extra-digit computation.
• Use the identity $\cos(x) = \cos(x - \pi)$ for $|x| \ge \pi$.
• Rewrite sin as $\sin(x) = \sqrt{1 - \cos^2(x)}$ except when $x$ is near zero.
• Adopt Ziv's loop in the proposed tan implementation (see Add support for tangent function #231) to guarantee precision.

Support all the functions in Math module

(I'll outline this later)

etc.

(I'll add additional TODO items and describe them in detail later)

[tompng]

Mult and div performance

• NTT multiplication and Newton-Raphson division #407
• Not planned to implement karatsuba/toom-3,4,5,etc for now for code maintainability reason.

SQRT performance

• Rewrite BigDecimal#sqrt in ruby with improved Newton's method #381

Trigonometric functions performance

• Improve taylor series calculation of exp and sin by bit burst algorithm #433

Support all the functions in Math module

• Add support for tangent function #231
• Implement major math functions #336
• Implement major math functions #336
• Implement BigMath.gamma and BigMath.lgamma #451
• Implement BigMath.frexp and ldexp with exponent of 10 #448