Skip to content

Decimo v0.8.0

Choose a tag to compare

View all tags
@forfudan forfudan released this 25 Feb 20:06
· 20 commits to main since this release
v0.8.0
b572a44

20260225 (v0.8.0)

Library renamed from decimojo to decimo. The package name, import path, and all public references have been updated.

Decimo v0.8.0 is a profound milestone in the development of Decimo, marking the "make it fast" phase. There are two major improvements in this release:

First, it introduces a completely new BigInt (BInt) type using a base-2^32 internal representation. This replaces the previous base-10^9 implementation (now available as BigInt10) with a little-endian format using UInt32 words, dramatically improving the performance of all integer operations. The new BigInt implements the Karatsuba multiplication algorithm and the Burnikel-Ziegler division algorithm for sub-quadratic performance on large integers, and includes divide-and-conquer base conversion for fast string I/O. It also adds bitwise operations, GCD and modular arithmetic, and an optimized integer square root. Benchmarks show that the new BigInt outperforms Python's built-in int type in most cases, with up to 11× speedup for power operations and 5× for shift operations.

Second, it optimizes the mathematical operations for BigDecimal, bringing significant performance and accuracy improvements. The sqrt() function is re-implemented using the reciprocal square root method combined with Newton's method for faster convergence. The ln() function now supports an atanh-based approach with mathematical constant caching via MathCache. The exp() function benefits from aggressive range reduction for much faster convergence. The root() function gains rational root decomposition and a direct Newton method. The to_string() method is aligned with CPython's decimal module formatting rules for scientific notation and trailing zeros. The BigUInt layer also gains the Toom-Cook 3-way multiplication algorithm. Benchmarks indicate that BigDecimal operations beat Python's decimal module in speed, especially for high-precision calculations (e.g., division up to 915× faster, sqrt 3.5× faster on average).

⭐️ New in v0.8.0

