A Snake game entirely written in assembler

Snake is always been for me my hello world program. I implemented it in many different languages Basic, C, C++, Java and Javascript. But I didn't limited myself at high level languages. At the second year of university (something like 7 years ago) I actually implemented it entirely in assembler MASM in roughly 600 lines of code. It is so old that the variables and the comments are in italian :)

Unfortunately I can't run it (and provide a screenshot of the game) because is using a library called compatib that I am not able to find. Friends can confirm that this code actually worked at the time :)

This is the main procedure:

This is the game loop:

This is the procedure that print the snake on the screen:

The entire code is available in my repository on copeplex.

This program is very old but I still remember the feeling after I implemented it in one evening and in particular the satisfaction of the following day when I showed it to my class mates. They were shocked!

This is what I call fun!

BigInteger multiplication - A recursive approach

Recently in the Coursera course "Algorithms: Design and Analysis, Part I" I come across to an interesting introduction of the divide and conquer technique using the multiplication between big integers as an example. My hands started to itch immediately. I would have to try to write an implementation!

The Problem

Given two integers x and y of any size return the product of them.

The Idea

The simplest algorithm is what we are all used to do, writing down all the products and then add them together. This is know as the "Long Multiplication" algorithm.

Using a simple calculus is easy to understand that the problem can be solved using a recursive approach. 

It is always possible to write x and y in the following way:

So the product can be calculated as:

This means that we can calculate the product xy calculating 4 small products (ac, ad, bc, bd) in a recursive way.

More info:

http://en.wikipedia.org/wiki/Multiplication_algorithm

The Implementation

For simplicity, I decided to represent a number using a string encapsulated in a class called MyBigInteger.

This is the implementation of the multiplication algorithm in C#:

In order to implement the algorithm I also had to implement the sum between two big numbers using the classic mathematical way:

The full code is available in my personal repository (BigIntegerMultiplication).

Tests

Improvements

In this example, we have a recursive tree with 4 branches. In reality it is possible to have only 3 branches using a simple trick (Karatsuba multiplication).

Instead of calculating ac and bd directly it is possible to calculate first:

and then calculate (ad + bc) using a subtraction:

In order to implement this slightly improved version of the algorithm is necessary to implement the subtraction of two big integers. I didn't wanted to do it, so I don't have an implementation to share.

Conclusion

The purpose of the exercise was to prove to myself that I was able to build the algorithm based on the original idea presented in the course. I would like to let the reader aware that the .NET framework already implement a comprehensive class that implement the operations on big integers in a quick way: BigInteger.