BigInteger 的最后 n 位数字-解网

问：

我正在寻找快速获取数字的最后 n 位数字的方法，表示为 BigInteger，比如说 m。

计算 m mod（10^n）（或转换为字符串）似乎太昂贵了，因为 n 的大小非常大。有没有更快的方法？

C# biginteger

如果它真的是关于一个常量（或者无论如何是可预测的数字，你可以准备）的单个模块化缩减，你可以实现 Barrett 缩减（它实际上在 .NET 中，即，但不能直接访问它）。这是否真的有意义，或者其他东西更有意义，再次取决于你还没有真正给出的细节。BigIntegerCalculator.FastReducer

答：

3赞 Matthew Watson 6/27/2023 #1

你能用或吗？BigInteger.DivRem()BigInteger.Remainder()

例如，要获取最后 4 位数字，“DivRem”乘以 10000：

BigInteger b1 = new BigInteger(123456789);
BigInteger b2 = new BigInteger(10000);

BigInteger.DivRem(b1, b2, out var b3);

Console.WriteLine(b3); // Prints "6789"

或者要获取更大数字的最后 20 位数字：

BigInteger b1 = BigInteger.Parse("1234567890123456789012345678901234567890");
BigInteger b2 = BigInteger.Pow(10, 20);

var b3 = BigInteger.Remainder(b1, b2);

Console.WriteLine(b3); // Prints "12345678901234567890"

不确定这是否比使用更快.......ModPow()

附录：我确实尝试过一个基准测试：

[MemoryDiagnoser]
public class Benchmarks
{
    [Benchmark]
    public void DivRem()
    {
        BigInteger.DivRem(b1, b2, out _);
    }

    [Benchmark]
    public void Remainder()
    {
        BigInteger.Remainder(b1, b2);
    }

    [Benchmark]
    public void ModPow()
    {
        BigInteger.ModPow(b1, 1, b2);
    }

    static readonly BigInteger b1 = BigInteger.Parse("12345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890");
    static readonly BigInteger b2 = BigInteger.Pow(10, 100);
}

有了这些结果：

|    Method |      Mean |    Error |   StdDev |   Gen0 | Allocated |
|---------- |----------:|---------:|---------:|-------:|----------:|
|    DivRem |  96.11 ns | 0.968 ns | 0.905 ns | 0.0076 |     120 B |
| Remainder |  86.89 ns | 0.476 ns | 0.445 ns | 0.0045 |      72 B |
|    ModPow | 167.48 ns | 0.726 ns | 0.679 ns | 0.0045 |      72 B |

因此，看起来速度几乎是基准测试中数字的两倍。当然，您应该尝试使用您实际使用的数字类型，因为结果可能会有所不同！DivRem()Remainder()

上一个：这些是 Java 长整数还是 BigInteger 格式数字？IP2Location csv 数据库

下一个：如何使用基类的映射方法进行派生类？

BigInteger 的最后 n 位数字

Last n digits of BigInteger

评论