The Bistromathique is an Arbitrary Precision Calculator EPITA project where the main focus is optimization. The input can be in any base (up to 250) and the following operations have to be performed: Addition, Subtraction, Multiplication, Division, Modulo.

Base Representation

Going back and forth a textual representation to a computable representation is the first part of the project and several optimizations are possible at this step.

Binary Representation

Encoding the numbers as binary allows you to make the best use of the processor calculation unit. There is no space lost and the number being represented as an uninterrupted series of 0 and 1 can be added and subtracted directly with the hardware.

However, in order to convert the number for a base B representation to a base 2 requires roughly n divisions by B. And to reconvert it back requires another n multiplications. This can be affordable for applications that uses the same numbers again and again but in our case, this cost is prohibitive.

The other major drawback is that you are required to have the multiplications and divisions (and therefore addition and subtraction) in order to have the numbers in the right form to start working on the operations ... In summary, you have to code all these operations before being able to test them!

char Representation

The binary representation not being possible, the solution that comes in mind is to put each digit into a char (8 bits). Since we are limited up to a base of 250, any base will fit. This comes at a price, there is a lot of space wasted, and it increases as the base size decreases.

We are in a 1 to 1 relation between the input and the represented number, this way we can store the represented number inside the input. This prevents from allocating memory at this step. The conversion can be efficiently done, each character goes through vector of 256 slots storing its representation and a magic value used as a non valid input. One final trick is to add a non number at the end of the input to remove a end of input check in the loop.

Filling more

A char can store values up to 256. If we are working on base 16 we could store two digits into 1 char and thus divide by 2 the number of digits. Additions are therefore 2 times faster and even more for n log n operations such as multiplication.

Calculating the number of digits to fill into a char is quite straightforward however some caution has to be taken during the transition. We have to know in advance the length of the input to decide how to start filling the digits. If you can fit 2 digits per char, if the number is even then it goes as expected, but if the number is odd you have to place 0 at the beginning to fill the gap.

Even: [1] [2] [3] [4] -> [12] [34]
Odd (Naive): [2] [3] [4] -> [23] [4?]
Odd (Smart): [2] [3] [4] -> [02] [34]

This method works well but requires 2 passes for each number and a special case at the beginning of each number. Not enough to stop us from using it.

Using a larger representation

Now that we filled the char at its maximum, why stick with it? This should ring a bell since you know that common architecture is 32-bit, and from now we are talking about a 8-bit representation. We would be tempted to change the char to an int (32-bit) or even a long (64-bit) that could benefit from register optimizations.

Moving away from a char, we lose the assumption that the output being smaller (or equal) than the input. Without it, this is no longer possible to work in place. We now have to compare the cost of a reduction in the number of operations and the cost of the memory allocation.

The overhead happens for values that are represented in less than 4 characters for an int representation. This is a maximum 3-characters overhead possible for each number, which is negligible. We could eat the operation character but we are left with 2 characters. I haven't found a solution to stay in place yet and this minor problem prevents from accessing a great speed up.

To be continued ...

If you liked this article, you might be interested in my Twitter feed as well.
 
 

Related Posts

  • August 7, 2009 SmallHash – Information Compression (1)
    SmallHash encodes any range of integers into the smallest possible string. This way, you can use the hash part of your url with efficiency.
  • August 4, 2009 Project – MMO-Champion Optimization (0)
    MMO-Champion is the biggest news website of World of Warcraft. The main page is viewed millions times a month and was done with old school tables. As a result, it was really slow to load but worse, all the content had to be loaded before being displayed. The first thing I did was […]
  • August 4, 2009 Project – Shortest Path (0)
    A school project was to find the shortest path in a dungeon graph. You start with an amount of hit points, and each edge gives or removes hit points. You have to find the path from two points going through the minimum of edges (no matter their value) alive (hp > 0 all along the path). […]
  • December 24, 2009 Guild Recruitement – Search Optimizations (0)
    In World of Raids Guild Recruitment Tool, we wanted the search to be instant! We achieved this goal by not having a single page refresh or ajax call while updating the settings. Since it runs in the browser, performance was a real concern. We will see in this article what were the tricks […]
  • August 10, 2009 Speed Up Javascript Sort() (1)
    By overriding the toString Object prototype, it is possible to speed up by 5x the sort function. This is an easy to implement trick that gives astonishing results I wanted to know if there were ways to speed up the Javascript Sort function. I came across an interesting article (Yet […]