Cistercian Number Counter

Hey y’all, I’ve been thinking a lot about cistercian numbers/numerals lately and decide to make a very simple counter to demonstrate they work. The best way to understand them is to just go through some examples really, and that’s the purpose of this counter. Left and right decrement and increment the counter by 1, respectively, while down and up decrement and increment as fast as they are able relative to frame rate.
There’s a simple chart in my github if you want a reference as well, thinking I may add it somewhere in-game.

At any rate, enjoy! It’s nothing to fancy but the code is kinda neat too, demonstrates how the pattern logic works.

cistercia.ino-arduboy.hex (29.4 KB)

Github Source

4 Likes

What are Cistercian numbers?

They’re a numeral system that was used by Cistercian monks in the 15th and 16th 13th through the 15th century particularly. The concept is that by compounding certain numerals together you could represent higher numbers, on a line with with units, tens, hundreds, and thousands being different quadrants (With a vertical line in the middle representing zero, the area to the top right of the line is your units, the top left your tens, bottom right your hundreds, and bottom left your thousands) thus there need only be separate symbols for 1,2,3,4, and 6, because 5,7,8, and 9 can be represented by a combination of the other characters, placed atop each other. It’s somewhat difficult to explain (clearly) but that’s why I made this counter pretty much, it’s easiest to understand how they work through exploration instead of explanation.

Besides the fact that they look neat and somewhat sci-fi, the convenient thing about them is that any value from 0-9999 can be represented using only one character space.

2 Likes

If I’m understanding this right, they’re effectively the 22-bit equivalent of a 7-seg display, in which case 9999 is nowhere near the value range they could actually achieve. Theoretically if you included all the symbol variants that aren’t valid by the existing rules, the system could be extended to represent 4,192,304 (222) values.

(By the way, I can think of a few ways the logic could be improved if you’re interested.)

1 Like

I’d love to hear! The code right now is essentially how my own brain tends to process it, I’d be very interested to learn how it could be improved!

1 Like

I had a quick go at cutting it down, and I’ve ended up with something that’s quite a few steps ahead so I’ll have to break it down a bit before I drop the link…

Firstly I was going to suggest replacing your `if` chain in `drawUnits` with a `switch` because it’s typically clearer when you’re doing something for each individual value. This wouldn’t extend to `drawTens` and so forth under the current system, but it does after the final change which I’ll mention later…

My second suggestion was going to be to pass the value in as an argument to each of `drawUnits`, `drawTens` et cetera because most of the time passing an argument is cheaper than modifying a global.

A global variable always has to be written back immediately after it’s modified because the compiler can’t guarantee that there isn’t some other function/process that’s going to need its value (or at least, not without a lot of extra processing and then people would complain about long compile times). In contrast, local variables and non-reference arguments can be kept in registers, so the compiler can optimise them better.

(In other words, all that adding and subtracting actually has an unintentional extra cost in this case, because you’re using a global.)

Now for the big savings I worked out after spending a few minutes with the code…

The first big thing was identifying the following three properties:

• `cistercian6` is always drawn when the value is `>= 6`, thus you can cut out several of the draw calls by just having an `if(value >= 6) Sprites::drawSelfMasked(x, y, cistercian6, 0);`
• `cisterian2` is always drawn for values `>= 8`, so that’s another chance to reduce the number of tests/calls
• `cistercian1` is always draw for odd values other than `3`, which is yet another simplification.

Together those three rules simplify `drawUnits` to:

``````void drawUnits(uint8_t x, uint8_t y, uint8_t value)
{
switch(value)
{
case 0:
break;

case 2:
break;

case 3:
break;

case 4:
case 5:
break;
}

if(isOdd(value) && (value != 3))

if(value >= 6)

if(value >= 8)
}
``````

Where `isOdd` is defined as:

``````bool isOdd(uint8_t value)
{
return ((value % 2) != 0);
}
``````

Function calls are expensive on AVR (the Arduboy’s chip architecture), so reducing the number of them always helps reduce progmem.

The second big saving was to introduce a variation of function I’ve used and provided for a few other games:

``````void extractDigits(uint8_t (& digits)[4], int16_t value)
{
uint16_t divisor = 1000;

for(uint8_t index = 0; index < 4; ++index)
{
digits[index] = (value % 10);
value /= 10;
}
}
``````

