英文:
Last n digits of BigInteger
问题
我正在寻找一种快速获取以BigInteger表示的数字m的最后n位数字的方法。计算m mod(10^n)（或转换为字符串）似乎太昂贵，因为n的大小相当大。有更快的方法吗？
英文:
I'm looking for fast way to get n last digits of number, represented as BigInteger, lets say, m.
Calculating m mod(10^n) (or converting to string) seems too expensive, because the sizes of n are pretty big. Is there faster way ?
答案1
得分: 3
你可以使用 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); // 输出 "6789"
或者要获取一个更大的数字的最后20位数字：
BigInteger b1 = BigInteger.Parse("1234567890123456789012345678901234567890");
BigInteger b2 = BigInteger.Pow(10, 20);
var b3 = BigInteger.Remainder(b1, b2);
Console.WriteLine(b3); // 输出 "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);
}
以下是测试结果：
| 方法 | 平均时间 (ns) | 误差 (ns) | 标准差 (ns) | Gen0 | 分配内存 (B) |
|---------- |-----------------:|------------:|------------:|-------:|-------------:|
| 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() 似乎快了近两倍。当然，你应该尝试在实际使用的数字上测试，因为结果可能会有所不同！
英文:
Can you use BigInteger.DivRem() or BigInteger.Remainder()?
For example, to get the last 4 digits, "DivRem" by 10000:
BigInteger b1 = new BigInteger(123456789);
BigInteger b2 = new BigInteger(10000);
BigInteger.DivRem(b1, b2, out var b3);
Console.WriteLine(b3); // Prints "6789"
Or to get the last 20 digits of a much bigger number:
BigInteger b1 = BigInteger.Parse("1234567890123456789012345678901234567890");
BigInteger b2 = BigInteger.Pow(10, 20);
var b3 = BigInteger.Remainder(b1, b2);
Console.WriteLine(b3); // Prints "12345678901234567890"
Not sure if this is any faster than using .ModPow() though...
Addendum: I did try a benchmark:
[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);
}
With these results:
| 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 |
So it appears that DivRem() and Remainder() is almost twice as fast, at least for the numbers in the benchmark. Of course, you should try it with the sort of numbers you're actually using because the results may differ!
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论