Sunday, January 11, 2015

Follow Up: A Binary Proof and a Trinary Clock

In the last blog I talked about making a binary clock widget (for Android) using Zooper, and I made a claim about how individual binary digits can be extracted from a decimal number - what follows is an explanation/proof of why it works.

The Claim

The n-th digit of the binary representation of a number, x, is a zero if \(x \bmod 2^{n+1} \lt 2^{n}\), or a one otherwise.


To start, we express our number x as a sum of powers of 2. This makes sense, since this is basically how binary works. So we have

\[ x = \sum_{i=0} a_{i} 2^{i}\]
where the \(a_i\) equal either 1 or 0 - these are equivalent to the i-th digits in the binary form of the number (reading right to left). For example, if x=5 then \(a_0=1, a_1=0, a_2=1\) and all other \(a_i=0\) (since 5 in binary is 101).

So lets split the sum up into three parts and expand

x &=\ a_{n} 2^{n} \ +\ \sum_{i=0}^{n-1} a_{i}2^{i} \ +\ \sum_{i=n+1} a_{i} 2^{i} \\ \\
&= a_{n} 2^{n} \\
&+ (a_{0}2^{0} + a_{1}2^1 + \ldots + a_{n-1}2^{n-1}) \\
&+ (a_{n+1}2^{n+1} + a_{n+2} 2^{n+2}+ a_{n+3} 2^{n+3}+\ldots)
Notice that in the second set of brackets, all the terms are divisible by \(2^{n+1}\) - so if we take mod \(2^{n+1}\), all of those terms disappear

\[ x \bmod 2^{n+1} = a_{n} 2^{n} + (a_{0}2^{0} + a_{1}2^1 + \ldots + a_{n-1}2^{n-1}) \]
The terms in the remaining set of brackets sum to some value between 0 and \(2^{n}-1\) (depending on the values of the \(a_i\)). We'll call this \(\sigma\) for convenience.

Therefore, if \(a_n = 1\) then

\[ x \bmod 2^{n+1} = 2^{n} + \sigma \ge 2^{n}\]
And if \(a_n = 0\) then

\[ x \bmod 2^{n+1} = \sigma \le (2^{n} - 1) \lt 2^{n}\]


As with powers of 2, we can write numbers as the sum of powers of any number/base. For example, we can write 11 as \(2\cdot 3^0 + 0\cdot 3^1 + 1\cdot 3^2\) - or to put it another way, 11 in base 3 is 102.

So in general, we can write a number 'x' in terms some base 'b' as

\[ x = \sum_{i=0} a_{i} b^{i}\]
where the \(a_i\) are whole numbers between 0 and (b-1) - equivalent to the i-th digits of x in base 'b'. So for example, for x=11 and b=3 we'd have \(a_0 = 2, a_1 = 0, a_2 = 1\) and \(a_i=0\) for all other i.

As before, we can split the summation and expand. But this time we're going to divide through by \(b^n\) as well

\frac{x}{b^n} &=\ a_{n} \ +\ \frac{1}{b^n}\sum_{i=0}^{n-1} a_{i}b^{i} \ +\ \frac{1}{b^n}\sum_{i=n+1} a_{i} b^{i} \\ \\
&= a_{n} \\
&+ \frac{1}{b^n}(a_{0}b^{0} + a_{1}b^1 + \ldots + a_{n-1}b^{n-1}) \\
&+ (a_{n+1}b^{1} + a_{n+2} b^{2} + a_{n+3} b^{3}+\ldots)
And now, all the terms in the last bracket are divisible by just 'b', so taking a modulo of 'b' will make those terms disappear. So we have

\[ \frac{x}{b^n} \bmod b = a_n + \varepsilon \]
where \(\varepsilon \le \frac{b^{n}-1}{b^{n}} \lt 1 \).

And from this, we can define a general function for extracting \(a_n\) - the n-th digit of x in base 'b' - as

\[ D^{n}_{b}(x) = \left \lfloor{ \frac{x}{b^{n}} \bmod b }\right \rfloor\]
where the brackets mean 'floor', or round down to the nearest whole number - basically, get rid of \(\varepsilon\).

So as an example, the zeroth and first digits of 35 in base 16 (hexadecimal) are

\[ D_{16}^{0}(35) = \left \lfloor{ \frac{35}{16^{0}} \bmod 16 }\right \rfloor = \left \lfloor{ 35 \bmod 16 }\right \rfloor  = 3 \\ D_{16}^{1}(35) = \left \lfloor{ \frac{35}{16^{1}} \bmod 16 }\right \rfloor = \left \lfloor{ 2.1875 \bmod 16 }\right \rfloor  = 2\]
So 35 in hexadecimal is 23. Easy.

Trinary Clock  [download]


The thing is, binary clocks are great and all. But they're old hat. So now we have a way of finding the individual digits of a number in any base, we can make something a little more unique - a trinary clock.

