Introduction
Long arithmetic is a collection of data structures and algorithms that allows us to work with numbers much larger than the standard integer types can store.
In this note, we use a simple representation based on decimal digits.
Data Structure
We will store a number as a vector<int>, where each element contains one decimal digit, and the digits are stored in reverse order.
For example, if
then we store it as
So the least significant digit comes first.
Output
To print a number, we traverse the vector from the last digit to the first.
Input
To convert an ordinary integer into our format, we repeatedly extract its last digit.
Normalization
After arithmetic operations, the result may contain extra leading zeros in the reversed representation. We remove them with a helper function.
Addition
To add two long numbers, we add their digits position by position and then propagate carries.
Subtraction
To subtract two long numbers, we assume that
Then we subtract digit by digit and handle borrows.
Multiplication
To multiply two long numbers, we simulate the usual school multiplication.