快速获得BigInteger对象大小的粗略估计

本文关键字：BigInteger 对象 | 更新日期: 2023-09-27 18:12:50

我有一个正的c# BigInteger。它可能非常大。我想粗略估计一下它有多大。如果我的估计错了(比如)千分之一，那也没关系。

我试过以下方法。它们都很慢(在3^1000000上大约80k)

 int est1 = myBigInt.ToByteArray().Count();
 double est2 = BigInteger.Log10(myBigInt);
 double est3 = BigInteger.Log(myBigInt);

编辑:这里的"大小"是指"数值"，而不是"内存大小"。

快速获得BigInteger对象大小的粗略估计

首先优化是为了避免这里的LINQ, ToByteArray()返回byte[]，那么你可以直接使用Length属性:

int est = myBigInt.ToByteArray().Length;
然而，这仍然是次优的，因为ToByteArray()克隆内部缓冲区。对于非常大的数字，使用反射读取它甚至可以获得更好的长期性能: 
var bits = typeof(BigInteger).GetField("_bits",
    BindingFlags.Default | BindingFlags.NonPublic);
int size = ((uint[])bits.GetValue(myBigInt)).Length * sizeof(uint);

请注意，属性名和它的类型是实现细节，然后可能会更改，添加适当的单元测试…

还要注意ToByteArray().Length和内部缓冲区可能不同(因为内部缓冲区是sizeof(uint)字节的倍数，最后一个数组项可能为空，参见内部Length()方法实现)

所有这些都说来自Oleksandr Pshenychnyy的有趣的评论没有错，除非你处理的是巨大的数字，并且+/-1000X(!!)估计就足够了，那么你可以使用16字节的常量(或32或64…)它应该足以容纳一个非常大的整数(参见c#中的任意大整数)…

从。net Core 2.1开始，有一个新的API: public int GetByteCount (bool isUnsigned = false);

我希望我们也能在。net标准的下一个版本中找到它。

刚刚看到这个线程。

从。net 5开始，我们现在有了BigInteger.GetBitLength()。

long bitSize = myBigInt.GetBitLength();

首先，让我们只考虑正的BigInteger，因为负数需要一些额外的条件才能正确计算(或者可以取反并调用这些方法)。同样对于负值，根据上下文，符号位可以被认为是额外的位或不是。

有两个反射方法，一个是属性，另一个是字段，因此人们提到的大写问题。无论如何，两者都很容易做到。以下是使用基于此的代码的唯一反射解决方案，毫无疑问，即使没有缓存反射字段/方法，它也执行得最快:

static int GetBitSizeReflection(BigInteger num)
{
  //uint[] bits = (uint[])typeof(BigInteger).GetField("_bits", System.Reflection.BindingFlags.Instance | System.Reflection.BindingFlags.NonPublic).GetValue(num);
  uint[] bits = (uint[])typeof(BigInteger).GetProperty("_Bits", System.Reflection.BindingFlags.Instance | System.Reflection.BindingFlags.NonPublic).GetValue(num);
  if (bits == null) {
    //int sign = (int)typeof(BigInteger).GetField("_sign", System.Reflection.BindingFlags.Instance | System.Reflection.BindingFlags.NonPublic).GetValue(num);
    int sign = (int)typeof(BigInteger).GetProperty("_Sign", System.Reflection.BindingFlags.Instance | System.Reflection.BindingFlags.NonPublic).GetValue(num);
    bits = new uint[] { (uint)(sign < 0 ? sign & int.MaxValue : sign) };
  }
  int uintLength = (int)typeof(BigInteger).GetMethod("Length", System.Reflection.BindingFlags.Static | System.Reflection.BindingFlags.NonPublic).Invoke(num, new object[] { bits });
  int topbits = (int)typeof(BigInteger).GetMethod("BitLengthOfUInt", System.Reflection.BindingFlags.Static | System.Reflection.BindingFlags.NonPublic).Invoke(num, new object[] { bits[uintLength - 1] });
  return (uintLength - 1) * sizeof(uint) * 8 + topbits;

对于GetByteSize例程-只需使用GetBitSize / 8。

如果你不想进入这样一个黑客的解决方案，那么这里有一个重复的二进制搜索方法，通常应该更有效，但在理论上它可能需要额外的比较，如3位的情况下，1,2,3比1,2,4,3快，虽然一个轻微的优化可能会解决这种情况。此外，它只适用于以下形式的正biginteger:

static int GetBitSizeRecurseBinSearch(BigInteger num)
{ //instead of 0, 1, 2, 3, 4... use 0, 1, 3, 7, 15, etc
  int s = 0, t = 1, oldt = 1;
  if (t <= 0) return 0;
  while (true) {
    if ((BigInteger.One << (s + t)) <= num) { oldt = t; t <<= 1; }
    else if (t == 1) break;
    else { s += oldt; t = 1; }
  }
  return s + 1;
}

不幸的是，这不是很有效，但它肯定比naïve的方法要好。

static int GetBitSizeSlow(BigInteger num)
{
  int s = 0;
  while ((BigInteger.One << s) <= num) s++;
  return s;
}

另一方面，如果你想在框架内保持快速，还有一个版本只需要一些额外的字节复制，并且是仅次于反射的最快版本:

static int GetBitSize(BigInteger num)
{
  byte[] bytes = num.ToByteArray();
  int size = bytes.Length;
  if (size == 0) return 0;
  int v = bytes[size - 1]; // 8-bit value to find the log2 of 
  if (v == 0) return (size - 1) * 8;
  int r; // result of log2(v) will go here
  int shift;
  r = (v > 0xF) ? 4 : 0; v >>= r;
  shift = (v > 0x3) ? 2 : 0; v >>= shift; r |= shift;
  r |= (v >> 1);
  return (size - 1) * 8 + r + 1;
}

最后，如果你真的喜欢二进制搜索，首先你必须在二进制搜索之前对一个高值进行二进制搜索:

static int GetBitSizeHiSearch(BigInteger num) //power of 2 search high, then binary search
{
  if (num.IsZero) return 0;
  int lo = 0, hi = 1;
  while ((BigInteger.One << hi) <= num) { lo = hi; hi <<= 1; }
  return GetBitSizeBinSearch(num, lo, hi);
}
static int GetBitSizeBinSearch(BigInteger num, int lo, int hi)
{
  int mid = (hi + lo) >> 1;
  while (lo <= hi) {
    if ((BigInteger.One << mid) <= num) lo = mid + 1;
    else hi = mid - 1;
    mid = (hi + lo) >> 1;
  }
  return mid + 1;
}

但是最快的是反射，其次是获得字节，其次是二进制搜索，然后是递归二进制搜索，最后naïve方法是最慢的，可以通过分析来确认，因为数字越来越大(在2^(2^20)，这肯定是显而易见的)。

还有一个特殊的字节优化版本，它可以以8的倍数进行搜索。

相关文章：