Performance of BigInteger.Pow isn't optimal when exponent is NPOT

[mcraiha]

I am trying to implement VDF (verifiable delay function) with C# and I noticed BigInteger.Pow has quite big performance penalty if exponent is NPOT (Non-Power-Of-Two).

// * Summary *

BenchmarkDotNet=v0.12.0, OS=Windows 10.0.18362
AMD Ryzen 7 1700, 1 CPU, 16 logical and 8 physical cores
.NET Core SDK=3.0.100
[Host] : .NET Core 3.0.0 (CoreCLR 4.700.19.46205, CoreFX 4.700.19.46214), X64 RyuJIT
DefaultJob : .NET Core 3.0.0 (CoreCLR 4.700.19.46205, CoreFX 4.700.19.46214), X64 RyuJIT

Method	Mean	Error	StdDev
PowNice	7.098 s	0.0324 s	0.0303 s
PowSlow	12.942 s	0.0972 s	0.0909 s

and code I used for testing

using System;
using System.Numerics;
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;

namespace benchmark
{
	public class BigIntegerPow
	{
		public BigIntegerPow()
		{
			
		}

		[Benchmark]
		public BigInteger PowNice() => BigInteger.Pow(13, 1 << 23);

		[Benchmark]
		public BigInteger PowSlow() => BigInteger.Pow(13, (1 << 23) - 1);
	}

	class Program
	{
		static void Main(string[] args)
		{
			var summary = BenchmarkRunner.Run<BigIntegerPow>();
		}
	}
}

[tannergooding]

Powers of two are faster because it is mostly just repeated squaring of the existing value and a multiplication at the end, where-as non-powers of two requires repeated multiplication (which is more expensive).

[dotnet-policy-service]

Due to lack of recent activity, this issue has been marked as a candidate for backlog cleanup. It will be closed if no further activity occurs within 14 more days. Any new comment (by anyone, not necessarily the author) will undo this process.

This process is part of our issue cleanup automation.