Math in Solidity (Part 5: Exponent and Logarithm)

This article is the fifth one in a series of articles about doing math in Solidity. This time the topic is: exponent and logarithm.

Mikhail Vladimirov

Published in

Coinmonks

9 min readApr 2, 2020

Introduction

For centuries, logarithm was used to simplify calculations. Before electronic electronic calculators became widely available, slide rule, logarithm-based mechanical calculator, was the symbol of the engineer’s profession.

Logarithmic function, together with exponential function, which logarithmic function is the inverse of, allow turning multiplication into addition and, which is even more important, exponentiation into multiplication. This is possible due to the following two rules:

After exponentiating left and right parts of these equations we have:

Note, that these formulas work for arbitrary positive base b other that one, so we may choose base that is convenient for implementation.

In this article we will show how base 2 logarithmic and exponential functions could be efficiently implemented in Solidity, how these base 2 functions could be turned into corresponding natural (base e) functions, and what are the real use cases for these functions in DeFi applications.

So the focus of this article is exponent and logarithm.

Logarithm

Let’s start with binary (base 2) logarithm. Binary logarithm of x, is the value y such that:

Obviously, the value of x has to be positive for y to exist.

Note, that if

then

so n is the integer part of the binary logarithm of x. Thus, our first question is:

How to Calculate The Integer Part of Binary Logarithm in Solidity?

Spoiler: shift right and count.

Here is straightforward approach that works for positive integer x:

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

While being clear and simple, this method is quite expensive as its gas consumption is O(n). Here is improved version that works for 256-bit positive integer x:

if (x >= 2**128) { x >>= 128; n += 128; }
if (x >= 2**64) { x >>= 64; n += 64; }
if (x >= 2**32) { x >>= 32; n += 32; }
if (x >= 2**16) { x >>= 16; n += 16; }
if (x >= 2**8) { x >>= 8; n += 8; }
if (x >= 2**4) { x >>= 4; n += 4; }
if (x >= 2**2) { x >>= 2; n += 2; }
if (x >= 2**1) { /* x >>= 1; */ n += 1; }

This improved implementation consumes about 600 gas in the worst case: 25 times less than the original, non-optimized one.

So far so good, but

What If X Is Fractional?

Spoiler: just add exponent.

There is no fractional numbers in the core of Solidity language, but there are several ways how such numbers could be emulated. Lets consider two of these ways: binary fixed- and binary floating-point. Both ways represent fractional number x like this:

where m and e are integers. Value m is known as mantissa and e is known as exponent. The different between binary fixed- and floating-point numbers is that for fixed-point number exponent is a predefined constant, usually negative, thus only the mantissa has to be stored; while for floating-point number exponent is variable and thus, it has to be stored along with mantissa.

Now let’s note, that

So, binary logarithm of a binary fixed- or floating-point number could be calculated as binary logarithm of the mantissa, plus exponent. As long as exponent is integer, the same formula also works for the integer part of the logarithm.

Now, when we know how to fund the integer part,

What About The Fractional Part of A Binary Logarithm?

Spoiler: square and halve.

Let n be the integer part of the binary logarithm of x, then fractional part of the logarithm can be calculated like this:

Note, that as long as

then

So, calculating the fractional part of a binary logarithm could be deduced to calculating the binary logarithm of a number between 1 (inclusive) and 2 (exclusive). In order to do this calculation we will use the following two rules:

Here is the code written as if Solidity would natively support fractional numbers:

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

At every iteration, we apply the former rule: square the value of x and halve the value of delta. If at some point value of x becomes greater than or equal to 2, then we applu the latter rule: add delta to result and halve the value of x. We repeat the loop until delta drops below desired precision as proceeding with the calculation would not add anything significant to the result.

Unfortunately, Solidity does not support fractions natively, so the real code will look something like this:

for (delta = ONE;
     gte (delta, precision);
     delta = div (delta, TWO)) {
  if (gte (x, TWO)) {
    result = add (resukt, delta);
    x = div (x, TWO);
  }
  x = mul (x, x);
}

