Open
Description
Background and motivation
when people need to calculate the Log10 of an integer,
they often use:
(int)Math.Log10((double)value)
[Intrinsic]
[MethodImpl(MethodImplOptions.InternalCall)]
public static extern double Log10(double d);however, for calculating the Log10 of an integer,
don’t actually need to convert it to a double and then back to an integer.
this approach incurs two overheads of converting between double and int.
in fact, can use BitOperations.Log2 and a small lookup table to speed up Log10 calculation for integers.
// https://graphics.stanford.edu/~seander/bithacks.html#IntegerLog10
// Find integer log base 10 of an integer
here is a simple benchmark:
using System.Numerics;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Configs;
namespace TestLog10
{
[ShortRunJob]
[GroupBenchmarksBy(BenchmarkLogicalGroupRule.ByCategory)]
[CategoriesColumn]
public class BenchmarkLog10
{
[Params(1000, 10000, 100000)] public int Count { get; set; }
public List<uint> Input;
public int Value1;
public int Value2;
[GlobalSetup]
public void Init()
{
Input = new List<uint>(Count);
for (int i = 0; i < Count; i++)
{
Input.Add((uint)Random.Shared.Next());
}
}
// https://graphics.stanford.edu/~seander/bithacks.html#IntegerLog10
// Find integer log base 10 of an integer
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int Log10(uint value)
{
value |= 1;
int num1 = BitOperations.Log2(value) + 1;
int num2 = (num1 * 0x4D1) >> 0xC;
return value < Unsafe.Add(ref MemoryMarshal.GetReference(PowersOf10), num2) ? num2 - 1 : num2;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int Log10(ulong value)
{
value |= 1;
int num1 = BitOperations.Log2(value) + 1;
int num2 = (num1 * 0x4D1) >> 0xC;
return value < Unsafe.Add(ref MemoryMarshal.GetReference(PowersOf10), num2) ? num2 - 1 : num2;
}
private static ReadOnlySpan<ulong> PowersOf10 => new ulong[]
{
0x1, 0xA, 0x64, 0x3E8, 0x2710, 0x186A0, 0xF4240, 0x989680, 0x5F5E100, 0x3B9ACA00, 0x2540BE400, 0x174876E800,
0xE8D4A51000, 0x9184E72A000, 0x5AF3107A4000, 0x38D7EA4C68000, 0x2386F26FC10000, 0x16345785D8A0000,
0xDE0B6B3A7640000, 0x8AC7230489E80000
};
[BenchmarkCategory("Log10")]
[Benchmark]
public void Log10ByBitOperations()
{
foreach (uint i in Input)
{
Value1 ^= Log10(i);
}
}
[BenchmarkCategory("Log10")]
[Benchmark]
public void Log10ByMath()
{
foreach (uint i in Input)
{
Value2 ^= (int)Math.Log10((double)i);
}
}
}
}result:
| Method | Count | Mean | Error | StdDev |
|--------------------- |------- |-----------:|-----------:|----------:|
| Log10ByBitOperations | 1000 | 1.237 us | 0.1159 us | 0.0064 us |
| Log10ByMath | 1000 | 7.003 us | 1.5248 us | 0.0836 us |
| Log10ByBitOperations | 10000 | 12.155 us | 0.6631 us | 0.0363 us |
| Log10ByMath | 10000 | 70.714 us | 5.7563 us | 0.3155 us |
| Log10ByBitOperations | 100000 | 326.526 us | 61.5916 us | 3.3760 us |
| Log10ByMath | 100000 | 710.025 us | 66.2781 us | 3.6329 us |
API Proposal
namespace System.Numerics;
public static class BitOperations
{
public int Log10(uint value);
public int Log10(ulong value);
}
public interface IBinaryInteger<TSelf>
{
static abstract TSelf Log10(TSelf value);
}API Usage
int value = XX;
int log10 = BitOperations.Log10(value);Alternative Designs
No response
Risks
No response