The surprising elegance of numerals and bigint routines.
Most languages have an etymologically old way of counting. Words like “one”, “two”, etc., have mostly meant what they now mean throughout history. Most languages also have their basic words stop at “ten”. The word “eleven” means “one left”, and while “left” is an unusual construction, the additive construction manifest in the Greek “hendeca” or “one ten” is more widespread linguistically.
In writing, it is common to represent numbers by special symbols. This is a bit odd in non-ideographic languages; why would the romans write “XIV” instead of “quattuordecim”? Presumably this evolved as a shorthand in writing tick marks; I, II, III are simple, and then at some point you say “I’m having trouble glancing at IIIII and knowing it’s not IIIIII” and so V is born. Unfortunately, this model doesn’t lend itself to mathematics.
In other languages you find similar bad models. For example, in Egyptian hieroglyphics there are symbols for one, ten, hundred, etc. but none for two, three, etc. The number twenty-three would be written with like “ten ten one one one”. Chinese had a motly arrangement with tickmarks up to four, unique glyphs for five through ten and hundred and thousnad, with ways for merging symbols to make intermediate values.
Babylonians had symbols for one and ten and arranged them like Egyptian (ten ten one one one) to get up to fifty-nine. But thereafter they had a powerful idea. To represent numbers between sixty and three thousand five hundred ninty-nine they wrote two numbers: the number of sixties and the number of singles. So three hundred sixty-five would be “‘one one one one one one’ ‘one one one one one’”: two counts in two adjoining boxes of their cuniform. Thus was one of the only scalable counting system: to get to a trillion you just had two put numbers in six consecutive boxes, no need to have a special word or symbol for trillion.
But it was the Hindu-Arabic system that first made mathematics simple. They had the surpringing good sense to have a unique symbol for each value between one and nine, and to also have a zero symbol. Like the babylonians, they used consecutive numbers to count singles, tens, hundreds, and so on; unlike the babylonians, there was no counting and no “leaving a spot blank.” Thus notation we all know and love, with ten as 10 instead of X, was born.
We don’t often dwell on it, but place-valued numerals make our life easy. To add, subtact or multiply all I need to do is know how to add, subtract, or multiply single digits. When I have something like 23 + 89 I simply check the 3 + 9 part, which is 12. I treat the 2 as part of the answer, the 1 as a “carry”, and move on with 2 + 8 + 1. There’s something similar with subtraction, though it is not often taught this way: 7 – 9 = (–1)(8), an eight with a negative one carry, also called a borrow. Thus in 37 – 19 I first get an 8 and a borrow of 1, then do (3 – 1 – 1) to get an answer of 18.
I’ve written before about starting at the other end, also made possible by place-value numbers.
algorithm In computers, the hardware base is 2 in place-value mathematics, but from a programmer’s perspective the base is actually 256, 65,536, or 4,294,967,296 depending on if you are working in bytes, words, or double words. For example, the following D routine I usually like to present more natural-language code but for messing with number types they don’t work well. I picked D as the cleanest systems-level language I know.
uint[2] times(uint a, uint b) {
ulong x = a;
x *= b;
return [cast(uint)(x>>32), cast(uint)(x)];
}
multiplies two base-4,294,967,296 digits to create a two-digit result. Thus, the standard elementary-school long multiplication adapted to computer code might look like
uint[] plus(uint[] a, uint[] b) {
uint n = a.length;
if (b.length > n) n = b.length;
n += 1;
uint[] ans = new uint[n];
uint carry = 0;
foreach(i; 0..n) {
ulong tmp = i < a.length ? a[i] : 0;
tmp += i < b.length ? b[i] : 0;
tmp += carry;
ans[i] = cast(uint)tmp;
carry = cast(uint)(tmp>>32);
}
while ( ans.length > 0 && ans[$-1] == 0 )
ans.length = ans.length - 1;
return ans;
}
uint[] times(uint[] a, uint b) {
uint[] ans = new uint[a.length+1];
uint carry = 0;
foreach(i; 0..a.length) {
ulong tmp = a[i];
tmp *= b;
tmp += carry;
ans[i] = cast(uint)tmp;
carry = cast(uint)(tmp>>32);
}
if (carry > 0) ans[$-1] = carry;
else ans.length = ans.length-1;
return ans;
}
uint[] times(uint[] a, uint[] b) {
uint[] ans;
foreach_reverse(digit; a) {
ans = [0u] ~ ans;
ans = plus(ans, times(b, digit));
}
return ans;
}
There’s no new magic in this; it’s simply the same thing we’ve been doing since grade school, only written in a way a computer understands. It is the everyday magic of positional numeral numbering.
Looking for comments…