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

Question

我有一个正 C# BigInteger。它可能非常大。我想粗略地估计一下它有多大。如果我的估计是错误的（比如说）千分之一，那很好。

我尝试了以下方法。一切都很慢（3^1000000 上大约有 80k 个刻度）

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

编辑："size"，我的意思是 "numerical value"，而不是 "memory size."

Answer 1

首先优化这里是为了避免LINQ,ToByteArray()returnsbyte[]然后就可以直接使用Length属性:

int est = myBigInt.ToByteArray().Length;

然而，这仍然不是最佳选择，因为 ToByteArray() 克隆了内部 buffer.For 一个 非常大的 数字，您甚至可能拥有更好的长期性能使用反射读取它：

var bits = typeof(BigInteger).GetField("_bits",
    BindingFlags.Default | BindingFlags.NonPublic);
int size = ((uint[])bits.GetValue(myBigInt)).Length * sizeof(uint);

请注意属性名称及其类型是实现细节，可能会发生变化，添加适当的单元测试...

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

所有这些都说 from Oleksandr Pshenychnyy is not wrong, unless you're working with enormous numbers and a +/-1000X (!!!) estimation is enough then you may use a constant size of 16 bytes (or 32 or 64...) It should be good enough to accommodate a very big integer (see also Arbitrarily large integers in C#)...

Answer 2

从 .NET Core 2.1 开始有 new API: public int GetByteCount (bool isUnsigned = false);

我希望我们也能在下一版本的 .NET Standard 中找到它。

Answer 3

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

有 2 种反射方法，一种是属性，另一种是字段，因此人们提到了大写问题。无论如何，两者都可以轻松完成。这是使用基于 this 的代码的仅反射解决方案，即使不缓存反射 fields/methods:

，它的执行速度也毫无疑问是最快的

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.

如果你不想进入这样一个 hacky 的解决方案，那么这里有一个重复的二进制搜索方法，它通常应该更有效，但理论上它可能需要对 3 位的情况进行额外的比较，其中 1, 2 , 3 比 1, 2, 4, 3 快，尽管稍作优化可能会解决这种情况。此外，它仅适用于以下形式的正 BigIntegers：

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;
}

不幸的是，这不是很有效，但它肯定胜过幼稚的做法。

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;
}

但最快的是反射，其次是获取字节，然后是二分搜索，然后是递归二分搜索，最后朴素方法是最慢的，随着数字越来越大（在 2^ (2^20) 肯定会很明显）。

还有一个特殊的字节优化版本，它以 8 的倍数进行搜索，可以从其中任何一个派生出来。

Answer 4

刚刚运行穿过这个线程..

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

long bitSize = myBigInt.GetBitLength();

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

Quickly get a rough estimate of the size of a BigInteger object?

c#

biginteger