brhfl.com

Aztec diamonds: Shifted like tangrams

Well, I was right about one thing – there was a straightforward solution to this whole Aztec diamond problem. To be fair to myself, my original solution holds up – I neglected to add one somewhere in my equation (we’ll get to that later), an error that was insignificant at the start, and less significant as the Aztec numbers increased. To get to the reveal, it’s worth backing up to our series, OEIS: A046092 again. Somehow, in my haste, I kind of glossed over the fact that these are ‘4 times triangular numbers,’ a fact that became readily apparent to me when I was coming up with the diagrams for the last post. You see…

An Aztec diamond split into four triangles.

…our Aztec diamond is made up of four triangles; and it is in fact true that each of our Aztec numbers is 4× the corresponding triangle number. A funny thing about triangle numbers is that if you multiply them by eight and add one, they become perfect squares. This can be demonstrated visually:

Nine triangles of leg size three tile into a seven by seven square with one unit ‘missing’.

This visual only proves that it’s true for the triangle number, 6, but it is universally true and readily proven – this ‘Cool Math Stuff’ post shows it succinctly, and John Conway and Richard Guy discuss it in The Book of Numbers. Rehashing the proof here seems rather pointless. Fascinatingly, I did almost figure this out last time, with the extra unit hypotenuse theory.

So, we know that for our Aztec number, x, x/4 is a triangle number, and for this triangle number, y, 8y+1 is a perfect square. We know that any given side of this square is made up of 2× the length of a side of triangle y plus one, which is ultimately the value that we need to recreate our square from our grid. We can see this rather clearly in the first diagram with the triangle highlighted – the three dots forming the outer side correspond directly to segments of our grid.

Thus, given a triangle number, y, the length of any of its sides is (sqrt(8y+1)-1)/2. Which then leads us to the same thing for our Aztec number, x, (sqrt(2x+1)-1)/2. Now, to solve my problem, I actually need to add one to this. Given that we’re dealing with integers, this can be simplified to ceil(sqrt(2x+1)/2) – precisely what I originally came up with, aside from the +1.

So, my equation was wrong, but it provably works – the off-by-one error is clearly insignificant for a 3×3 square, and, given x, sqrt(x2)-sqrt(x2-1) converges toward zero:

Chart shows that the aforementioned equation quickly approaches zero.


Aztec diamonds: Testing the reversed Aztec numbers

My initial test of x=ceil(sqrt(2y)/2) to determine the size of a square given a value in A046092 corresponding to how many line segments would remain if the grid formed internally at every unit of height and width of the square was broken at every intersection was tested and shown to be valid for the first 1000 numbers in the sequence. I did this haphazardly in Excel, just to make sure it wasn’t going to fail quickly.

I have since scripted a test in python, which has thus far shown my method viable up to a 50907428697×50907428697 square. The script is called by passing it an argument containing the initial integer for the square’s size (default 2), and it loops infinitely until it either fails or is halted with SIGINT. Upon halting, it returns something like Last success: Square 39033633; azNum 3047249088424644; urNum 39033633.0, where Square is the height/width of the square being tested, azNum is the number of line segments (or squares in the equivalent Aztec diamond), and urNum is the calculation which (hopefully) is equal to Square. Revealing the last success in this way tells me where to start next time. The code:

import signal
import sys
from math import ceil,sqrt
def sigintHdl(signal,f):
    print "Last success: Square %s; azNum %s; urNum %s" % (tNum-1,azNum,urNum)
    sys.exit(0)
signal.signal(signal.SIGINT,sigintHdl)
tNum = 2 if len(sys.argv)<2 or int(sys.argv[1])<2 else int(sys.argv[1])
result=0
while result==0:
    azNum=tNum**2+tNum*(tNum-2)
    urNum=ceil(((2*azNum)**.5)/2)
    result=urNum-tNum
    tNum+=1
print "FAILURE: Square %s; azNum %s; urNum %s" % (tNum-1,azNum,urNum)

There’s another way of looking at this whole thing. If we consider an isosceles right triangle with hypotenuse h, we know the length of either of the legs is equal to sqrt(h^2/2). Interestingly enough, if we work with a hypotenuse of one unit larger (which should never exist as a halved Aztec diamond), h^2/2 is equal to our A046092 value +0.5.