This decomposes an integer into the lowest 4 decimal digits and stores those values into an array. (The odd `uint8_t (& digits)[4]` syntax is how you create a mutable reference to a 4-element array.)

After which, it’s possible to rewrite `drawTens`, `drawHundreds` and `drawThousands` to effectively be the same as `drawUnits`, with the only difference being which sprites get drawn.

Then by creating a function to tie the four together, like so:

``````void drawCistercianValue(uint8_t x, uint8_t y, int16_t value)
{
uint8_t digits[4];

extractDigits(digits, value);

drawUnits(x, y, digits[0]);
drawTens(x, y, digits[1]);
drawHundreds(x, y, digits[2]);
drawThousands(x, y, digits[3]);
}
``````

The overall result achieves the same effect, but around 1200 bytes cheaper

Before:
Sketch uses 10594 bytes (36%) of program storage space. Maximum is 28672 bytes.
Global variables use 1236 bytes (48%) of dynamic memory, leaving 1324 bytes for local variables. Maximum is 2560 bytes.

After:
Sketch uses 9222 bytes (32%) of program storage space. Maximum is 28672 bytes.
Global variables use 1234 bytes (48%) of dynamic memory, leaving 1326 bytes for local variables. Maximum is 2560 bytes.

You can see the final version here:

I can think of two more potential savings, but I don’t have time to write test them at the moment because I have to dash off:

• Merging the images into a single array and using the `frame` parameter of `drawSelfMasked` would save a few bytes (there should be a thread or two about this floating around the forum if you’re interested)
• Merging all four functions into a single function that takes an extra parameter that identifies which set of symbols to use, which should save quite a large number of bytes

It possibly wouldn’t save memory, and it may or may not be slower, but I’d like to also point out that theoretically all the symbols could be drawn with just the line drawing functions.

1 Like

This is really neat! The extractDigits function is clever, I was trying to figure something like that out during development before scrapping it, so it’s really cool to see a version that works!

I probably will put the cistercian sprites all into a single array, I thought about doing so not just to save space but because I like the way it looks in the code better, but was too lazy at the time of development. I also thought about using the line drawing functions to draw them just cuz it could be done, but decided against it so the code was easier to understand from a glance.

1 Like

I ended up thinking about this a bit more because I’ve been doing some tangentially related things…

Firstly, a minor correction: 20-bit, 5 per digit.
(220 would be 1,048,576 possible variations.)

When I made the 22-bit calculation I was under the impression that there were two extra lines, and it only just occurred to me those lines aren’t used.

Secondly, following the 7-seg logic, I thought of another approach that may be even cheaper.

To understand this properly you’ll need to know what binary and bit shifting are. You should still be able to understand without understanding progmem though, if you just pretend the `pgm_read_byte` is a normal array lookup.

``````constexpr uint8_t pattern0 = 0;
constexpr uint8_t pattern1 = (1 << 0);
constexpr uint8_t pattern2 = (1 << 1);
constexpr uint8_t pattern3 = (1 << 2);
constexpr uint8_t pattern4 = (1 << 3);
constexpr uint8_t pattern6 = (1 << 4);

constexpr uint8_t bitPattern[10] PROGMEM
{
pattern0,
pattern1,
pattern2,
pattern3,
pattern4,
pattern1 | pattern4,
pattern6,
pattern6 | pattern1,
pattern6 | pattern2,
pattern6 | pattern2 | pattern1,
};

void drawUnits(uint8_t x, uint8_t y, uint8_t value)
{

if((pattern & pattern1) != 0)

if((pattern & pattern2) != 0)

if((pattern & pattern3) != 0)

if((pattern & pattern4) != 0)

if((pattern & pattern6) != 0)
}
``````

Essentially, the 0-9 value is used as an index into an array that retrieves a byte with a bit pattern that represents the lines that compose one of the four sub-glyphs of the numeral. It’s then just a matter of testing each bit and drawing the appropriate line if required.

Exactly like a 7-seg display, but instead it’s 5-seg, and only 1/4 of the numeral. You’d need the same thing for each of the thousands, hundreds, tens and units - but the good news is you can reuse the pattern array and just swap out the sprite set.

