←back to thread

Cherokee Numerals

(thereader.mitpress.mit.edu)
91 points horseradish | 2 comments | | HN request time: 0.428s | source
Show context
exporectomy ◴[] No.26521415[source]
Sounds like no loss. Invented and used by one person. We surely all invent and use our own personal ad-hoc notations for things when we don't happen to already know a conventional one.
replies(1): >>26522473 #
1. marksbrown ◴[] No.26522473[source]
Radix Positional notation is just one way to represent numbers. A way that is better for arithmetic than arbitrary numerals certainly. However it's important to remember that alternatives give us a comparison. A way of seeing implicit detail. Who knows, maybe someone will invent a better notation one day, and those future humans will look back and wonder why we didn't see the obvious solution!
replies(1): >>26525837 #
2. kragen ◴[] No.26525837[source]
If you really want a way that is better for everyday arithmetic, you're looking for residue number systems, like Maya tzolk'in–haab dates (if you disregard the wayeb', anyway) or Fliess's cocaine-fueled invention of biorhythms. For example, a five-digit RNS consisting of remainders from division by 5, 7, 8, 9, and 11 can uniquely represent the natural numbers up to what we call 27720.

You count as follows: 00000, 11111, 22222, 33333, 44444, 55550, 66661, 77702, 88013, 90124, X1230, 02341, 13452, and so on. Each digit proceeds to its successor independent of all the other digits, but wraps around at a different number. Similarly, when adding, subtracting, or multiplying, each digit is added, subtracted, or multiplied independently, modulo the base for its place; so 74702 + 17301 = 82203, because 7 + 1 = 8, 4 + 7 = 2 (mod 9), 7 + 3 = 2 (mod 8), 0 + 0 = 0, and 2 + 1 = 3. There's nothing to carry. (In our conventional notation, we would say 9247 + 4291 = 13538.) The computational advantage is even bigger for multiplication, although you need five different multiplication tables if you're going to memorize them, but for example X7313 × 38030 = 82030, where each digit is just the product of the corresponding digits.

It's easy to overlook the enormous performance advantage this implies for larger numbers. Multiplying two ten-digit numbers in place-value notation with the standard algorithm requires computing 100 two-digit products and then adding them up with 99 two-digit additions, a total of some 298 digit operations. Even with Karatsuba multiplication, it's only a little faster, though the advantage grows for larger numbers. But with an RNS, it only requires ten digit-to-digit multiplications, so you can multiply such pairs of numbers 30 times as fast, and moreover the RNS multiplication is embarrassingly parallel. As you can imagine, RNSs get substantial use in extremely recondite DSP applications.

Exact division, requiring divisibility, can be done with per-digit multiplicative inverses. For example, suppose you want to divide 46451 (which we would call 3876) by 48313 (which we would call 323). The first digit is of course 1, because 1 × 4 = 4. To compute 6 ÷ 8 in the 9s place, we need to use the multiplicative inverse of 8 in ℤ/9ℤ, which turns out to be 8 itself (8 × 8 % 9 = 1), so we multiply 6 × 8, most easily done with duplation and mediation (without a multiplication table) as 6 + 6 = 3, 3 + 3 = 6, 6 + 6 = 3. So our quotient is 13.... For the third digit, 4 ÷ 3, we again get lucky and the multiplicative inverse of 3 in ℤ/8ℤ is just 3, so it's 4 × 3: 4 + 4 = 0, 0 + 4 = 4. So it's 434... The fourth digit is 5 ÷ 1 = 5, since 1 is always its own multiplicative inverse. And the final digit is 1 ÷ 3; the multiplicative inverse of 3 mod 5 is 2, so that's 1 × 2 = 2. So our division result is 13452, which as you see above we conventionally call 12, which is correct.

Digit division by zero is less problematic than it sounds; 0 ÷ 0 = 0, and ∀x≠0: x ÷ 0 = ⊥, that is, fails to exist. That's because if your dividend has a 0 where the divisor doesn't, the dividend is not a multiple of the divisor at all — it's an exact multiple of one of the bases, and the divisor isn't.

Exact square roots are also relatively trivial, though they may involve many possibilities: √91141 = 81354 in the usual sense (√361 = 19), but other possibilities include 81351, 81321, 81554, 81154, and so on. The first of these corresponds to the fact that 16'651 (in our usual notation!) squares to 277'255'801, which is 10'002 × 27'720 + 361.

In base 10, it's easy to see if a number is divisible by 2 or 5, and slightly harder to tell if it's divisible by 9 or 11, or any of these multiplied by some power of 10, such as 1100 or 50; but beyond that you end up doing a fair bit of work. In an RNS, it's easy to see if a number is divisible by any factor of any of the bases, in this case 2, 3, 4, 5, 7, 8, 9, or 11, or any product of factors of two or more bases, which in this case is additionally 6, 10, 11, 12, 14, 15, 18, 20, 21, 22, 24, 28, 30, 33, 35, 36, 40, 42, 44, 45, 55, 56, 60, 63, 66, 70, 72, 77, 84, 88, 90, 99, 105, 110, 120, 126, 132, 140, 154, 165, 168, 180, 198, 210, 220, 231, 252, 264, 280, 308, 315, 330, 360, 385, 396, 420, 440, 462, 495, 504, 616, 630, 660, 693, 770, 792, 840, 924, 990, 1155, 1260, 1320, 1386, 1540, 1848, 1980, 2310, 2520, 2772, 3080, 3465, 3960, 4620, 5544, 6930, 9240, 13860 (in our usual notation!), and of course 27720.

There are some serious problems.

Without some kind of huffman coding, it's a little less efficient than a place-value system because of the need for varying numbers of symbols for the different places, although this problem becomes less serious with larger bases like 255 and 256. At some point—sooner if you're using large bases—you start needing a lot of distinct digits, though the Maya handled the analogous problem by writing each base-20 digit of the Long Count in base 5, and the Babylonians handled it by writing their base-60 digits in base 10. And needing separate multiplication tables and reciprocal tables for each digit is confusing.

Worse, though, it's hard to tell which of two numbers is larger than the other. The easiest way is to use the Chinese remainder theorem to convert them to a more conventional notation, which you can then compare lexicographically. In 01999, Brönnimann, Emiris, Pan, and Pion published an open-access article on "Sign determination in residue number systems" https://www.sciencedirect.com/science/article/pii/S030439759... which claims to have a better algorithm. Unfortunately I do not understand their paper.

And that makes it hard to compute everyday things like ⌊x÷3⌋.

If you were such a nutcase that you actually wanted to use an RNS for human computation, you'd probably be better off with a very small number of bases, like two (as in Fliess's original delusions about biorhythms and in tzolk'in dates) or three (as in some modern biorhythm scams).