Magic of Floating Point Representation in the Digital World

Many great engineering and scientific advances of recent decades would not have been possible without the floating-point capabilities of digital computers. Still, some results of floating-point calculations look pretty strange, even to people with years of mathematical experience. I will attempt to explain the causes of some of these strange results and give some suggestions where appropriate.
Lets take a look at the following example :

groovy> System.out.println(100.87d * 0.01d)

1.0087000000000002    --> Oops ! What is happening here ?

groovy>

We all know 100.87 multiplied by 0.01 is 1.0087. How is this junk introduced. Lets look at the following statements to add more confusion:

groovy> System.out.println(100.87f * 0.01f)

1.0087000049196178

groovy> 

groovy> System.out.println(100.87 * 0.01)

1.0087

groovy>

To answers these questions lets go to the basics.

How are floating point numbers represented in the modern computer systems and how is arithmetic done. As we all know, floating point numbers are represented in binary format which follows IEEE standard for floating point arithmetic. 

The format for single precision numbers uses 32 bits divided in the following way,

     seeeeeeeefffffffffffffffffffffff
     
     s = sign bit, 1 bit
     e = exponent, 8 bits  (E_min=-126, E_max=127, bias=127)
     f = fraction, 23 bits

The format for double precision numbers uses 64 bits divided in the following way,

     seeeeeeeeeeeffffffffffffffffffffffffffffffffffffffffffffffffffff
     
     s = sign bit, 1 bit
     e = exponent, 11 bits  (E_min=-1022, E_max=1023, bias=1023)
     f = fraction, 52 bits

The above problem is because some numbers can't be represented exactly in this format.

(100.87)10 = (1100100.11011110101110000101000111101011100001010001111010111000010100.........)2

When we say 100.87d, it means 100.87 is stored in a double variable which has 64 bit precision and when we say 100.87f, it means 100.87 is stored in a float variable, which has 32 bit precision. So even though 100.87 is a real number, it can't be exactly represented in binary format. This poses a big challenge to programmers in financial domain where accuracy is very important. So if you normalizing a price of 100.87 with a scale of 0.01, you would introduce noise as seen above. Mostly what programmers do is rounding to some significant digits based on the requirement. 

A key feature of the IEEE standard is that it requires correctly rounded arithmetic operations. Very often, the result of an arithmetic operation on two floating point numbers is not a floating point number. This is most obviously the case for multiplication and division; for example, 1 and 10 are both floating point numbers but 1/10 is not, regardless of where the single or double format is in use. It is also true of addition and subtraction.

Let x and y be floating point numbers, let +,−,* ,/ denote the four standard arithmetic operations, and let (+),(-), (*), (/) denote the corresponding operations as they are actually implemented on the computer. Thus, x + y may not be a floating point number, but x (+) y is the floating point number which is the computed approximation of x + y. When the result of a floating point operation is not a floating point number, the IEEE standard requires

that the computed result is the rounded value of the exact result. It is worth stating this requirement carefully. The rule is as follows: if x and y are floating point numbers, then

x (+) y = round(x + y);

x (-) y = round(x − y);

x (*) y = round(x * y);

and

x (/) y = round(x / y)

where round is the operation of rounding to the nearest floating point number in the single or double format, whichever is in use.

Now lets explain the behaviors seen in my cases presented at the beginning.

groovy> System.out.println(100.87d * 0.01d)

1.0087000000000002

groovy> System.out.println(100.87f * 0.01f)

1.0087000049196178

groovy> 

100.87 is not exactly representable in binary, same is the case with 0.01. We represent an approximation of these numbers in binary. The rule is if a number is not exactly representable, then it must be approximated by one of the nearest representable values. So, when we are multiplying 100.87 with 0.01 in the above case, we actually are multiplying some approximation of these numbers and that's why we the junk. This is expected. But what about the below case. What is happening here ?

groovy> System.out.println(100.87 * 0.01)

1.0087

groovy>

In the above case we are not storing the intermediate values in any variable and hence no rounding is done. They are stored in registers and hence we are getting better precision. To prove my point analyze the following cases:

groovy> System.out.println((float)(100.87f * 0.01f))

1.0087

groovy> System.out.println(100.87f * 0.01f)

1.0087000049196178

groovy>

In the 1st case you are putting the value in a float variable and then printing. In the 2nd case, you are directly printing the value in the registers.

HipHop for PHP