Adding one unit to our central line yields seven units; squaring seven and then halving the result yields 24.5. 7

Ultimately, the problem seems to be one of dealing with a not-quite-proper triangle. It’s easy to imagine additional nodes that make the triangle more… triangular. Doing so leads to more funny math, but it all sort of, kind of makes sense. I guarantee there’s an off-the-shelf solution out there, and it’s likely quite straightforward and, in hindsight, obvious. But this sort of math isn’t necessarily my forté, so I’ll just fidget around until I come up with something conclusive. At this point, it’s all for fun – I have far more known-valid values than I could ever imagine needing. My little python test snippet will easily be reused for other things as well, so I’ll call that a win.


Aztec diamonds: How I came to learn of them

A little project I’m working on requires me to suss out the size of a square given the following: Imagine a square of width and height x units. The square is gridded by unit such that x^2 squares are visible inside it. How many of these squares’ perimeter lines exist inside the outer square? Or, put another way, if you then erase the border of the original square and break every line segment at the intersections, how many line segments do you have left?

It seems to work out to x^2+x*(x-2). For a 2×2 square, there are 4 segments left. 3×3 yields 12, 4×4 yields 24, 5×5 yields 40, 6×6 yields 60, and so on. I confirmed this far by manually counting the segments, and everything seemed good. This wasn’t what I needed, however, I needed to be able to do it in reverse – given 24 segments, I needed to come up with my outer square’s width and height of 4. This was not an obvious solution.

I tried searching for things like ‘size of square from inner grid segments’, but I couldn’t really articulate the thing in a way that got me anywhere. Or, perhaps, nobody has ever really needed this version of this problem solved before (though I find that doubtful). I needed a new angle. I searched OEIS for my sequence, 4, 12, 24, 40, 60, and came up with A046092, ‘4 times triangular numbers’. Now, OEIS is great, but it has a way of presenting a lot of information very tersely, which can be overwhelming. So I googled A046092, and nearly every hit came back to one thing – Aztec diamonds.

Further searching revealed that Aztec diamonds are popular because of the Aztec diamond theorem and the Arctic Circle theorem, both related to domino tilings. This is all very fascinating, but unfortunately presented me with a dead end. Fortunately, I did also discover that Aztec Diamond Equestrian is a company that makes leggings with very functional looking pockets, so that was a win. But on the math side of things, I wasn’t coming up with much. I did, at least, realize that if I rotated my grid and treated each of those segments as the diagonal of a square, I was in fact dealing with an Aztec diamond. If nothing else, this allowed me to confirm that A046092 was the sequence I was dealing with, it allowed me to confirm my original equation, and therefore meant I could test any arbitrary case without manually counting.

I started noticing other patterns, too. The problem is complicated because it’s like a square, but it’s missing the corners. This is where the narrative begins to fall apart. All these thoughts of squares and right triangles, hypotenuses… I established a formula that I have tested for the first 1000 integers in A046092, they all pass. But I cannot come up with a proof that explains it. Furthermore, I am not confident that it actually holds up despite the first 1000 integers validating. The next step is scripting the formulae out to test well beyond 1000.

Now, for my project, I don’t need anywhere near 1000, so the equation is Good Enough. Hell, I could probably hardcode the sequence as far as I need it, and a lookup table would likely be faster than a bunch of math. But now I’m really curious. So for a square x by x units, and y as the xth integer in A046092, I’d love to prove that x=ceil(sqrt(2y)/2). I don’t know that I can, but I would really like to. Ultimately I know I’m looking at a hypotenuse, or an approximation of a hypotenuse, with the Pythagorean theorem being beautifully simple given the area of a square.

I guess, in the end, I have an equation that more than meets my needs. I learned about Aztec diamonds, and I figured out why this problem is not as simple as it originally seems. I also learned about some pretty bangin’ equestrian leggings. I’m going to keep at this, though, because it fascinates me, and I haven’t found a solution in the wild. I’ll report back, but before I do, there will likely be a game-in-a-post to explain why I was trying to solve it in the first place.


Tetris has been implemented in Conway's Game of Life (external)

