C# Reciprocal: One Divided by Number

Reciprocal. Division is slow.

A reciprocal of a number is one divided by that number. How can we optimize computing reciprocals for real numbers? I investigate a lookup table, with switch, for this purpose, and benchmark it.

For the multiplicative inverse of a real number, divide 1 by the number. For example, the reciprocal of 5 is one fifth.

Multiplicative Inverse: Wikipedia

Example. To begin, this example introduces two methods. The Invert method does the division with the variable argument. The InvertConst method first switches on the number argument. It then returns a constant division expression.

Tip: The C# compiler is able to optimize constant divisions. It can precompute them. It cannot do this with variables.

C# program that optimizes invert

using System;
using System.Diagnostics;

class Program
{
    static double Invert(int number)
    {
	return 1 / (double)number;
    }

    static double InvertConst(int number)
    {
	switch (number)
	{
	    case 1:
		return 1 / 1d;
	    case 2:
		return 1 / 2d;
	    case 3:
		return 1 / 3d;
	    case 4:
		return 1 / 4d;
	    case 5:
		return 1 / 5d;
	    case 6:
		return 1 / 6d;
	    case 7:
		return 1 / 7d;
	    case 8:
		return 1 / 8d;
	    case 9:
		return 1 / 9d;
	    case 10:
		return 1 / 10d;
	    case 11:
		return 1 / 11d;
	    case 12:
		return 1 / 12d;
	    case 13:
		return 1 / 13d;
	    case 14:
		return 1 / 14d;
	    case 15:
		return 1 / 15d;
	    case 16:
		return 1 / 16d;
	    case 17:
		return 1 / 17d;
	    case 18:
		return 1 / 18d;
	    case 19:
		return 1 / 19d;
	    case 20:
		return 1 / 20d;
	}
	// ... Fallback.
	return 1 / number;
    }

    const int _max = 100000000;
    static void Main()
    {
	int one = int.Parse("13");

	var s1 = Stopwatch.StartNew();
	for (int i = 0; i < _max; i++)
	{
	    double v = Invert(one);
	    v = Invert(one);
	    v = Invert(one);
	    v = Invert(one);
	    v = Invert(one);
	    if (v == 0)
	    {
		throw new Exception();
	    }
	}
	s1.Stop();
	var s2 = Stopwatch.StartNew();
	for (int i = 0; i < _max; i++)
	{
	    double v = InvertConst(one);
	    v = InvertConst(one);
	    v = InvertConst(one);
	    v = InvertConst(one);
	    v = InvertConst(one);
	    if (v == 0)
	    {
		throw new Exception();
	    }
	}
	s2.Stop();
	Console.WriteLine(((double)(s1.Elapsed.TotalMilliseconds * 1000000) /
	    _max).ToString("0.00 ns"));
	Console.WriteLine(((double)(s2.Elapsed.TotalMilliseconds * 1000000) /
	    _max).ToString("0.00 ns"));
	Console.Read();
    }
}

Output

32.60 ns [Invert]
17.53 ns [InvertConst]

We find that the InvertConst method is nearly twice as fast as the actual division method. A lookup table optimizes the reciprocal function. In my testing, it was faster for all values that were matched in the lookup.

However: Values not included in the switch, such as 21, will be slightly slower. The lookup may need tuning for a specific program.

Summary. Using a lookup table can make many mathematical operations faster. Division, in particular, tends to be slower than other operations. A switch statement is faster to evaluate. We exploited the compiler's constant expression analysis.

Related Links