[API Proposal]: BitOperations add Log10(uint/ulong value)

[Molth]

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

public interface IBinaryInteger<TSelf>
{
    static abstract TSelf Log10(TSelf value);
}

Cover BigInteger and the various primitive types that it will be publicly exposed on as part of defining it for IBinaryInteger. In particular, byte, sbyte, short, ushort, int, uint, long, ulong, Int128, UInt128, CLong, and CULong.

It will also end up being exposed as part of the vector APIs: Vector64, Vector128, Vector256 and Vector512 in the System.Runtime.Intrinsics namespace; as well as Vector2, Vector3, Vector4, and Vector in the System.Numerics namespace; and as part of TensorPrimitives and Tensor in the System.Numerics.Tensors namespace

API Usage

        int value = XX;
        int log10 = BitOperations.Log10(value);

Alternative Designs

No response

Risks

No response

[Molth]

@tannergooding Hi, thank you for your feedback! I’ve written up the [API proposal] as you suggested. Could you please take a look? I’d really appreciate it!

[tannergooding]

@Molth sorry for the delay.

It generally looks good/correct. However, you should explicitly cover BigInteger and the various primitive types that it will be publicly exposed on as part of defining it for IBinaryInteger. In particular, byte, sbyte, short, ushort, int, uint, long, ulong, Int128, UInt128, CLong, and CULong.

It will also end up being exposed as part of the vector APIs: Vector64, Vector128, Vector256 and Vector512 in the System.Runtime.Intrinsics namespace; as well as Vector2, Vector3, Vector4, and Vector in the System.Numerics namespace; and as part of TensorPrimitives and Tensor in the System.Numerics.Tensors namespace

[Molth]

@tannergooding
Thank you very much for the detailed feedback!

Regarding the primitive types like byte, sbyte, short, ushort, int, uint, long, ulong, Int128, UInt128, CLong, and CULong, I believe the API should work correctly for all of these. However, for BigInteger, it relies on some internal properties, so I haven’t thoroughly tested whether it will fully support the proposed API yet.

As for the vector APIs, such as those in System.Runtime.Intrinsics and System.Numerics namespaces, I expect the API to be compatible and usable there as well.

using System;
using System.Diagnostics.CodeAnalysis;
using System.Numerics;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;

namespace Log10Test;

// only for test
internal static class ThrowHelper
{
    [DoesNotReturn]
    internal static void ThrowValueArgumentOutOfRange_NeedNonNegNumException()
    {
        throw new ArgumentOutOfRangeException();
    }
}