Over four years ago, a challenge was posed on the Programming Puzzles & Code Golf Stack Exchange: Build a working game of Tetris in Conway’s Game of Life (GoL). Yesterday, an incredibly dedicated team of seven posted a working solution that is just fantastic to read about. I am flabbergasted by the work that went into this, and what these folks achieved. Starting with the concept of a metapixel – essentially a giant block of GoL tiles that can be programmed to behave like a single GoL cell, but with any ruleset – they developed wiring, logic gates, an ALU, a RISC architecture, an assembly language, a higher-level language, and finally (for now) a working game of Tetris. Not the first example of advanced computation in GoL (Wireworld is well known), but almost certainly the largest in scope and likely the best-documented as well. I linked to the Stack Exchange page, and if you have any knowledge of GoL, logic gates, or low-level computing, the multiple write-ups are incredibly clear and fascinating.


Sinclair Scientific Programmable

The Sinclair Scientific is one of my favorite calculators, though certainly not for its speed, accuracy, or feature set. In fact, in an era where full-featured scientific calculators can be had for under ten bucks, it’s a downright laughably bad machine. But it’s evidence of the ingenuity of Sinclair in their race to have made tech accessible for those with slimmer wallets. The Scientific may well be a post for another day, but recently I fell into another ridiculously quirky Sinclair calculator, the Scientific Programmable. Its manual describes it as ‘the first mains/battery calculator in the world to offer a self-contained programming facility combined with true scientific functions at a price within the reach of the general public’.

As with the Scientific, that last bit is key – this machine was engineered to meet a price point. HPs of the day were engineered for speed and accuracy, and were beautiful, easily operated machines to boot. Sinclairs were affordable, period. To start investigating this thing’s quirks, let’s address the ‘true scientific functions’ that the calculator includes. Sine, cosine, arctan, log, and antilog. No arcsine, arccos, or tangent – instead the manual tells you how to derive them yourself using the included functions. Precisely what I expect from a Sinclair (though the aforementioned Scientific did include all standard trig functions).

The highlight (if you will) of this calculator is, of course, its ‘self-contained programming facility’, which is really what I’d like to discuss. While the terms are oft indistinguishable nowadays, I would really consider the Scientific Programmable’s functionality more of a macro recording system than anything resembling programming. There are no conditionals, there is no branching, and a program can only contain 24 keystrokes. The keyboard is shifted for program entry, and integers thus require two extra keystrokes as they are delimited. I say integers because that is all one can enter during program entry – if your program requires you to multiply by .125, you would need to calculate that with integer math first.

My go-to demo program is Viète’s formula for pi. It’s simple, requiring very little in the way of scientific functions, stack manipulation, memory registers, or instructions; yet it’s fun and rewarding. Unfortunately, I don’t actually think it’s possible on the Scientific Programmable, primarily due to the lack of a stack and the single memory register. I just need one more place to stick a value, and a stack would be ideal – it would contain the previous result ready to be multiplied by the next iteration.

We could try pi the Leibniz (et al.) way, 1 – 13 + 1517 + 19, and so on. But we still need to store two variables – the result of every go, and the counter. I still don’t think it can be done.

How about we eschew pi and just make 3. Easy enough, just type 3 or, perhaps 69 enter 23 ÷. But what if I want to do it Ramanujan-style with more nested radicals? I… still don’t think I can, because again I essentially need a decrement counter. Bit of the inverse of the problem as above, one place for storage just isn’t enough. Sorry, Ramanujan.

So what can we do? I guess the golden ratio is simple enough: ' 1 ' + √ and then just mash EXEC repeatedly until we have something resembling 1.618. Not terribly satisfying. Also, the calculator lacks the precision to ever actually make it beyond 1.6179.

To be fair, the calculator (well, not mine, but a new one) comes with a program library in addition to the manual. Katie Wasserman’s site has them, fortunately. And while none of the programs are particularly interesting in any sort of technical way, they do give a good overview of how this macro mentality would cut down on repetitive calculations. One thing that I do find technically interesting, from a small systems/low level perspective is Sinclair’s advice on dealing with the limitations. For instance, they mention that pi is 355113 which yields 3.1416, as accurate as is possible. But if one is willing to deal with less accuracy, they suggest 4*(arctan 1) for 3.1408 (~.02%) or 227 for 3.1428 (~.04%). Determine needs and spend memory accordingly.