where ONE, TWO, add, mul, div, and gte are constants and functions emulating some sort of fractional numbers and arithmetic on them for Solidity.

Fortunately, ABDK Libraries has ready to use binary logarithm implementations for 64.64-bit binary fixed-point quadruple-precision binary floating-point numbers.

Now, when we know how to calculate binary logarithm,

What About Natural and Common Logarithms?

Spoiler: magic factors.

In order to calculate natural (base e) and common (base 10) logarithms, we may use the following rule:

thus,

Here

are magic factors that could be hardcoded into the implementation and don’t need to be calculated at run time.

Now, when we done with logarithm, lets switch to

Exponent

Again, let’s start with base 2 exponentiation, i.e. calculating

Solidity has ** operator for power, so the obvious solution would be:

y = 2**x

However, this works only for those values of x, that are both, integer and non-negative. Also, this was is not the most efficient one, as using shift operation would be somewhat cheaper:

y = 1 << x

The shift may also help with negative values of x:

y = x >= 0 ? 1 << x : 1 >> -x

As Solidity does not support fractions natively, any negative x will lead to zero result, which does not make much sense. However, if we would replace integer 1 here with fixed-point representation of 1, this code would become more reasonable.

It’s even simpler for binary floating-point numbers, as in the formula above y is a binary floating-point number with mantissa equal to 1 and exponent equal to x.

So far so good, but

What If x is Fractional?

Spoiler: multiply magic factors.

Let’s split a fractional value of x into the integer part n and the fractional part f:

then

Let f be a binary fraction:

then

Note, that:

The magic factors,

could be precomputed and don’t need to be calculated at run time:

This is fine, but

How Many Magic Factors Should We Precompute?

Spoiler: as many as desired bits of precision.

For binary fixed-point numbers the answer is obvious, as the number of binary digits after the dot is fixed. So. if fixed point has 64 bits in fractional part, then we need 64 magic factors.

For binary floating-point numbers things are a bit more complicated, as mantissa m could be shifted far right by the large negative exponent e. So, the binary representation of such floating-point number would look like this:

Fortunately, for any f between 0 and 1, it is true that

so if f is the number whose binary representation was shown above, then

Thus, if desired result precision is M bits, then we may just ignore those bits of the binary representation of f, that are located further than M binary places after the dot. This way we would need at most precomputed M magic factors to calculate the exponent.

Ready to use implementations of base 2 exponential functions for binary fixed- and floating-point numbers could be found in ABDK Libraries source code.

Base 2 exponential is good, but

What About Exponential with Arbitrary Base?

Spoiler: use logarithm.

We know, that for arbitrary positive x and arbintrary positive b other than one the following is true:

So, for arbitrary y:

For b=2 this gives us:

As we already know how to calculate base-2 logarithm and exponential functions, we may calculate exponential functions with arbitrary base.

This formula could be used to effectively calculate comtimuous compound interest:

Here r is the interest rate for a single time unit and t is the length of a time interval to calculate compound interest for. Note that in case of a fixed interest rate, the value

could be calculated only once, probably off-chain, and then reused, which would make this formula even more efficient.

Conclusion

In this article we showed how base-2 logarithm and exponential functions could be efficiently calculated in Solidity for binary fixed- and floating-point numbers.

We also described, how arbitrary based logarithm and exponential functions could be implemented via base-2 functions.

We presented real use case of continuous compound interest calculation efficiently implemented using logarithm and exponential functions.

The our next article we will show more use cases for logarithm and exponent in DeFi applications, the ne next topic will be: Bancor formula.

Math in Solidity (Part 5: Exponent and Logarithm)

This article is the fifth one in a series of articles about doing math in Solidity. This time the topic is: exponent and logarithm.

Introduction

Logarithm

How to Calculate The Integer Part of Binary Logarithm in Solidity?

What If X Is Fractional?

What About The Fractional Part of A Binary Logarithm?

What About Natural and Common Logarithms?

Exponent

What If x is Fractional?

How Many Magic Factors Should We Precompute?

What About Exponential with Arbitrary Base?

Conclusion

Also, Read

Written by Mikhail Vladimirov