Monthly Archives: May 2014

Fibonacci in FRACTRAN

I’ve always found esoteric programming languages pretty amusing – they’re silly, occasionally witty, but most of all there’s the ones which take a lot of thinking, like Golfcode or Whitespace.

Today I had a bit of fun and tried writing a Fibonacci number generator in FRACTRAN. FRACTRAN, invented by the infamous John Conway, is a programming language where programs are just a list of fractions, and input is a single positive integer n. At each iteration, n is updated by multiplying it by the first fraction in the list which results in another positive integer, until this is no longer possible.

For instance, one of the simplest FRACTRAN programs is just:

3/2

Given input in the form of n = 2a × 3b, the program will continue multiplying n by 3/2 until n is no longer divisible by 2. This will happen when n is of the form 3a+b, so the single instruction program 3/2 is actually an addition program which stores the result of a+b as the exponent of 3 in the output.

The reason why FRACTRAN works is that what you really have is a bunch of registers labelled by prime numbers. For example, 3072 = 210 × 31 represents a state where register 2 has the value ten, and register 3 has the value one. Each fraction is then an instruction to increase or decrease the register values, provided that the result doesn’t make any register have a negative value. So for 3/2, if n is divisible by two then register 3 is incremented by one and register 2 is decremented by one. This shows how if statements are possible in FRACTRAN.

The Fibonacci program I wrote is the following:

39/55 33/65 78/77 66/91 1/11 1/13 5/2 7/3 11/1

The program starts with the initial value 3 = 20 × 31 and if at any iteration a number of the form 2a × 3b appears, then a and b are successive Fibonacci numbers.

It’s my first FRACTRAN program so it could probably be improved, but hey I’m pretty happy that I got it working. The hardest part was figuring out how to do loops in FRACTRAN, which is a surprisingly tough challenge.

My program works like so:

  • Initially, registers 2 and 3 store a and b respectively, which are consecutive Fibonacci numbers (with a < b by the initial condition).
  • a and b are then transferred to registers 5 and 7 respectively.
  • a is added from register 5 to register 2, while b is added from register 7 to both registers 2 and 3.
  • The result is that registers 2 and 3 now hold b and a+b respectively

This is how the fractions work:

  • 11 and 13 are indicator variables. If either of the registers are set to something nonzero, then one of the first four fractions will trigger, either subtracting 1 from register 5 and adding 1 to register 2, or subtracting 1 from register 7 and adding 1 to both registers 2 and 3. There’s two indicator variables because I couldn’t figure out how to do loops well – here registers 11 and 13 alternate from being 0, 1 and 1, 0 respectively so that one of them will always be set while this addition step is being performed.
  • This addition will continue until n is no longer divisible by 2 or 3, in which case 1/11 and 1/13 nullify the indicator variables
  • After this, 5/2 and 7/3 do the transferring from registers 2,3 to registers 5,7
  • Once the transfer is complete, 11/1 retriggers the indicator variable and we go again

Of course, if you want the program to actually terminate, then a slight modification can be made (to make register 2 the only input, the other registers got shifted up by one):

85/91 65/119 255/143 195/187 1/13 1/17 7/3 11/5 13/2 1/11

This version takes in input of the form 2n × 5 and returns 7F(n).

I think the nice thing about FRACTRAN is how easy programs are to explain to people, even if they don’t do computer science. Unfortunately though, explaining how the program actually works is a lot harder.

For some additional FRACTRAN trivia, somebody actually created a FRACTRAN interpreter in FRACTRAN, which goes to show that even a language that is easy to describe can be capable of quite a lot.

Advertisements

Project SDVX: Part 2

← Part 1 | None 

A lot of loot

A lot of loot

I came home today to find, with joy, that my Sparkfun shipment had finally arrived. Sure it took a while, but to be fair I did choose the cheapest shipping option.

What I got was:

  • A pack or resistors, because I have no idea which ones I’ll need. In fact, I have no idea how to work out which ones I’ll need either, but I’ll figure that out somehow.
  • A new breadboard, because I like having an entire column for for + and – voltage. It makes breadboarding much easier (my previous breadboard only had rows of 5 holes).
  • An Arduino Uno, to program the rotary encoders.
  • 3 rotary encoders and 3 knobs. I bought one extra just in case one breaks, because Sparkfun shipping is not the cheapest out there. These ones have a clicky feeling as you turn them, which from memory is different from how the arcade knobs feel.
  • Some wire, just in case.

I probably didn’t need the resistors, breadboard and wire, but I thought that I might as well get a few more things while I was at it.

The Arduino really is quite small. Here’s a comparison with my favourite Pilot ballpoint pen.

The box this came in was probably small than a deck of cards

The box this came in was probably small than a deck of cards

Unfortunately, as much as I’d love to start testing the rotary encoders straight away, I can’t yet. The first reason is because I’ll be busy for the next few days, but the second and bigger reason is that I don’t have a USB cable.

Yes, I should have checked when I bought it.

So now it’s time for a bit more waiting while I buy a USB cable for my Arduino. Meanwhile I’ll also have to figure out is how to use the rotary encoders – there’s about 8 pins on the bottom and I need to look up which one’s which. Also, it doesn’t actually fit in the breadboard so I can’t test it that way – it looks like I’ll need to attach wires to it directly.

Oh and the BT buttons from last time? I gave up and bought the round ones. Saves me money that way.

Perfectionism wishes restrained by monetary budgets

Edit: After a few minutes of research leading to Sparkfun’s USB buying guide, it appears that what I need is a USB-A to USB-B cable, which isn’t necessarily designed specifically for the Arduino. In fact, my printer cable is exactly that type, so it looks like I won’t need to buy any cables. I still can’t play around with the encoders any time soon though, due to being busy for the next few days.

← Part 1 | None