All in all, I don’t know what I’ll do with the Scientific Programmable beyond occasionally pulling it out to mess with. It’s not really fun to program like an old HP, because it’s just too limited. I guess if I come up with any other simple, iterative formulas that I can plug into it, I may revisit. But, much like the Sinclair Scientific, it will largely stay in my collection as a quirk, a demonstration of what was ‘good enough’ alongside the cutting edge.


Sieve of Eratosthenes

This post contains APL code, and assumes that your system will be capable of rendering the relevant unicode code points. If the code below looks like gibberish, either you don’t understand APL or your computer doesn’t ☺. I use the APL standard of six spaces indentation to show my input, and zero indentation for output. As for the code itself, it assumes one-indexing, that is, ⎕IO←1.

I was messing around with some primality and coprimality testing in dc the other day when I got to wondering about inefficient methods for checking primality (specifically, the thought of testing primality of n by testing coprimality of n and m where m is every integer<n). This reminded me of the sieve of Eratosthenes, a first-century CE means of narrowing down a list of integers to a list of primes by eliminating multiples of primes (which must be composites). My APL is getting very rusty, unfortunately, but this seemed like a fun exercise since APL is a language heavily invested in arrays. We may start by assigning s to the integers 2-26, and confirm this by printing s as a 5x5 matrix:

      s←1↓⍳26
      5 5 ⍴s
 2  3  4  5  6
 7  8  9 10 11
12 13 14 15 16
17 18 19 20 21
22 23 24 25 26

Then we can start sieving. I’m going to skip ahead to the threes to avoid a potential spot of confusion, so what we need to do is reassign the elements after 3 to either a zero if there’s no remainder (upon dividing by 3), or the original value if there is. 2↓s narrows us down to the appropriate elements, and we have to make sure that we do that everywhere so that our 1x25 shape stays intact. The first step is getting our remainders. 3|2↓s performs modulus 3 on elements 4-25, resulting in 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2. This doesn’t fit neatly into a 5x5 grid, however, so I’m going to temporarily write it over the corresponding elements in s:

      (2↓s)←(3|2↓s)
      5 5 ⍴s
2 3 1 2 0
1 2 0 1 2
0 1 2 0 1
2 0 1 2 0
1 2 0 1 2

This gives us zeroes where we need them – at every multiple of three (excluding three itself, of course). We can then turn this into a series of ones and zeroes by comparing each value to zero:

      5 5 ⍴ 0<s
1 1 1 1 0
1 1 0 1 1
0 1 1 0 1
1 0 1 1 0
1 1 0 1 1

Which we could then multiply by our original set of 25 integers, if we still had them. So let’s reassign s and put it all together. And since we skipped over two, we should probably do that as well.

      s←1↓⍳26
      (2↓s)←((3|2↓s)>0)×2↓s
      5 5 ⍴s
 2  3  4  5  0
 7  8  0 10 11
 0 13 14  0 16
17  0 19 20  0
22 23  0 25 26

      (1↓s)←((2|1↓s)>0)×1↓s
      5 5 ⍴s
 2  3  0  5  0
 7  0  0  0 11
 0 13  0  0  0
17  0 19  0  0
 0 23  0 25  0

So now we’ve sieved out all of our multiples of 2 and 3, and the only thing left to sieve is 5. Of course, if we didn’t already know the primes ≤25, we’d want to keep trying every nonzero value in the list, but we do know that 25 is the only outstanding composite in the list, and (4↓s)←((5|4↓s)>0)×4↓s does, in fact, take care of it, as can be seen here, on TryAPL.org.

I mentioned that my APL skills are a bit rusty. I’m not sure I’ve even mentioned APL on this blog before, but it is probably tied with Forth for the coveted title of Bri’s favorite language. I’ve never been great at it, though. It’s a relic, with lineage dating before computers were capable of running it. I either don’t do enough array-based math, or I don’t think of enough of the math I do in array-based terms to use APL regularly. Where I get really rather rusty is in thinking outside of imperative terms or using APL’s imperative programming behaviors. Which was why my little demo here was very REPL-esque. Hopefully a future post will bundle this thing up into an actual, runnable function that knocks the whole process out in one go. But for now, have fun typing in those iotas.


