The protoshadok number system

We’re so used to our positional notation system that we can’t really figure out how to write numbers in other systems. Most of the ancient systems are either tedious, complicated, or both. Zero, of course, plays a central role within that positional system. But is it indispensable?

shadok

In one of my classes, I discuss a lot of different numeration systems (like Egyptian, Babylonian, Roman and Greek) to explain why the positional system solves all, or at least most, of these systems’ problems. I even give the example of Shadok counting (in french) to show that the basis used isn’t that important (it still has to be greater than one, and, while not strictly necessary, preferably a positive integer). But can we write numbers in a positional system without zero?

The usual “to base 10” routine would look something like this:

std::string to_decimal(int n)
 {
  std::string t;
  do
   {
    t.insert(t.begin(),'0'+(n%10));
   } while (n/=10);

  return t;
 }

The function extracts, one by one, a digit and prepends it to the string. But this function uses zero and behaves as we are used to. It can write a number like 204120, and its interpretation is unambiguous.

Now, how do we modify this routine so that it doesn’t use a zero but still writes down unambiguous numbers?

Let’s get back to the Shadoks. In the video, we see that before using a base-4 positional system, which includes a zero, the Shadoks used numerals for one, two, three and four, but no zero. Let’s see how a Shadok could have written numbers without using zeroes.

gabuzomeu

Without a zero, zero can’t be written down, so the numbers start at one, we’re in the real of natural numbers. We have only four symbols, let’s say a,b,c,d. The first numbers are, of course, a, b, c, and d, which are 1, 2, 3, and 4. Then we have aa, ab, ac, ad, which are 5, 6, 7, 8. Then ba, bc,… you get the idea.

In the above code snippet, we use modulo to extract a digit, but modulo extracts a number from 0 to base-1, whichever base we use. What we need to write without a zero is an operation that extracts a number from 1 to base, inclusive, for the next digit. In the Shadok system, it would extract 1, 2, 3, or 4. Turns out, modulo can still serve:

std::string to_protoshadok(int n)
 {
  std::string t;

  while (n)
   {
    int r = n % 4;
    r=r ? r : 4;
    t.insert(t.begin(),'a'+r-1); 
    n-=r;
    n/=4;
   }

  return t;
 }

There’s likely a better implementation of the two operations r=n%4 and r=r ? r : 4, but it will suffice for now. Indeed, it outputs the desired result:

1	a
2	b
3	c
4	d
5	aa
6	ab
7	ac
8	ad
9	ba
10	bb
11	bc
12	bd
13	ca
14	cb
15	cc
16	cd
17	da
18	db
19	dc
20	dd
21	aaa
22	aab
23	aac
...

*
* *

This system works, but is very counter-intuitive. In this system, 8 is not written as 2 times 4, but as 1 times 4 plus 4. But simple arithmetic, such as addition, seems to remains pretty much the same except that borrow and carry rules vary only slightly. It’s probably not that practical, but it shows that we can write numbers in a positional system without a zero.

2 Responses to The protoshadok number system

  1. o0o says:

    This idea has been rediscovered many times… afaict, the “official” name for it is “Bijective numeration”: https://en.wikipedia.org/wiki/Bijective_numeration

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: