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.

Proof

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

\[\begin{align*}
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)
\end{align*}\]
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}\]
QED


Generalisation

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

\[\begin{align*}
\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)
\end{align*}\]
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]

15:52

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]

22:44

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


Decary (Base 10) Clock  [download]


22:16

You get the idea...


Finally

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.


Oatzy.


[Decary? Really..?]

3 comments:

thistimearound said...

Stumbled upon this blog after lots of searching. You definitely seem to know your way around Zooper. I know it's got limited nested conditionals, but I'm trying to set up a string that condenses the weather into less characters. Example:

$$#W0COND#=scattered clouds?S-Clouds:$$#W0COND#=mixed snow and sleet?Snow & Sleet:$$#W0COND#=scattered thunderstorms || isolated thunderstorms?Thunderstorms:#W0COND#$

If the weather conditions are either of the thunderstorms variables I am greeted with Thunderstorms. However, if the condition is Mixed Snow and Sleet I'm presented with Snow & Sleet:Mixed Snow and Sleet. I don't understand how it's breaking, or where. I suspect it's too many nested conditions, but I'm not well versed enough to come up with an alternative.

If you can help, that would be awesome. Good tutorials! Thanks!

Oatzy said...

The problem is, when you try to put a new expression in the OR statement, the '$' closes the previous IF. So the code you've posted will be interpreted as 3 IFs. For example, when the condition is 'Mixed Snow and Sleet', the first statement evaluates to nothing, the second evaluates to 'Snow & Sleet:' and the third evaluates to #W0COND#

Unfortunately, there's no way around this. You'll have to do it the long way:

$#W0COND#=scattered clouds?S-Clouds$
$#W0COND#=mixed snow and sleet?Snow & Sleet$
$#W0COND#=scattered thunderstorms || #W0COND#=isolated thunderstorms?Thunderstorms$
$#W0COND#!=scattered clouds && #W0COND#!=mixed snow and sleet && #W0COND#!=scattered thunderstorms && #W0COND#!=isolated thunderstorms?#W0COND#$

Alternatively, you could try using the condition codes #W0CODE#, explained here.

For example, 'Thunderstorms', 'Scattered Thunderstorms', 'Isolated Thunderstorms', etc. all have a code of 2. So you could do something like:

$#W0CODE#=13?S-Clouds$
$#W0CODE#=7?Snow & Sleet$
$#W0CODE#=2?Thunderstorms$
$#W0CODE#!=13 && #W0CODE#!=7 && #W0CODE#!=2?#W0COND#$

It's more succinct, but I've had to assume, for example, that 'Snow and Sleet' is equivalent to code 7: 'Snow and Rain'.

Hope this helps.

thistimearound said...

LOL, you just murdered that for me. Thank you so much. You wouldn't believe the amount of XDA and Google searching I did for such a simpler idea. You explained a lot, and gave me usable example code. So, so grateful.