Fast Integer Log10

Mathematical function log10can be quite time consuming. If it is not available, for some languages such as VBScript, you have to compute it base on the fact.

and therefore, we can compute log10 base on natural log.

and since can only be computed once and stored for next computation, we can replace it with the constant. Since multiplication is faster than division in most cases, we can replace the whole division thing with the constant 0.4342944819.

Sometimes, we just want the integer part of the log10, so we can use a faster function base on the fact that it is only 10 possible integer values for unsigned 32-bit integers. The maximum value that can be represented by unsigned 32-bit integers (e.g. uint in C#, LongWord in Delphi) is 4294967295, the log10 value of which is 9. i.e. 4294967295 is larger than but less than .

So instead of computing directly the log10 value, we can easily check which range the given number falls into.

1
2
3
4
5
6
7

static uint log10(uint v)
{
    return (v >= 1000000000u) ? 9 : (v >= 100000000u) ? 8 : 
        (v >= 10000000u) ? 7 : (v >= 1000000u) ? 6 : 
        (v >= 100000u) ? 5 : (v >= 10000u) ? 4 :
        (v >= 1000u) ? 3 : (v >= 100u) ? 2 : (v >= 10u) ? 1u : 0u; 
}

static uint log10(uint v)
{
    return (v >= 1000000000u) ? 9 : (v >= 100000000u) ? 8 : 
        (v >= 10000000u) ? 7 : (v >= 1000000u) ? 6 : 
        (v >= 100000u) ? 5 : (v >= 10000u) ? 4 :
        (v >= 1000u) ? 3 : (v >= 100u) ? 2 : (v >= 10u) ? 1u : 0u; 
}

As shown in above C# code, the function log10 takes the unsigned 32-bit integer v and quickly checks which range it falls into, from a larger set of numbers to a smaller one. So if the input is uniform equally distributed, it will return values for the first few (e.g. 3) checks. i.e. The return value is zero when the input is less than 10 (10 possible inputs); the return value is one when the input is less than 100 (90 possible inputs) and so on. So we should check the largest group set first.

How does this perform? We time the performance in the C# .NET environment.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

using System;
using System.Diagnostics;
 
namespace ConsoleApplication2
{
    class Program
    {
        static uint log10(uint v)
        {
            return (v >= 1000000000u) ? 9 : (v >= 100000000u) ? 8 : 
                (v >= 10000000u) ? 7 : (v >= 1000000u) ? 6 : 
                (v >= 100000u) ? 5 : (v >= 10000u) ? 4 :
                (v >= 1000u) ? 3 : (v >= 100u) ? 2 : (v >= 10u) ? 1u : 0u; 
        }
 
        static void Main(string[] args)
        {
            Stopwatch w = new Stopwatch();
            w.Start();
            for (uint i = 0; i <= 200000000; i++)
            {
                uint x = log10(i);
            }
            w.Stop();
            Console.WriteLine(w.ElapsedMilliseconds);
 
            w.Restart();
            for (uint i = 0; i <= 200000000; i++)
            {
                uint y = (uint)Math.Log10(i);
            }
            w.Stop();
            Console.WriteLine(w.ElapsedMilliseconds);
            Console.ReadLine();
        }
    }
}

using System;
using System.Diagnostics;

namespace ConsoleApplication2
{
    class Program
    {
        static uint log10(uint v)
        {
            return (v >= 1000000000u) ? 9 : (v >= 100000000u) ? 8 : 
                (v >= 10000000u) ? 7 : (v >= 1000000u) ? 6 : 
                (v >= 100000u) ? 5 : (v >= 10000u) ? 4 :
                (v >= 1000u) ? 3 : (v >= 100u) ? 2 : (v >= 10u) ? 1u : 0u; 
        }

        static void Main(string[] args)
        {
            Stopwatch w = new Stopwatch();
            w.Start();
            for (uint i = 0; i <= 200000000; i++)
            {
                uint x = log10(i);
            }
            w.Stop();
            Console.WriteLine(w.ElapsedMilliseconds);

            w.Restart();
            for (uint i = 0; i <= 200000000; i++)
            {
                uint y = (uint)Math.Log10(i);
            }
            w.Stop();
            Console.WriteLine(w.ElapsedMilliseconds);
            Console.ReadLine();
        }
    }
}

It is no surprise that the log10 is roughly three times faster. 3507 milliseconds versus 10327 milliseconds (the traditional System.Math.Log10).

References:

1. http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog10Obvious

–EOF (The Ultimate Computing & Technology Blog) —