If I get time later on I might piece together a version using this, purely because I’m curious about whether or not it would be cheaper, and if so by how much.

I have the fortune (some would say misfortune) of knowing C++ in excruciating detail.

Thinking about it again, whether line drawing would be cheaper depends entirely on how expensive the maths would be for calculating the positions of the lines.

The diagonal lines would almost certainly be more expensive, but a hybrid approach using the fast horizontal and vertical line functions might be cheaper.

Sorry if I’ve ended up taking this horribly off-piste, but this particular scenario is at an intersection of several of my interests*, so it’s hard to ignore the impulse to get involved.

* (In no particular order: shrinking code, symbols/glyphs/writing systems, interesting logic/algorithm conundrums and esoteric/arcane things in general).

1 Like

Fantastic! I thought there might be a way to go about this using bit shifting for a very minimal approach, but I had only a vague idea, as I’m not super familiar with it and only started understanding binary a few months ago. So to see this is really impressive!!

Don’t worry about it! This is all very interesting and fun to follow, and feels very relevant! Cistercian numbers are about efficiency so having code that reflects that feels natural as well.

Did a refresher on bitwise operations and understand the code a bit better now (no pun intended), and while I understand most of what’s going on, I’m not sure how you would go about adding the tens, hundreds, and thousands. As I understand, if the sprites were just swapped out and use the same pattern array, then it would just draw cistercian 10, 20, 30… at the same time as 1, 2, 3…
How would we make sure the tens flips over only every ten counts? I’ve been playing around with it but can’t quite figure it out

Not at the same time, but in the same way.

It would be used exactly the same as the previous revision where the 4 digits are extracted and fed to the relevant functions (`drawUnits`, `drawTens` et cetera), but the functions would be implemented using this bitwise approach instead of the `switch` and three branches approach.

By ‘swapped out’ I mean you can just copy the function and replace the sprites that are being drawn.

You could create a single function with a parameter that dictates which set of sprites to use, but that can always be done afterwards. Either way the net result should be the same.

This is still just a rendering algorithm, as it was in your original and in the current revision. All the arithmetic is normal binary arithmetic as performed on integer datatypes. The logic is all in how those integers are rendered.

1 Like

Here’s an implementation of what I mean:

Not a massive saving in the grand scheme of things, but it’s still fairly significant.

Before:
Sketch uses 9222 bytes (32%) of program storage space. Maximum is 28672 bytes.
Global variables use 1234 bytes (48%) of dynamic memory, leaving 1326 bytes for local variables. Maximum is 2560 bytes.

After:
Sketch uses 9148 bytes (31%) of program storage space. Maximum is 28672 bytes.
Global variables use 1234 bytes (48%) of dynamic memory, leaving 1326 bytes for local variables. Maximum is 2560 bytes.

1 Like

Oh I get it now! That’s really neat, it’s awesome to see it laid out this way. Ever since I first found out about Cistercian numerals, I’ve been wondering how it could be rendered to something in a bit-wise manner. Somewhere out there there’s a universe where Cistercian is the mainstream and Arabic is archaic, can’t help but wonder what their computers are like. And the 1% difference is pretty decent!

1 Like

If you thought that was neat, here’s the hat-trick:

I fused all the arrays together (apart from the zero digit) and then I fused the four variations of the rendering functions together, as I mentioned was possible a few times earlier. I waited until now because it didn’t really make sense until now.

I then followed up by fusing `extractDigits` with `drawCisterianValue`:

Ordinarily you should have a single well defined function for each job for the sake of good readability and modularity, but when you’re trying to save memory sometimes you have to sacrifice modularity.

I also tried turning `drawUnits` into a loop, but that resulted in a large increase in size, which I suspected was a possibility. It may be due to excessive inlining, or it may be a side effect of making the pattern mask (`patern1`, `pattern2` et cetera) a mutable variable instead of a constant. Either way it’s not really important.

(These last changes save another 200 or so bytes.)

I’m fairly confident that this is about as minimalistic as this code can get without getting into really low level shenanigans or ending up with volatile savings.

In other words, this code now represents the essence of what it means to render Cistercian numerals. The `drawDigit` function is the essence of the pattern/rule exhibited by the four quadrants, and the `drawCistercianValue` function represents the same rule applied to four quadrants as dictated by four decimal digits of a binary number. There’s almost something ‘zen’ about that.