HipHop for PHP is a source code transformer for PHP script code. Hiphop for PHP is a set of PHP execution engines. HipHop started as project at Facebook Inc. and was later made open source. Till date, facebook has achieved 6X reduction in CPU utilization for its site using HipHop as compared to Apache.

One of the design of HipHop was to write complex logic with PHP. Since PHP is an interpreted language, it is bound to be slow. Companies like Facebook which have large PHP codebases would have to write their complex functionality with extensions in C or C++. This would lead to lesser amount of resources which could work on the complete codebase. By continuing to use PHP with HipHop Facebook is able to maintain a high number of engineers who can work on the whole codebase.

HipHop has evolved over the years. Initially it started as 'HPHPc' which translates the PHP code to C++ code and  then passes it to gcc which compiles it into one monolithic binary representing the site's entire code tree. This gave significant performance gains, but it was horrible for development. The most important reason to use PHP is to avoid having to recompile for every small change, since PHP is a interpreted language.

'HPHPi' came hereafter as an interactive version of HPHP. It had the feature to automatically recompile on changing the behavior, but it led to different behavior in development and production machine which is risky.

HipHop Virtual Machine (HHVM)was created with an intent to replace both HPHPc and HPHPi. HHVM does not call gcc unlike its predecessors. HHVM transforms PHP code to byte code just as regular PHP does. It differs from the regular PHP due to its optimizer and JIT(Just in Time Compilation).

The following article gives a complete picture of HipHop VM :
https://www.facebook.com/note.php?note_id=10150415177928920

Algorithmic Trading - Part 1

Algorithmic Trading is the use of electronic platform for placing trading orders with an algorithm deciding the timing, price and size of orders. High Frequency Trading (HFT) is a special class of algorithmic trading in which trading systems make trading decisions based on the information they receive electronically before human traders are capable of processing the information they observe. 

Who is suited for Algorithmic Trading ?

The most important reason for going for algorithmic trading is to control the market impact while placing big orders and thus seek favorable prices. Anyone who places big orders needs to worry about the market impact. As a thumb rule, if the size of order exceeds the sum of best 5 levels you need to worry about the market impact.  Big institutions like pension fund managers, investment banks, hedge funds, etc. are the ones who place Algo orders.

 Lets see how algorithmic trading minimizes market impact. All the orders placed can be classified either as Market Orders or Limit Orders. Markets orders want the exchange to execute the order in the best possible price. So, if you want to buy, the exchange will find the seller who is willing to sell at the lowest possible price and execute the order. Limit Ordrs on th other hand specify the limit on the negative side. These limit orders are not executed right away and they stay in the book for some time. These live but non executed orders form what is called the order book. Lets say I place a Market Order to buy 1 million Yahoo shares. The exchange will try to find the best seller which is selling at the least price and then the next best and so on, till the I get 1 million shares. This means that the execution price is going to be poor. On the other hand if I place a limit order. Now, the exchange will execute whatever it can but it will stop as soon as there are no more sell side orders with favorable price. Once this is done, your order becomes part of order book.  Once everyone, including other algorithms, sees such a massive order sitting on the buy side, price is bound to rise sharply.

However, algorithmic trading has generally been a sell-side product. This means that institutional brokers are the ones who actually have the systems for placing and managing algorithmic orders. Institutional traders place Algo orders with brokers who submit the orders either programatically from automated systems or manually through user interfaces. Institutional brokers and investors have invested a lot of time and money on Algo trading systems over the years.

Lets look at one of the simplest algorithmic strategies :

TWAP (Time Weighted Average Price) trading strategy :

TWAP breaks a big orders into smaller chucks of orders which are executed after a fixed interval. But a simple algorithm or even a smart trader can figure out this pattern by looking at the order book. So, nearly all production TWAP algorithms involve some type of randomization. This randomization can be done in terms of the sizes of orders or in terms of the intervals between the orders or both. 

The basic rule is to start with an initial order size and keep increasing or decreasing the size of order. The first question that comes to mind is when to increase and when to decrease the size of order. The answer depends on whether the market is in mean reversion mode or is trending towards one direction. If you a buyer and the price continues to drop, then it makes sense to wait for some time as the price is going to be more lucrative. On the other hand, if the market is in mean reversion mode, the trend is not going to last for ever and so we need to increase the size whenever price becomes favorable.

The next question is how to predict the market. Well, truly speaking, nobody can predict the market. We just try to be correct more often than we are wrong. This is where high frequency trading comes into picture which helps us to predict the market by analyzing the market trends quickly.