BigInt (base-2^32):

  1. Implement the BigInt (BInt) type using a base-2^32 internal representation with little-endian UInt32 words. This is a completely new implementation optimized for binary computations while supporting arbitrary precision (PR #133, #134, #135, #141).
  2. Implement the Karatsuba multiplication algorithm for BigInt, reducing time complexity from $O(n^2)$ to $O(n^{\log_2 3})$ for large integers (PR #142).
  3. Implement the slice-based Burnikel-Ziegler division algorithm for BigInt, providing sub-quadratic division performance for the base-2^32 representation (PR #144).
  4. Implement divide-and-conquer base conversion for BigInt.to_string(), significantly improving string conversion speed for large integers (PR #145).
  5. Implement bitwise operations (__and__, __or__, __xor__, __lshift__, __rshift__, __invert__) and true in-place bitwise operations for BigInt (PR #150, #151).
  6. Implement gcd(), extended_gcd(), mod_inverse(), and mod_pow() for BigInt, providing number-theoretic functions (PR #152, #153).
  7. Implement an optimized sqrt() for BigInt using Newton's method with a good initial approximation, delivering 1.39× average speedup over Python (PR #155).

BigDecimal:

  1. Implement the quantize() function for BigDecimal to format decimal numbers to a specified number of decimal places, similar to Python's Decimal.quantize() (PR #126).
  2. Implement true in-place arithmetic functions (__iadd__, __isub__, __imul__) for BigDecimal to reduce memory allocations during repeated operations (PR #162).
  3. Implement methods to initialize BigInt and BigDecimal from Python objects, enabling seamless interoperability with Python's int and decimal.Decimal (PR #129).

Core:

  1. Add ROUND_CEILING and ROUND_FLOOR rounding modes to RoundingMode, bringing the total to six modes (PR #164).

TOMLMojo:

  1. Implement all core TOML v1.0 specification features for TOMLMojo, including inline tables, arrays of tables, dotted keys, multiline strings, and all value types (PR #140).

🦋 Changed in v0.8.0

BigInt:

  1. Rename the previous base-10^9 BigInt to BigInt10. The alias BInt now refers to the new base-2^32 BigInt type (PR #143, #154).
  2. Optimize from_string() for BigInt with an improved string parser and divide-and-conquer approach for fast base conversion (PR #146, #147, #148).
  3. Optimize to_string() for BigInt with divide-and-conquer base conversion, achieving 6× average speedup over Python (PR #149).

BigDecimal:

  1. Re-implement sqrt() for BigDecimal using the reciprocal square root method combined with Newton's method, delivering faster convergence and better accuracy for high-precision calculations (PR #163).
  2. Optimize ln() and exp() for BigDecimal with mathematical constant caching via MathCache and improved handling of one-word dividends (PR #160).
  3. Apply aggressive range reduction for exp() to achieve faster convergence at high precision (PR #167).
  4. Implement direct Newton method for general root() calculation, replacing the previous iterative approach (PR #161).
  5. Add rational root decomposition to root() and an atanh-based approach to ln() for improved accuracy and convergence (PR #168).
  6. Optimize true_divide_general() to correctly account for existing word surplus in the dividend (PR #158).
  7. Optimize division with truncation and align to_string() output with CPython's decimal module formatting for scientific notation and trailing zeros (PR #165).

BigUInt:

  1. Implement the Toom-Cook 3-way multiplication algorithm for BigUInt, improving performance for large number multiplications (PR #166).
  2. Unify and refine initialization methods for BigUInt with consistent constructors and improved validation (PR #127, #128, #131).

Core:

  1. Improve naming consistency between types, ensuring uniform method names across BigInt, BigDecimal, and Decimal128 (PR #164).
  2. Make RoundingMode type implicitly copyable for easier usage in function signatures (PR #125).

🛠️ Fixed in v0.8.0

  • Fix string formatting for BigDecimal to match Python's decimal module formatting rules, including correct scientific notation thresholds and trailing zero handling (PR #163, #165).

📚 Documentation and testing in v0.8.0

  • Refactor the testing files for Decimal128 (PR #132).
  • Refactor the benchmarking system to use TOML-based input files with configurable precision (PR #139, #159).
  • Update document links for the repository organization move to forfudan (PR #130).
  • Update documents and add the planning files for BigInt and BigDecimal optimization roadmaps (PR #157).

What's Changed

  • [decimal][rounding] Make RoundingMode type implicitly copyable by @forfudan in #125
  • [decimal] Implement quantize() function for BigDecimal by @forfudan in #126
  • [docs] Update the links in documents due to moving repo to an organization by @forfudan in #130
  • [integer][bigint] Unify initialization methods for unsigned integers by @forfudan in #131
  • [test] Refactor the testing files for Decimal128 by @forfudan in #132
  • [integer] Create basic methods for BigBinaryInt type by @forfudan in #133
  • [integer] Rename BigBinaryInt as BigInt2 by @forfudan in #134
  • [integer] Implement comparison and arithmetic routines for big binary int by @forfudan in #135
  • [bench] Refactor benchmarking system and use toml files as input by @forfudan in #139
  • [integer] Implement all necessary operations for big binary integer by @forfudan in #141
  • [integer] Implement Karatsuba algorithm for BigInt2 by @forfudan in #142
  • [integer] Rename BigInt as BigInt10 by @forfudan in #143
  • [integer][BInt2] Implement slice-based Burnikel-Ziegler algorithm for 2^32-based integer by @forfudan in #144
  • [integer][BInt2] Implement divide-and-conquer base conversion from BInt2 to String by @forfudan in #145
  • [integer][BigInt2] Improve the performance of from_string() and refactor the string parser by @forfudan in #146
  • [integer][BigInt2] Update conversion from 10-based integer to 2-based integer by @forfudan in #147
  • [integer][BigInt2] Optimize both the simple and D&C paths for from_string by @forfudan in #148
  • [integer][BigInt2] Optimize to_string() by @forfudan in #149
  • [integer][BigInt2] Add bitwise operations and true inplace operations by @forfudan in #150
  • [integer][BigInt2] Implement in-place bit-wise operations by @forfudan in #151
  • [integer][BigInt2] Implement GCD, extended GCD, and modular arithmetic by @forfudan in #152
  • [integer][BigInt2] Add methods for GCD, extended GCD, etc by @forfudan in #153
  • [integer] Rename BigInt2 as BigInt and bind the alias BInt to it by @forfudan in #154
  • [integer] Refactor sqrt() and significantly increase the speed by @forfudan in #155
  • [integer][docs] Update several documents and add the planning file for BigDecimal optimization by @forfudan in #157
  • [decimal] Update true_divide_general() to account for existing word surplus in dividend by @forfudan in #158
  • [bench] Add precision in toml files for benches by @forfudan in #159
  • [decimal] Improve ln and exp with caching and new function handling one-word dividend by @forfudan in #160
  • [decimal] Use direct Newton method for general root calculation by @forfudan in #161
  • [decimal] Implement true in-place functions for BigDecimal type by @forfudan in #162
  • [decimal] Refactor sqrt() + fix string formatting to match Python's decimal rule by @forfudan in #163
  • [core] Add more rounding modes + improve naming consistency between types by @forfudan in #164
  • [decimal][core][test] Division truncation optimization + to_string() CPython alignment + test refactor by @forfudan in #165
  • [biguint] Implement Toom-Cook 3-way algorithm for BigUInt multiplication by @forfudan in #166
  • [decimal] Apply aggressive range reduction for exp by @forfudan in #167
  • [decimal] Add rational root decompostion to root() and add atanh approach to ln() by @forfudan in #168

Full Changelog: v0.7.0...v0.8.0

Contributors

forfudan
Assets 3
Loading