On the I/O complexity of hybrid algorithms for Integer Multiplication

2019/12/15 by Lorenzo De Stefani, De Stefani, Lorenzo
Computer Science · #Advanced Data Storage Technologies #Coding theory and cryptography #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences

paper · pdf · doi:10.48550/arxiv.1912.08045

openalex publication_date 2019/12/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/31

Abstract

Almost asymptotically tight lower bounds are derived for the Input/Output (I/O) complexity IO_A(n,M) of a general class of hybrid algorithms computing the product of two integers, each represented with n digits in a given base s, in a two-level storage hierarchy with M words of fast memory, with different digits stored in different memory words. The considered hybrid algorithms combine the Toom-Cook-k (or Toom-k) fast integer multiplication approach with computational complexity Θ(c_kn^{log_k (2k-1)}), and "standard" integer multiplication algorithms which compute Ω(n²) digit multiplications. We present an Ω((n/max\M,n₀\)^{log_k (2k-1)}(max\1,n₀/M\)²M) lower bound for the I/O complexity of a class of "uniform, non-stationary" hybrid algorithms, where n₀ denotes the threshold size of sub-problems which are computed using standard algorithms with algebraic complexity Ω(n²). As a special case, our result yields an asymptotically tight Θ(n²/M) lower bound for the I/O complexity of any standard integer multiplication algorithm. As some sequential hybrid algorithms from this class exhibit I/O cost within a O(k²) multiplicative term of the corresponding lower bounds, the proposed lower bounds are almost asymptotically tight and indeed tight for constant values of k. By extending these results to a distributed memory model with n₀ processors, we obtain both memory-dependent and memory-independent I/O lower bounds for parallel versions of hybrid integer multiplication algorithms. All the lower bounds are derived for the more general class of "non-uniform, non-stationary" hybrid algorithms that allow recursive calls to have a different structure.

Related

• The I/O complexity of hybrid algorithms for square matrix multiplication
• Communication-Optimal Parallel Standard and Karatsuba Integer\n Multiplication in the Distributed Memory Model
• How Fast Can We Multiply Large Integers on an Actual Computer?
• On the I/O Complexity of the CYK Algorithm and of a Family of Related DP Algorithms
• A Tight I/O Lower Bound for Matrix Multiplication