Eukleides

Despite having failed out of geometry in my younger days, it has become my favorite sort of recreational math. I think, back in elhi geometry, too much emphasis was placed on potential practical applications instead of just distilling it down to the reality that this was what math was before there was any sort of formal mathematical system. Geometry is hands-on, it’s playful, and as such I have come to really enjoy playing with it. As much as I enjoy doing constructions with a straightedge and compass, I occasionally poke around to see what tools exist on the computer as well. Recently, I stumbled across a very neat thing: Eukleides.

I’m drawn to Eukleides because it is a language for geometry, and not a mouse-flinging WYSIWYG virtual compass. This seems contradictory given my gushing about geometry being hands-on, and don’t get me wrong – I love a hands-on GUI circle-canvas too1. But sometimes (often times) my brain is in code-mode and it’s easier to express what I’m trying to do in words than to fiddle around with a mouse. And a task like ‘intersecting a couple of circles’ is far more conducive to writing out than, say, laying down an SVG illustration from scratch.

a b c d e bi

There you have one of the first constructions learned by anyone studying geometry – bisecting an angle with three arcs (or, full-blown circles in this case). Angle ∠abc is bisected by segment bbi. Here’s the code:

% Percent signs are comments
a=point(7,0); b=point(0,0) % Semicolons and newlines separate commands
a b c triangle 5,-40°
g=circle(b,3)
d=intersection(g,a.b); e=intersection(g,b.c)
d=d[0]; e=e[0] % Intersections return sets (arrays), extract the points
h=circle(d,3); i=circle(e,3)
bi=intersection(h,i)
bi=bi[1]
label
  a 0°; b 180°; c 40° % Label the points
  d -40° gray; e 90° gray
  bi 20°
  a,b,bi; bi,b,c 1.5 % Make the angle markers
end
draw
  c.b.a
  g lightgray; h gray
  i gray
  bi
  b.bi
end

Note that the code originally used shades of grey, I shifted these around to match my site’s colors when I converted the resulting EPS file to SVG. The code is pretty straightforward: define some points, make an angle of them, draw a circle, intersect segments ab and bc, make some more circles, intersect where the circles meet, and boom – a bisected angle. The language reminds me a bit of GraphViz/DOT – purpose-built for naturally expressing how things will be drawn.

We can actually prove that the construction works without even generating an image file. Removing the draw and label sections, and replacing them with some print (to stdout) statements calling angle measurement functions:

a=point(7,0); b=point(0,0)
a b c triangle 5,-40°
g=circle(b,3)
d=intersection(g,a.b); e=intersection(g,b.c)
d=d[0];e=e[0]
h=circle(d,3); i=circle(e,3)
bi=intersection(h,i)
bi=bi[1]
%%%%%%%% New content starts here:
print angle(a,b,c)
print angle(a,b,c)/2
print angle(a,b,bi)
print angle(bi,b,c)

We get ∠abc, ∠abc/2, ∠abbi, and ∠bcbi. The last three of these should be equal, and:

40
20
20
20

…they are! We can also do fun things like dividing the circumference of a circle by its diameter:

print (perimeter(circle(point(0,0),4))/8)

…to get 3.14159. Very cool. There are a few improvements I would like to see. Notably, while you can label points etc. with their names, I can’t find a way to add arbitrary labels, or even labels based on functions. So you can’t (seemingly) label a line segment with its length, or an angle with its measure. Also, the interpreter wants ISO 8859-1 encoding, and it uses the degree symbol2 (°) to represent angle measures. This gets all flippy-floppy when moving to UTF-8, and in fact if I forget to convert a file to ISO 8859-1, I’ll get syntax errors if I use degree symbols. Finally, it only outputs to EPS; native SVG would be incredibly welcome.

Eukleides is a lot of fun to play with, and it’s worth mentioning that it has looping and conditionals and the like, so it is programmable and not just computational or presentational. Presumably some pretty interesting opportunities are thus opened up.


