[This page is auto-generated; please prefer to read the article’s PDF Form.]
The hardware already provides some basic arithmetic operations on the 32-bit uint integers, that is, on the individual digits of our bigint. We will be using these digit-level hardware operations to help us implement the bigint-level operations. For the addition, subtraction, multiplication and division operations, we will take the algorithms for doing the same on decimal numerals which we learned in school, and adapt them for numerals with any arbitrary base B. These algorithms are sometimes referred as “Schoolbook” algorithms. Additionally, multiplication will also be implemented using Karatsuba Multiplication Algorithm.
We will denote the two operands by a = (ana−1ana−2…a1a0) and b = (bnb−1bnb−2…b1b0). Each digit ai (or bi) denotes the digit of a (or b) at position i; the LSD is at position 0. Since the base is B, the digits are in range 0 to B − 1.
The correctness proofs of these schoolbook algorithms for any base B are similar to that for decimal numerals.
Copyright © 2021 Nitin Verma. All rights reserved.