Representing a 10 radix as a $10^k$ radix - How will the arithmetic and representation differ?

Question

Hi I am trying to understand how write code that deals with large integers greater than the predefined numeric datatypes (ie much greater than 64 bit integers).

I have observed that most libraries actually take a large base $10$ number and treat it as a base $10^9$ number.

For example take the base 10 number : $12345678901234567890123456789012345678901234567890$, if I were to represent this a base $10^9$ number, without introducing any new symbols for the digits (like A or $\alpha$) how would the arithmetic work ?

1. Would there be a change in the representation ? I think no, because if each digit is between $0$ and $10^9-1$ then the number should look the same as a base 10 number, provide we are still not using any esoteric symbols to denote the digits. Correct me if I am wrong.
2. How would the arithmetic work ? For example how would addition and multiplication work ? How will add and carry work ? Can some simple examples be shared ? I am really confused about how this works.

Answer 1

1. Of course , the value of the number does not depend on the base $b$ we choose to write it down in a base-$b$-system

2. Essentially , adding would work blockwise the carry is the sum (+ an eventual carry) modulo $10^9$. Mutltiplication would work analogue to the way it works in base $10$ , but the calculation would become really messy (Basically we would treat the blocks as digits , carries are still taken modulo $10^9$). So, it is better to apply the calculations in base $10$ and transform the result into the base-$10^9$-system which is easy.

Answer 2

I have observed that most libraries actually take a large base 10 number and treat it as a base $10^9$ number.

This is because computers work internally in binary. It requires 30 bits (which can represent a number between 0 and 1,073,741,823) to represent each base-billion “digit”. This easily fits in the widely-available 32-bit integer type, with two bits left over. A computer program could store decimal digits individually using 4 bits per digit, but this would allow only 8 digits instead of 9 to fit in a 32-bit integer.

Would there be a change in the representation?

If you mean the human-visible representation, probably not. It's impractical for a person to learn and distinguish a billion different digits, so most likely we'd continue spelling each base-billion “digit” with 9 decimal digits. Maybe add some punctuation to emphasize the fact that the numbers are grouped in units of 9, like:

000012345:678901234:567890123:456789012:345678901:234567890

If you mean the computer-internal binary representation, then yes, there is a difference. Representing the above number as a sequence of 32-bit integers storing base-billion digits gives:

00000000000000000011000000111001 00101000011101110011010111110010 
00100001110110010101000011001011 00011011001110100000110000010100 
00010100100110101010010000110101 00001101111110110011100011010010

While representing the individual decimal digits in binary gives:

0001 0010 0011 0100 0101 0110 0111 1000 1001 0000
0001 0010 0011 0100 0101 0110 0111 1000 1001 0000
0001 0010 0011 0100 0101 0110 0111 1000 1001 0000
0001 0010 0011 0100 0101 0110 0111 1000 1001 0000
0001 0010 0011 0100 0101 0110 0111 1000 1001 0000

How would the arithmetic work ? For example how would addition and multiplication work ? How will add and carry work ?

You just use the standard elementary-school algorithms for base-$b$ addition and multiplication, setting $b = 10^9$.

Addition is column by column, from least-significant to most-significant digit. If any column sum is $\ge b$, then subtract $b$ from the sum, and carry 1 to the next column.