public static class TestBitOperations
{
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static int Log10(BigInteger value)
    {
        /*

        if (value._sign < 0 || baseValue == 1.0D)
            return double.NaN;
        if (baseValue == double.PositiveInfinity)
            return value.IsOne ? 0.0D : double.NaN;
        if (baseValue == 0.0D && !value.IsOne)
            return double.NaN;
        if (value._bits == null)
            TODO: return Log10(value._sign)
            return Math.Log(value._sign, baseValue);

        ulong h = value._bits[value._bits.Length - 1];
        ulong m = value._bits.Length > 1 ? value._bits[value._bits.Length - 2] : 0;
        ulong l = value._bits.Length > 2 ? value._bits[value._bits.Length - 3] : 0;

        // Measure the exact bit count
        int c = BitOperations.LeadingZeroCount((uint)h);
        long b = (long)value._bits.Length * 32 - c;

        // Extract most significant bits
        ulong x = (h << 32 + c) | (m << c) | (l >> 32 - c);

        // Let v = value, b = bit count, x = v/2^b-64
        // log ( v/2^b-64 * 2^b-64 ) = log ( x ) + log ( 2^b-64 )
        TODO: return (int)(Log10(x) + (b - 64) / Log2(baseValue));
        return Math.Log(x, baseValue) + (b - 64) / Math.Log(baseValue, 2);

        */

        throw new NotImplementedException();
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static int Log10(byte value) => Log10((uint)value);

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static int Log10(sbyte value)
    {
        if (value < 0)
            ThrowHelper.ThrowValueArgumentOutOfRange_NeedNonNegNumException();

        return Log10((uint)value);
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static int Log10(short value)
    {
        if (value < 0)
            ThrowHelper.ThrowValueArgumentOutOfRange_NeedNonNegNumException();

        return Log10((uint)value);
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static int Log10(ushort value) => Log10((uint)value);

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static int Log10(int value)
    {
        if (value < 0)
            ThrowHelper.ThrowValueArgumentOutOfRange_NeedNonNegNumException();

        return Log10((uint)value);
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static int Log10(uint value)
    {
        value |= 1;
        int num1 = BitOperations.Log2(value) + 1;
        int num2 = (num1 * 1233) >> 12;
        return value < Unsafe.Add(ref MemoryMarshal.GetReference(UIntPowersOf10), num2) ? num2 - 1 : num2;
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static int Log10(long value)
    {
        if (value < 0)
            ThrowHelper.ThrowValueArgumentOutOfRange_NeedNonNegNumException();

        return Log10((ulong)value);
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static int Log10(ulong value)
    {
        value |= 1;
        int num1 = BitOperations.Log2(value) + 1;
        int num2 = (num1 * 1233) >> 12;
        return value < Unsafe.Add(ref MemoryMarshal.GetReference(UInt64PowersOf10), num2) ? num2 - 1 : num2;
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static int Log10(IntPtr value)
    {
        if (value < 0)
            ThrowHelper.ThrowValueArgumentOutOfRange_NeedNonNegNumException();

        if (IntPtr.Size == 8)
            return Log10((ulong)value);

        return Log10((uint)value);
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static int Log10(UIntPtr value)
    {
        if (IntPtr.Size == 8)
            return Log10((ulong)value);

        return Log10((uint)value);
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static int Log10(Int128 value)
    {
        if (value < 0)
            ThrowHelper.ThrowValueArgumentOutOfRange_NeedNonNegNumException();

        return Log10((UInt128)value);
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static int Log10(UInt128 value)
    {
        value |= 1;
        int num1 = (int)UInt128.Log2(value) + 1;
        int num2 = (num1 * 1233) >> 12;
        return value < UInt128PowersOf10[num2] ? num2 - 1 : num2;
    }

    // only for test
    public static int DummyLog10(Int128 value)
    {
        if (value < 0)
            ThrowHelper.ThrowValueArgumentOutOfRange_NeedNonNegNumException();

        return DummyLog10((UInt128)value);
    }

    // only for test
    public static int DummyLog10(UInt128 value)
    {
        if (value == 0)
            return 0;

        if (value >= UInt128PowersOf10[38]) return 38;
        if (value >= UInt128PowersOf10[37]) return 37;
        if (value >= UInt128PowersOf10[36]) return 36;
        if (value >= UInt128PowersOf10[35]) return 35;
        if (value >= UInt128PowersOf10[34]) return 34;
        if (value >= UInt128PowersOf10[33]) return 33;
        if (value >= UInt128PowersOf10[32]) return 32;
        if (value >= UInt128PowersOf10[31]) return 31;
        if (value >= UInt128PowersOf10[30]) return 30;
        if (value >= UInt128PowersOf10[29]) return 29;
        if (value >= UInt128PowersOf10[28]) return 28;
        if (value >= UInt128PowersOf10[27]) return 27;
        if (value >= UInt128PowersOf10[26]) return 26;
        if (value >= UInt128PowersOf10[25]) return 25;
        if (value >= UInt128PowersOf10[24]) return 24;
        if (value >= UInt128PowersOf10[23]) return 23;
        if (value >= UInt128PowersOf10[22]) return 22;
        if (value >= UInt128PowersOf10[21]) return 21;
        if (value >= UInt128PowersOf10[20]) return 20;
        if (value >= UInt128PowersOf10[19]) return 19;
        if (value >= UInt128PowersOf10[18]) return 18;
        if (value >= UInt128PowersOf10[17]) return 17;
        if (value >= UInt128PowersOf10[16]) return 16;
        if (value >= UInt128PowersOf10[15]) return 15;
        if (value >= UInt128PowersOf10[14]) return 14;
        if (value >= UInt128PowersOf10[13]) return 13;
        if (value >= UInt128PowersOf10[12]) return 12;
        if (value >= UInt128PowersOf10[11]) return 11;
        if (value >= UInt128PowersOf10[10]) return 10;
        if (value >= UInt128PowersOf10[9]) return 9;
        if (value >= UInt128PowersOf10[8]) return 8;
        if (value >= UInt128PowersOf10[7]) return 7;
        if (value >= UInt128PowersOf10[6]) return 6;
        if (value >= UInt128PowersOf10[5]) return 5;
        if (value >= UInt128PowersOf10[4]) return 4;
        if (value >= UInt128PowersOf10[3]) return 3;
        if (value >= UInt128PowersOf10[2]) return 2;
        if (value >= UInt128PowersOf10[1]) return 1;

        return 0;
    }

    private static ReadOnlySpan<uint> UIntPowersOf10 => new uint[]
    {
        1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000
    };

    private static ReadOnlySpan<ulong> UInt64PowersOf10 => new ulong[]
    {
        1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000, 10000000000, 100000000000,
        1000000000000, 10000000000000, 100000000000000, 1000000000000000, 10000000000000000, 100000000000000000,
        1000000000000000000, 10000000000000000000
    };

    private static ReadOnlySpan<UInt128> UInt128PowersOf10 => new UInt128[]
    {
        new UInt128(0, 1UL),
        new UInt128(0, 10UL),
        new UInt128(0, 100UL),
        new UInt128(0, 1_000UL),
        new UInt128(0, 10_000UL),
        new UInt128(0, 100_000UL),
        new UInt128(0, 1_000_000UL),
        new UInt128(0, 10_000_000UL),
        new UInt128(0, 100_000_000UL),
        new UInt128(0, 1_000_000_000UL),
        new UInt128(0, 10_000_000_000UL),
        new UInt128(0, 100_000_000_000UL),
        new UInt128(0, 1_000_000_000_000UL),
        new UInt128(0, 10_000_000_000_000UL),
        new UInt128(0, 100_000_000_000_000UL),
        new UInt128(0, 1_000_000_000_000_000UL),
        new UInt128(0, 10_000_000_000_000_000UL),
        new UInt128(0, 100_000_000_000_000_000UL),
        new UInt128(0, 1_000_000_000_000_000_000UL),
        new UInt128(0, 10_000_000_000_000_000_000UL),
        new UInt128(5, 7766279631452241920UL),
        new UInt128(54, 3875820019684212736UL),
        new UInt128(542, 1864712049423024128UL),
        new UInt128(5421, 200376420520689664UL),
        new UInt128(54210, 2003764205206896640UL),
        new UInt128(542101, 1590897978359414784UL),
        new UInt128(5421010, 15908979783594147840UL),
        new UInt128(54210108, 11515845246265065472UL),
        new UInt128(542101086, 4477988020393345024UL),
        new UInt128(5421010862, 7886392056514347008UL),
        new UInt128(54210108624, 5076944270305263616UL),
        new UInt128(542101086242, 13875954555633532928UL),
        new UInt128(5421010862427, 9632337040368467968UL),
        new UInt128(54210108624275, 4089650035136921600UL),
        new UInt128(542101086242752, 4003012203950112768UL),
        new UInt128(5421010862427522, 3136633892082024448UL),
        new UInt128(54210108624275221, 12919594847110692864UL),
        new UInt128(542101086242752217, 6873995514006732800UL),
        new UInt128(5421010862427522170, 6873995514006732800UL),
    };
}

[tannergooding]

Sorry, I meant the proposal just needs to be updated to list these types and that the API will be publicly exposed on them.

[Molth]

@tannergooding Thank you, I’ve updated the proposal.