Nth-order Fibonacci sequence in dc

After working on the nearest Fibonacci number problem in dc, I got to thinking about how one might implement other generalized Fibonacci sequences in the language. Nth-order sequences seemed like a fun little challenge, and since I was simply doing it for my own pleasure I went ahead and gave it prompts and user input:

% dc -e '[_nacci? ]n?1-sg[terms? ]n?2-snlgsi[0lid1-si1<Z]dsZx1[dls+ssli:flid1+silg>G]sG[li;flid1-si0<R]sRlgsz[0si0sslGxlgsilRxlslzd1+szln>M]dsMxf'
_nacci? 4
terms? 20
20569
10671
5536
2872
1490
773
401
208
108
56
29
15
8
4
2
1
1
0
0
0

…gives us the first 20 terms of the tetranacci sequence. This interested me because unlike a simple Fibonacci iteration that can be handled on the stack with only rudimentary stack manipulation (dsf+lfr), higher order ‘naccis need summation of more terms. For a defined number, I could simply use registers, but dc does support arrays, so setting the order at runtime is plausible. There’s a bit going on here, so I’m going to start by rattling off all of the registers I use:

g
The order (so, a g-nacci sequence)
n
Number of terms to run through
s
Sum
i
General counter
f
Array used to temporarily hold the last sequence as it’s being summed
G
Generalized Fibonacci generating macro
R
Macro to retrieve previous sequence from f
Z
Zero-seed macro
z
Counter for iterations (compares to n)
M
Main macro

Now to break down what’s going on. [_nacci? ]n?1-sg[terms? ]n?2-sn just prompts the user and inputs g and n. We reduce each of these in the process to appease the loops. After doing this, we need to seed the sequence with g-1 zeroes, and one one. lgsi sets counter i to g, and then the macro Z, does nothing but put a zero on the stack and loop: [0lid1-si1<Z]1. dsZx stores the macro and executes it; then 1 pushes the necessary one onto the stack such that we can begin.

[dls+ss]sS is our macro, S, which is a simple summer for register s. It duplicates the top of stack, recalls s, adds the two together, and then writes that back to s. The stack is returned to its original state.

Our next macro, G, has a bit more going on: [dls+ssli:flid1+silg>G]sG. It starts with a simple summer for register s, dls+ss. This duplicates the stack, recalls s, adds them and then overwrites s with the new sum. The stack returns to its original state. The next thing we need to do is move the top of the stack into our holding array, f. We’ll use our counter i as an index, so we load i and then do the array operation, li:f. Every time we do these two things, our summation (the next number in the sequence) nears its next value, and our stack shrinks. The rest of the macro, lid1+sig>G just handles incrementing i and comparing it to our order, g, determining whether or not to continue the loop.

Macro R, [li;flid1-si0<R]sR repopulates the stack from array f. Before calling R, i is set to g, and we use that as our array index to pull from, thus treating the array as a LIFO2. li;f does this, and then the rest of the macro is (surprise, surprise) counter/loop handling.

Before we run macro M, which is our main macro essentially, we set counter z to our order number g, which accounts for the fact that we already have our first few terms in assorted zeroes and a one. M, [0si0sslGxlgsilRxlslzd1+szln>M]dsMx, starts out by resetting counter i and the sum register s to zero: 0si0ss. lGx runs macro G, lgsi sets counter i to our order g, and then lRx runs macro R. ls puts our sum (the new Fibonacci value) at the top of the stack, and then the rest of the thing is counter/loop handling. dsMx saves the macro as M and also sets it running, while our last command, f prints the entire stack.


Nearest Fibonacci number in dc

I hadn’t really exercised my code golf skills in a while, but saw a fun challenge today that seemed like an easy solve, well-suited for dc. The challenge was, given a positive integer, return the nearest Fibonacci number. The Fibonacci sequence is fun on its own in a stack language; in dc one step can be performed with something like dsf+lfr. Given that the stack is prepared with two integers, this will duplicate the top, store it in an intermediate register f, add the two previous values, push f back onto the stack, and then swap them such that they’re in the correct order. It doesn’t pollute the stack, either, these two values are all that remain.

