↑Go to Month

Radix, Roman, Spreadsheet

###
Description
A dive into numeral systems that have no zero.
Publish Date
Calculating Date
Tags
[[radix], [competitive programming], [cpp]]
###

I was troubled by this problem that described a numeral system that had no zero. There existed two symbols: '4' and '7' in the system, but neither of them represented null, which means that if I wrote down a side-by-side comparison of it with the binary system, it would result in the following (for the sake of readability, I replaced '4' and '7' with '1' and '2' respectively):

Base 10		Base 2		Base 2 (w/o 0)
0			0			undefined
1			1			1
2			10			2
3			11			11
4			100			12
5			101			21
6			110			22
7			111			111
and so on

Since I was unfamiliar with base systems without zero (seriously, what?), I went down the rabbit hole. The first result I got from my search engine was "Roman Numerals", which made sense since it didn't have zero. Then I read more into it, and I found another result that, at first glance, looked completely unrelated - How to convert a column number (e.g. 127) into an Excel column (e.g. AA). Then it occurred to me that Excel columns did not have the concept of nothing. A-Z represent 1 to 26. In other words, the question is asking to convert Base 26 to Base 26 w/o 0. Let's check... yep someone has responded with a checked answer, hopefully. The code is as simple as the following:

while(from > 0)
{
	int modu = (from - 1) % MODULO;
	buffer += char_set[modu];
	if(modu == MODULO - 1)
	{
		from -= modu;
	}
	from /= MODULO;
}
reverse(buffer);

However, I didn't quite understand the fifth line. It turned out to be easier than met the eye. During each iteration, we are checking a specific digit of the number in base MODULO since division acts as a single right shift operation if the denominator is the same as the nn of base-nn. In that digit, it is evident we are converting from 0n10 \sim n-1 to 1n1 \sim n; however, notice 00 should become nn (index in the character set is n1n-1), hence line 3. After that, the if statement only applies to digit 00. Notice if we hadn't applied this operation, we'd be left with one less offset each time we come across 00. Remember how 1002100_2 becomes 12wo012_{wo0}, so we'd count one more digit if we didn't subtract it with MODULO - 1.

Anyway, that's enough yapping and I almost forget what I'm writing about. See you in the next post.