# Speeding up decimal multiplication

**Authors:** Viktor Krapivensky  
**arXiv:** [2011.11524](https://arxiv.org/abs/2011.11524)  
**Date:** 2020-11-23  
**Summary page:** https://www.summarizepaper.com/en/paper/2011.11524v1/

## Key points

- Viktor Krapivensky explores decimal multiplication in base $10^N using number-theoretic transform (NTT) algorithms
- Achieves 3x to 5x speedup compared to the mpdecimal library through portable techniques
- Introduces a cache-efficient algorithm for in-place $2n \times n$ or $n \times 2n$ matrix transposition, crucial for scenarios like the "six-step algorithm"
- Discusses decision-making process for choosing prime moduli based on factors like machine word length (w), maximum multiplicand length (M), and desired simplicity in modulo addition operations
- Calculation of λ(ℓ) helps determine if additional prime moduli are necessary based on specific parameters like µ and M
- Analysis of how λ(ℓ)/ℓ impacts computational efficiency by utilizing multiple transforms with different prime moduli
- Detailed calculations showcase how different configurations affect performance and digit handling during decimal multiplication

## Summary

In the paper "Speeding up decimal multiplication," Viktor Krapivensky explores the task of multiplying two numbers in base $10^N$ through the use of number-theoretic transform (NTT) algorithms. By employing portable techniques, the author achieves a significant 3x to 5x speedup compared to the mpdecimal library. The implementation details and potential optimizations are discussed in depth, shedding light on the efficiency gains achieved. One notable contribution of the paper is the introduction of a cache-efficient algorithm for in-place $2n \times n$ or $n \times 2n$ matrix transposition. This algorithm proves crucial in scenarios like the "six-step algorithm" variation of the matrix Fourier algorithm, filling a gap in existing knowledge within this domain. Furthermore, Krapivensky delves into the decision-making process behind choosing prime moduli for decimal multiplication. By considering factors such as machine word length (w), maximum multiplicand length (M), and desired simplicity in modulo addition operations, the author provides insights into selecting an optimal number of primes (ℓ). The calculation of λ(ℓ) helps determine if additional prime moduli are necessary based on specific parameters like µ and M.

The analysis also touches upon how λ(ℓ)/ℓ impacts computational efficiency, offering a glimpse into the potential speedup factor achieved by utilizing multiple transforms with different prime moduli. Through detailed calculations for various values of µ and M, Krapivensky showcases how different configurations affect performance and digit handling during decimal multiplication. Overall, "Speeding up decimal multiplication" not only presents novel approaches to enhancing computational efficiency but also offers valuable insights into prime modulus selection strategies and their impact on overall performance in decimal multiplication algorithms.