For this challenge, those two values are all I ever need – my input (which I will refer to as i) is always going to fall between two consecutive numbers in the Fibonacci sequence (or on one of them, in which case I would only need that value to test against). Keeping as much work on the stack as possible is ideal when golfing in dc because the byte cost of working with registers adds up quickly. So my strategy is to seed the Fibonacci generator with two 1s, and run it until the larger of the two Fibonacci numbers is greater than i. One of those two Fibonacci numbers will be the right one, and if i happened to be a Fibonacci number, I’ve just generated an extra one for no reason. I convert both of the Fibonacci numbers to their respective differences from i. Since I know for a fact that the top of the stack is greater than i, and the second value on the stack is either less than or equal to i, I don’t have to worry about dc’s lack of an absolute value mechanism; I simply subtract i from the big one and subtract the small one from i. Since I know which difference is which, I have no need to retain the Fibonacci numbers. I simply compare the differences, and then reconstruct the Fibonacci number by adding or subtracting the difference to i depending on which difference ‘won’. The code:

?si1d[dsf+lfrdli>F]dsFxli-rlir-sd[lild-pq]sDdld<Dli+p

…and the explanation:

?si                  Store user input in register i
1d                   Push 1 to stack, duplicate it to seed Fibonacci sequence
[dsf+lfrdli>F]dsFX   Macro F: Fibonacci generator as described above, with the
                       addition of loading register i and continuing to run F
                       until the top-of-stack Fibonacci number is larger than i
li-                  Turn our high Fibonacci number into its difference
rlir-                Swap the stack, and turn our low Fibonacci number into its
                       difference. The stack stays swapped, but it doesn't 
                       matter
sd                   Store our low Fibonacci difference in register d
[lild-pq]sD          Macro D: reconstruct the low Fibonacci number by 
                       subtracting d (the difference) from i; print the result
                       and quit. Macro is stored for later use.
dld<D                Duplicate the high Fibonacci difference and push the low 
                       Fibonacci difference onto the stack. Compare them and run
                       D if the low difference is less than the high difference
li+p                 Else, add i to the high difference and print the result


Scaling visualized data using common multiples

How we’re presented with data skews how we interpret that data. Anyone who has read a lick of Tufte (or simply tried to make sense of a chart in USA Today) knows this. Many such commonly-encountered misrepresentations tend to relate to scaling. Volatility in a trend line minimized by a reduction in scale, perspective distortion in a 3D pie chart, a pictograph being scaled in two dimensions such that its visual weight becomes disproportionate – technically, the graphic may accurately line up with the values to be conveyed, but visually the message is lost.

In taking mandatory domestic violence training at work recently, I was thrown completely off by a statistic and accompanying graphic. The graphic (albeit using masculine and feminine silhouette images) resembled:

♀♀
♂♂♂♂♂

…with the corresponding statistic that one in every four women and one in every seven men has experienced domestic violence. While the numbers made sense to me, it took me a while to grasp them, because the graphic was simply showing more men than women. It’s something akin to a scale problem, our brains are going to see the obvious numbers – four and seven – instead of readily converting the graphics into their respective percentages. How to fix this, then?

♀♀♀♀♀♀♀♀♀♀♀♀♀♀
♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂

If we simply repeat our graphics such that the total number in either set is a common multiple, now it’s much simpler to process the information that we’re supposed to process. We might not immediately recognize that seven in twenty-four is the same as one in four, nor that four in twenty-four is the same as one in seven, but we do know that seven is greater than four (which caused the problem in the first place earlier), and now we’re not dealing with mentally constructing percentages from a simple visual.


A chessboard for pebbling

Another post inspired by Numberphile. This one, specifically, is in response to a game presented by Zvezdelina Stankova in this introductory video on ‘Pebbling a Chessboard’, and three others that I’ll link to in a bit. Not right away, though, because she explains the game and then pauses for a bit so that the viewer can try to figure it out for themself. My way of doing this was to whip together a bit of a web game.

