Discovering fixed point

I told a story today in class about my own personal learning experience with regards to figuring out how do to fractional mathematics with integers (also known as fixed point math).

While I was relating this story about my personal exploration of programming at the age of 15 or so, a student asked “Why didn’t you just use fixed point”. I had to point out that I had to work out fixed point for myself, because I had to teach myself, there was no one who could teach me.

It just occurred to me that the student may not have fully appreciated the situation. Sure it’s obvious *now*, but imagine what it was like for me about in around 1980 or so. When I said it took me years to figure out (it was about 2 years) I can now imagine students running around saying “It took Mr. Dini 2 years to understand fixed point!”. Talk about a teacher digging a hole for themselves *sigh*. An explanation is in order.

The truth is that I invented fixed point… for myself in my own little world. Sure other people also invented fixed point. But to be clear, since I worked it out on my own, I did invent it. For me. Stick with me, it’s not as strange as you might think…

First of all, I was programming on an 8 bit microprocessor (a 6502) in assembler on the BBC Micro, which had a 2 Mhz processor. I wanted to write an asteroids clone. The 6502 did not have a floating point processor. Floating point math routines were possible to code in assembler, but they were very slow: too slow for a 50 FPS game, where the graphics also had to be blitted in software.

It took me about 2 years to figure out the correct solution to the problem of how to emulate real numbers with only integers. The idea is of course very simple: You just scale everything up. One way of thinking about this is to imagine working on a much higher resolution than the screen. I can’t remember the BBC Micro resolution I used, but it was something like 320×240 (I had to use a black and white display to keep the resolution that high). Well, instead of having the program work internally on a pixel resolution, I can make it work on an internal resolution of 32000×24000 for instance. If I do this I can have the sub pixel accuracy that allows me to move in more than 8 directions… essential for an asteroids clone. Then when drawing, you simply divide the internal coordinates down to screen coordinates.

Obvious? Perhaps, as I said, it is now. How should people learn about this stuff? Oh I guess you can ask on a forum, or search google, or look on wikipedia. Perhaps that student today was thinking “eh? It would take be no time to find that out! Who does this guy think he is blah blah”. Well I don’t know if you have spotted the flaw in that potential argument yet… anyway carrying on…

One day, as I was experimenting, it hit me. I could see the idea of internally having a much higher resolution. And… a way of implementing the scaling down in assembler so that it would be very fast.

If my play field is 256×256 pixels, then a coordinate axis (X or Y) can be held in a single byte. But if I use two bytes (and of course write the code to chain adds together using “add with carry” instructions: 8 bit processor, remember?), I can then work internally at a resolution of 65536×65536 ‘pixels’. And the real beauty of this is that I can simply read the most significant byte, and thus not even have to divide it back down by using shift instructions!

And this is how I invented fixed point… for me. No, I did not read about it. I did not have someone who told me. I was on my own, closed off from the rest of the world of computers, in my bedroom writing games and figuring it all out for myself.

So I hope you spotted the flaw I mentioned: not only was there no one to teach me, but there was no Google, there were no forums, there were no books on game programming, there were no mentors, teachers, twitter, YouTube, Wikipedia, mobile phones…

All there was was a 15 year old geeky kid with a 2Mhz 6502, 32K of ram, the BBC Micro programming manual and a cassette tape recorder to record my programs on and a strong desire to write an asteroids clone (which was later actually published).

So, I simply had to invent fixed point.

2 Responses to “Discovering fixed point”

  1. Sébastien Sénégas Says:

    Very nice story Dino, remember me many things also from this period /-)

  2. stevebt Says:

    Yeah, nice story. Funny, I was talking to one of my contract PLC programmers about the BBC B onMonday… He’s reverse engineering a PLC for me at the moment. I was telling him as a geek kid I reverse engineered the BBC OS and found all of Acorn’s undocumented system calls :o)

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: