./ahmedhashim

Patterns that occur in life and nature are often non-linear. From comparing frequencies of notes on a piano to Moore’s Law, logarithms provide a way to measure values extremely far apart from one another. When building tools for society, this can also be a useful property to map nuanced human behavior at scale.

Normalizing magnitude

Simply put, a logarithm is the inverse function to exponentiation. In other words, it’s the power y to which a base number x must be raised to in order to get the argument z:

$$ x^y = z \ \iff \ \log_{x} z = y $$

This makes comparing large ranges of numbers easier by normalizing the distance between extremely small and extremely large values in the range according to a regular base interval.

For example, Reddit uses a logarithm in its hot ranking function to decide which posts appear on the homepage. Specifically, it weighs the first 10 votes on a post the same as the next 100. Those 100 in turn weigh the same as the next 1000, and so on for every magnitude of ten thereafter (10 being the base).

As the votes increase by orders of magnitude, the weight between each order remains the same. This helps to mitigate a “pile-on” effect on post submissions which may occur through brigading.

In other words: Logarithms can be used to clamp linear growth.

Floating in Solidity

While working with Solidity, the smart-contract programming language for Ethereum, I found myself in a similar situation. I needed a function to rank a post in a microblogging dApp based on the number of “likes” it had.

My initial plan was to take the logarithm of likes in order to normalize its value in the ranking function. However, I quickly learned that solidity doesn’t natively support logarithms due to the EVM’s lack of floating point numbers.

To put it bluntly, it’s because implementing floating point types consistently across programming languages is difficult.

Different implementation of the same function could possibly return slightly different values. This is largely due to how the language handles binary arithmetic under the hood to represent floats as decimals. If you’ve worked with one such language, you might have come across this familiar example:

0.1 + 0.2 = 0.30000000000000004

Ethereum clients (aka “nodes”) are written in a variety of languages. If floating point types were used in the consensus mechanism across polyglot nodes, they might arrive at different values. This would cause forks to occur, and over time, will weaken the cumulative strength of the network — leaving it vulnerable to 51% attacks.

Now that we understand the “why”, it still poses the question: how does one perform logarithms in a language that doesn’t support floating points?

The key lies in understanding how computers represent numbers — namely, in binary.

Fixed imagination

Take the number 3 represented by four bits:

0011

Using bitwise shifting, we can double the value by shifting to the left, or half it by shifting to the right. So in order to multiply by 2, we shift each value to the left by 1 bit, thereby doubling it to arrive at a binary value of 6:

0011 << 1 == 0110 // 6

But suppose we wanted to go the other way and divide by 2 instead? Shifting the value right by 1 drops the least significant bit from the memory register, and we’re left with a binary value of 1.

0011 >> 1 == 0001 // lost the least significant bit

How can we represent the decimal value 1.5 in binary?

Let’s rewind & break down exactly what’s going on in the original four bit representation:

0011 == (0 * 2^3) + (0 * 2^2) + (1 * 2^1) + (1 * 2^0)

Which equals 3.

Notice that each bit is represented by a power of 2 decreasing, until it gets raised to the power 0 in the least significant bit. If we continued the series past the last bit, it would look like the following:

(n * 2^0) + (n * 2^-1) + (n * 2^-2) + ...

We know 2^-1 is equal to 0.5, and 2^-2 is equal to 0.25, so we’re heading in the right direction! But how can you represent a number lower than 2^0 in binary?

Picture an imaginary decimal point in the middle of the four bit value representing 3:

00.11

Applying the same formula, this would be equivalent to:

0.75 == (0 * 2^1) + (0 * 2^0) + (1 * 2^-1) + (1 * 2^-2)

Not quite the answer we’re looking for, but getting closer.

What if, before placing the imaginary decimal point, we left shifted the original value by half the bits available? (2 bits in this example):

0011 << 2 == 1100

The computer sees this value as 12. However, we’ll continue to use our imagination to place a decimal point in the middle of the four bits to split our whole numbers to the left of it, and fractional values to the right.

11.00

This lets us pretend we’re back at the bit representation of 3, along with space for our fractional values.

Now if we right shift by 1 in order to divide in half, we’re left with:

11.00 >> 1 == 01.10

Giving us a value of 1.5 in our minds. We did it!

However, regardless of our shift, the computer still isn’t aware of the decimal point:

0110 // 6

As it turns out, this doesn’t matter!

Deja Q

In order to perform floating point calcuations in binary, we need to reserve an arbitrary amount of bits representing the fractional component for all numbers in the equation.

This amount is known as the Q-value. The higher the Q, the more floating point precision there is to work with.

To summarize: we fix an imaginary decimal point after a specific amount of bits in the space available to represent the fractional number, hence the term “fixed point”.

If every number in the calculation has the same Q, then the final result will be the desired value with the same imaginary fixed point.

It can be shifted back by the Q amount to get its (accurate enough) integer representation for display purposes. However, if displaying the value isn’t required, then keeping all the calculations in fixed point will be more precise.

The accuracy of the result will depend on the precision involved. Namely, how high the Q is (usually determined by the amount of memory & compute you have to work with). Luckily the IEEE-754 standard exists to serve as a guide on this matter.

Equipped with this knowledge, we can now take logarithms in Solidity by converting our integers to fixed point values.

Shifting perspective

Since we’re working with fixed point binary numbers, a binary logarithm is a good place to begin (that of base 2). They can be represented such that 2 to the power y is equal to x:

$$ 2^y = x \ \iff \ \log_{2} x = y $$

Which means, in order for y to exist, x must be a positive number. To calculate the integer component of the log (the bits to the left of the fixed point), we can use the following formula for a positive integer x:

for (n = 0; x > 1; x >>= 1) n += 1;

On every loop, we count an additional order of magnitude represented by n, and right shift x until it’s past the least significant bit. Since the orders in a binary log are powers of of 2, bit-shifting is an efficient way to update the value.

If x itself is a fractional number, we can factor it into a mantissa multiplied by an exponent:

$$ x = m \times 2^{e} = \log_{2} m + e $$

and use the above loop to calculate the binary log of the mantissa, then add the exponent to it.

Too close for missiles, switching to guns

On the right side of the fixed point, we have the fractional part of the number x. Since we know it must lie between the orders of magnitude represented by the integer n that we calculated in the previous step:

$$ 2^n \ \leq \ x \ < \ 2^{n+1} $$

then using the properties of logarithms, we know that x is at least 1, and less than 2:

$$ 1 \ \leq \ \frac{x}{2^n} \ < \ 2 $$

Recall that the fractional values on the right side of the fixed point were calculated by 2 * x^-n where n starts at 0 decreasing for every bit m. Each bit’s value can be represented as:

$$ 2 \times \frac{x}{2^{n-m}} $$

So we’re looking for the binary logarithm of that fraction for every bit of precision available:

$$ \log_{2} \frac{x}{2^n} \ + \ \log_{2} \frac{x}{2^{n-1}} \ + \ … $$

In order to find such a number, we’ll use another two properties of logarithms:

$$ \log_{2}x = \frac{\log_{2}x^2}{2} \ = \ 1 + \log_{2}x \frac{x}{2} $$

Based on a specific level of precision, we can use the following code to calculate the fractional value:

for (delta = 1; delta >= precision; delta /= 2) {
  if (x >= 2) { result += delta; x /= 2; }
  x *= x;
}

Every loop applies the first property of squaring x, and halfing the delta until x is equal to or greater than 2. At that point, you save the current delta as part of the result, divide x in half & keep repeating until the delta value has fallen below the level of precision desired.

What results is a function that converges towards the fractional value of x.

Reinventing the wheel

Unfortunately, the last bit of code won’t accurately work in Solidity due to the lack of floating points. Instead, one would have to write a library to perform integer math for a specific Q value of the number that you’re taking a logarithm of in order to reach the desired result.

Fortunately, this exists in the form of ABDK Libraries for Solidity.

Not only does it perform binary logarithms, it can also take the natural log, exponent, and other useful floating point calculations) all with 64x64 fixed point or 128x128 IEEE 754 quadruple precision.

If a common logarithm (base 10) is required, you can use the following property to compute it from a binary log:

$$ \log_{10}x = \log_{2}x \times \log_{10}2 $$

the common logarithm of 2 can be precomputed ahead of time as:

0.3010299956639811952137388947244930267681898814621085

or in 128x128 bit quadruple precision hexadecimal format:

0x4d104d427de7fbcc47c4acd605be48bc

By multiplying the fixed point binary log of a number with the above hex value, common logarithms can be calculated in Solidity.

Going further

Now that we’ve unlocked the secrets of fixed point calculations in a language without floating point types, a world of opportunity is available to us.

I was able to use natural logarithms in the microblogging dApp to clamp my “likes” after all. But that’s only scratching the surface of what could be done with the power of floating point precision on the EVM.

Some interesting ideas I’d like to see implemented in Solidity using logarithms would include:

• Richter scale prediction dApp
• pH values of water by geolocation
• Decible meter
• Fast inverse square root algorithm for polygons

Relief-fund contracts for crises like earthquakes or contaminated water zones? A peer-to-peer digital audio workstation that incentivizes collaboration? John Carmack releases Quake 4 on the EVM?

What can you think of next?