I’ll do a few explanations of my web version here before the reveal. The core game is one of checkers on an infinite checkerboard; pull a checker and place one up and to the right. Can’t pull one if you can’t do the placement. In my web version here, we’re reflected on the horizontal, so we’re going down and to the right. Much simpler to implement. The initial grid is 20x20, but it expands infinitely whenever a checker nears a border. Game is after the jump, I recommend watching the beginning of the previously linked video, and then playing around. That was why I made this. If you play around a bit, then eventually you can scroll down for more thoughts, I suppose. I think the board is tall enough so as to not accidentally spoil anything.


Arbitrary precision

I use dc as my day-to-day computer calculator because it’s RPN, it’s there, and I know its language. But as I was watching this Numberphile video from a few years back on the 1998001 phenomenon, I remembered that dc is capable of arbitrary precision. I don’t think about this much, because it’s rare that I actually need 3000 digits of precision, generally I just sort of start my session with 4k so I know I’m getting something past the point. It was fun, however, to run dc -e '3000k1 998001/p' and see a full cycle of its repeating decimal instead of something like 1.002003004×10-6.


Musical numbers (external)

Music is, at its very core, mathematical. Harmonics are ratios; rich sounds are produced as a result of the interplay of fundamental frequencies and partials. Some, like Tom Johnson and Seth Horvitz, have been far more explicit in their use of mathematics as composition. While searching for something else on The On-line Encyclopedia of Integer Sequences, I was incredibly pleased to find the linked page, which generates a MIDI file from any of the OEIS’s sequences. Handful of curated sequences on the front page, but even beyond that it’s all great fun.


Pi from pi (external)

It briefly occurred to me last night that pi might be random enough so as to be used as a random number table for a Monte Carlo simulation approximating pi. Looks like Rhett Allain over at Wired had the same idea 4.5 years ago. He used 25,000 samples, which is woefully low for a Monte Carlo simulation, so I’m not sure how much the (obviously lacking) results say about randomness in pi. Nevertheless, it’s a fun idea and a fun read with some graphics illustrating a random distribution vs. the distribution of pi.


Collatz sequences in dc

Inspired by this recent post and code snippet by John Gruber, I decided to have a go at outputting Collatz conjecture sequences in dc. Running

    dc -e '?[r3*1+]so[d2~1=opd1<x]dsxx'

from the command line will take a single value as input, and run the sequence. ? takes input, puts it on the stack. [r3*1+]so is our macro for n3+1, what we do when we encounter an odd value. [d2~1=opd1<x]dsxx is our main macro, as well as our macro for handling even numbers (n/2). First it duplicates the value on the stack (last iteration) and divides by 2 to return the quotient and the remainder. 1=o uses the remainder to test for oddness and run o if true. Here I do something rather lazy for the sake of concise code: that initial duplication was solely for the sake of oddness. o swaps the top of the stack to get that value back, then multiplies by three and adds one, leaving this value on the stack. Evenness will never run this, and since the test for evenness leaves the outcome for evenness on the stack (what luck!), and the initial duplication is below it. Either way, the bottom of the stack is going to fill up with a lot of garbage, which should be inconsequential unless our sequences become absurdly long. At this point, the top of our stack is the result of the current step, so we print it, duplicate it, and run x if it’s greater than 0. Finally, we duplicate our main macro, save it as x, and then execute the copy we left on the stack.


dc

This is an old post from an old blog; assets may be missing, links may be broken, and my opinions may differ considerably by this point…
Even though I generally have an HP or two handy, the POSIX command-line RPN calculator, dc, is probably the calculator that I use most often. The manpage is pretty clear on its operation, albeit in a very manpagish way. While the manpage makes for a nice reference, I've not seen a friendly, readable primer available on the program before. This is likely because there aren't really people lining up to use dc, but there are a couple of compelling reasons to get to know it.

dc Syntax for Vim

This is an old post from an old blog; assets may be missing, links may be broken, and my opinions may differ considerably by this point…

I use dc as my primary calculator for day-to-day needs. I use other calculators as well, but I try to largely stick to dc for two reasons - I was raised on postfix (HP 41CX, to be exact) and I'm pretty much guaranteed to find dc on any *nix machine I happen to come across. Recently, however, I've been expanding my horizons, experimenting with dc as a programming environment, something safe and comfortable to use as a mental exercise. All of that is another post for another day, however - right now I want to discuss writing a dc syntax definition for vim.