If they had any sense, they’d be exactly the same but their computers would render digits with an algorithm similar to what’s evolved here. (Though it might take more or less time depending on how the rest of history played out.)

Modern computers don’t use binary to be awkward, they use binary because the laws of the universe make binary computers so much more practical. People have tried making analogue, decimal and even trinary/ternary computers, but binary has reached the top of the pile out of pure practicality.

At any rate, hopefully you’ve learnt a few tricks along the way.

If there’s anything you don’t quite understand or that you’d like to know more about, feel free to ask questions. Ordinarily I’d have checked you understood at each step, but I’ve been toing and froing a bit today, so I haven’t been in full ‘help/teaching mode’, I’ve been in ‘light pondering mode’ instead.

If nothing else, this proves something Donald Knuth once said:

Always remember, however, that there’s usually a simpler and better way to do something than the first way that pops into your head.

(And it’s clearly true at all levels of experience/expertise.)

1 Like

Absolutely brilliant. This actually helped me grasp bit-wise operations much more than before.

Precisely what I was getting at I should have worded my statement better before, but it’s that thought that led me to want to make something like this. I knew I couldn’t get the bit-wise operations right before, though, so I approximated what could be considered a more human-like approach for rendering them. Your last version of the code is basically the answer to that question I was pondering

Going a little off-topic, but this is something I think about a lot, and was captivated recently by Steve Mould’s video showing how he used a series of Pythagorean siphons to build a fluid-based adder, the siphons themselves acting as AND or XOR gates, it’s really brilliant to see in action.

In an alternate universe, or even this universe, Cisterian numerals could have been, or still could be, added to Unicode, as many other alternate numeral systems have been.

They’re included in the Under-ConsScript Unicode Registry (UCSUR), which is an informal arrangement for encoding scripts not accepted by Unicode in the ‘private use area’ of Unicode. It includes finctional scripts such as Aurebesh, Cirth, Klingon, Tengwar, the Standard Galactic Alphabet and D’ni, as well as some less fictional scripts like ‘solresol’ and ‘visible speech’.

(Incidentally I was reading about the UCSUR the other day, so I must have skimmed the words ‘Cistercian numerals’ before this topic was made.)

There’s a note at the bottom of the Cistercian numerals Wikipedia page saying that the page in question makes up for this by substituting tone letters, which are similar in shape and are included in Unicode.

That’s a reasonable strategy for writing software in general. Adapting the human way of doing something so a computer can understand it is generally a good way to get something that works, even if it isn’t very efficient.

I’ve heard of people doing this sort of thing from time to time.

It’s nice to see an explanation of how the gates are actually implemented with water.

(He loses points for not having a water wheel though. `:P`)

1 Like

Cool! I saw a video about this number system, actually, and thought I’d share it. Very cool to see a modern generator for it! Perhaps you could give us the ability to enter a number in, like a calculator?

2 Likes

Since this has been bumped anyway…

@poevoid, another number system you might be interested in is the D’ni number system from the Myst series of games.

Before I explain it, I’ll mention that working out the numeral system was actually one of the puzzles in Riven (the sequel to Myst, effectively Myst II), which is why I’m hiding the details. If anyone wants to play Myst and Riven at some point, I don’t want to spoil it for them.

The D'ni Numeral System

It’s a base-25 system, and like the cistercian system the glyphs are constructed using a set of rules that combine certain marks to produce new glyphs.

These are the symbols:

And here is a table demonstrating how the 25 symbols are formed:

The grid contains the numbers increasing in value from 0 in the top left (which should actually be a box with a dot in the centre) to 24 in the bottom right, with each column increasing the value by 1 and each row increasing the value by 5.

Thus it would be possible to create a rendering algorithm for them that works on a similar principle of combining the component parts.

1 Like

Nice! Love that guy’s enthusiasm about everything lol

A calculator would be pretty neat too! I’ll probably work on that a bit between my other projects at the moment

This is pretty cool! A little bit less intuitive than Cistercian, but also a little bit more visually interesting. I can see why it’d be constructed for use in an RPG or a puzzle game!

1 Like