Before, when I constructed the binary clock, I used rectangles for each binary digit, which changed colour depending on whether the digit it represented was a one or a zero. For a trinary clock we'd need each rectangle to have 3 state - 0, 1, 2. The problem is, Zooper can only do 2-state logic - if-then-else - not else-ifs, and no nested if-statements. So we can't make a rectangle that switches between 3 colours.

Instead, I made each segment a progress bar with values 0-2. For the current value of each bar/digit, we can use the formula we found above - \(D^{n}_{3}(x) = \frac{x}{3^n} \bmod 3\).

For example, for the 3rd segment (n=2) of the hours ring, we'd set the current value to

$(#DH#/9) % 3$

The progress bar automatically rounds values down to the nearest whole number, so we don't have to worry about getting rid of any decimals. But you could add a 'floor' function if you wanted.

Like the binary clock, I made the sizes of each segment proportional to the values they represent - the three-segment is 3 times bigger than the one-segment, etc. And to make reading clearer, I've made the leading edge of each segment a darker blue - that way it's easier to tell where one segment ends and the next one begins.

Quinary (Base 5) Clock  [download]


Once you've figured out the trinary clock, adapting it to other bases is very straightforward.

Decary (Base 10) Clock  [download]


You get the idea...


As far as telling the time goes, all the clocks in this and the previous blog are pretty... challenging. At least until you get the hang of it. But they look cool. And that, I think is worth the extra effort. If I ever get a smartwatch I'll probably try to port some of these designs over. And if/when I do, you can bet I'll post them here.

[edit] - Android Wear versions are here.


[Decary? Really..?]

Friday, January 09, 2015

Metric and Binary Clocks (for Android)

A long while back I wrote a couple of blogs about clocks. In the first I talked about decimalising time. Half a year later, I wrote another where I designed a couple of circular binary clocks. I thought I'd try to recreate those clocks for my phone.

I had a widget making app - Zooper - installed on my phone, that I'd played with before. I build myself an autumnal homescreen, that looked like this.
I don't use that theme anymore. These days I prefer a more minimalist homescreen - no widgets, as few icons as possible. But if you like it, you can [download] the widgets/wallpaper for the above theme. You'll need the Media Utilities app for the music bar.

Note - if you want to use any of the widgets I've linked in this blog, you'll need the paid version of Zooper. Alternatively, you can try to recreate them yourself - I'll include important details in this blog. There are other widget making apps, but I don't know much of using them.

How to Make a Basic Clock Widget

I'm going to quickly go over making a normal clock first so you can get a sense of how stuff works.

Making a circular clock, such as below, is pretty straightforward. Create a progress bar object for the minutes (the inner ring) and set its 'curve' value to 360. Then set the min and max values to 0 and 60 respectively and set the current value to #Dm# (the current minutes). You may need to rotate and reposition it.

Create the hours circle in much the same way - using #Dh# for 12h format, or #DH# for 24h format. There are then loads of style settings you can play with. In the end you'll have something like this.
Above is actually one of the built-in widgets that I de-cluttered a little. So if you don't want to go to the trouble of creating a widget from scratch, you can just tweak the ones that are already installed.

Note - all the clock images in this blog are shown on a grey background for clarity. Their actual backgrounds (if you download them) are transparent.

Backwards Clock  [download]

This is actually the last one I made. I have an analogue backwards clock on my bedroom wall, that my sister got me from the Science Museum in London. I figured, while I was at making clocks, why not make one of those as well. I put it second in this blogs because it's trivially different from the normal, forwards clock.

As before, you make your hour and minute rings from progress bars, but in this case you set the curve to negative 360. Like I said, trivial.

Decimalised/Metric Clock  [download]
That's 17:55 in real money.
The idea behind 'metric' or decimalised time is that the day is redefined as being 10 hours long, with 100 minutes per hour and 100 seconds per minute. The construction of the clock itself is the same as for the normal clock, we just have to convert the current time to metric.

For that, we first convert the current time to minutes, and divide that by the total number of minutes in a standard day (24*60) - this gives us the fraction of the day that's elapsed. Multiplying that by the number of hours in a metric day (10) gives us the current decimalised hour.

For example, if we decimalise the time 12:51, we get the hour as 5.3542. In fact, because of the way metric time works, 5, is the hour and the first two digits after the decimal point, 35, is the minutes.

So for the hours ring, we set the current value to

$(0.00649*(60*#DH# + #Dm#))$

The progress bar object will automatically round this down to the nearest whole number.

To extract the minutes, we can use the 'modulo' operator (written as a percentage symbol '%' in coding). The modulo operator gives us the remainder from division. So if we multiply the (metric) hours by 100, and take mod 100 we get something like \((100\cdot 5.3542) \bmod 100 = (535.42 \bmod 100) = 35.42\). Again, the progress bar will round this down.

So we can set the current value for the minutes ring to

$(0.649*(60*#DH# + #Dm#) % 100)$

I also included a text output the decimalised time. As mentioned above, we can just calculate the metric hour, which will give us something like 5.35. But I wanted it to have it to have the 5:35 format like a normal clock.

We already have our expressions above for the metric hours and minutes. We just need to slip in a couple of 'floor' functions to round them down to whole numbers. The other thing is that when the minutes is less than 10, they display as a one digit number, e.g. 5:3 instead of 5:03. To fix this we just throw in an if-statement.

The code for the text output of the metric time looks like this


Yeah, it's a little unwieldy.

Binary Clock  [download]

10011:011101 = 19:29
In this design, each segment on each ring represents a power of two/binary digit. When the segment is grey it's a zero, when it's blue it's a one. So in the above, the hour (outer ring) is 10011 in binary, or \(1\cdot 16 + 0\cdot 8 +0\cdot 4 + 1\cdot 2 + 1\cdot 1 = 19\), in base 10.

In this case, we can't use progress bars. Instead, we have to make each ring segment an individual rectangle object, that will change its colour depending on whether it's representing a one or a zero. This makes constructing the clock a little less straightforward.

For the minutes ring, create 6 rectangles each with a curve of 60, and rotated so that they form a circle. Similarly, for the hours ring create 5 rectangles with curve 72, and so on.

I originally tried aligning everything 'free-hand'. That didn't work so well, so I created a temporary full circle as a guide. Of course, you don't have to make a binary clock circular - you could have it as a line of dot/bars. I just like the circle design.

Now, we need a way of converting the time to binary, and a way of telling each block whether the binary digit it represents is a one or a zero. At this point, I'm going to make a claim -

The n-th digit of a number, x, in binary is a zero if \(x \bmod 2^{n+1} \lt 2^{n}\), or a one otherwise.

I'll prove this in a supplemental blog, that will be posted shortly after this one. In the meantime, you might like to try proving it for yourself.*

[edit] - You can read that supplemental blog here.

So we can use this condition to set/change the colours of each rectangle. For example, for the 2nd rectangle on the minutes ring (n=1), go to "Advanced Parameters", and enter something like

$(#Dm# % 4)<2?([c]#19ffffff[/c]):([c]#ff1084cb[/c])$

Or for the 5th rectangle on the hours ring (n=4), enter

$(#DH# % 32)<16?([c]#19ffffff[/c]):([c]#ff1084cb[/c])$

And so on.

I also made an annotated version of the design [download] to make telling the time slightly easier; albeit at the cost of looking a little cluttered
(16+4):(32+8+4+1) = 20:45

I tried adding a seconds circle, like in the version from the old blog, but the widgets don't seem to refresh often enough for it to work. Which is a shame, 'cause it's fun to watch the seconds move.

Proportional Binary Clock  [download]


This is pretty much the same as the one above, except, each segment is sized in proportion to the power of two it represents - the 8-segment is four times as big as the 2-segment, etc. I did this to give a better perspective on how much time has passed - because, really, one minute shouldn't take up as much of the clock face as 16 minutes. And also, I just think it looks neat.

The mechanics work the same as above. The tricky part is getting the rectangle sizes, curves and rotations right, and getting everything lined up just right, without loosing you mind over how that one bit is half a pixel out of place and there's nothing you can do about it so just let it go, okay!



[Making a backwards, binary, metric clock is left as an exercise for the reader.]

* Hint: Try re-writing x as a sum of powers of 2.
Bonus: Generalise for other bases.

Thursday, January 01, 2015

Lights Out (Game)

I was watching this year's RI Christmas Lectures, and it reminded me of this game I had when I was much younger. It was, I think, a Christmas present from my grandparents, back in '96. It was called Lights Out, and it looked something like this.

Basically, the console had a 5x5 grid of these rubbery, transluscent buttons with little red lights underneath them. When you press a button, that button and the four adjacent buttons switch state - light on to light off, or off to on. So, in the example below (where blue square are lights), if you press the centre square, the centre square turns off and the four adjacent squares turn on.

In the game, you're given a pattern of lights, such as the one above, and the task is to press buttons until all the lights are out.

Interestingly, in the pattern above (on the left), you can clear the board by just pressing the squares that are on at the start (in any order).

Anyway, I was reminded of that. Meanwhile, I'd been learning some Pygame for this other thing (that I'll talk about in a later blog). Now, Pygame is a Python library for making games (amongst other things). So you can probably see where this is going...

Coding a 'Lights Out' clone was straightforward enough - the code is short and not too complicated. The above images are actually screenshots. You can look at my code/download it here. You'll need Python and Pygame to run it.

This is a very threadbare version of the game. You can load a level as a text file of five lines of ones and zeros, like here. Or else you can just play from a blank board - make patterns then try to get rid of them again (not necessarily as easy as it sounds).

If you want something more fancy, or if you don't want to install Python and all that, there are probably loads of playable clones online.

Now, at this point you're probably thinking "Yeah, that's great. But what about the maths of Lights Out?". And you'd be damn right to ask. If you're interested, there's a good summary, as well as links to articles/papers, on the wikipedia page. I don't want to just repeat what's written there. Basically, it all comes down to linear algebra.

Anyway, have fun with that.


[Call this a late Christmas present.]