Implementing Basic Arithmetic for Large Integers: Multiplication

[This page is auto-generated; please prefer to read the article’s PDF Form.]

Implementing Basic Arithmetic for Large Integers: Multiplication

Nitin Verma

June 18, 2021

This article is a continuation of the earlier one titled Implementing Basic Arithmetic for Large Integers: Introduction [1], which introduced how arbitrarily large integers along with basic arithmetic operations can be implemented via a program. It discussed the bigint structure for such large integers, the operations of addition, subtraction and printing, and also included the source code of all common internal methods.

Now we look into the multiplication operation, and discuss two algorithms for the same: Schoolbook Multiplication and Karatsuba Multiplication. We will be frequently using the concepts and deﬁnitions from [1]. As done earlier, the two operands of arithmetic operations will generally be denoted by a = (a_{n_a−1}a_{n_a−2}…a₁a₀) and b = (b_{n_b−1}b_{n_b−2}…b₁b₀), in base B numeral system.

[Next]