快速了解BigInteger对象的大小?

问题描述 投票:3回答:3

我有一个积极的C#BigInteger。它可能很大。我想对它的大小做一个非常粗略的估算。如果我的估计错了(说)千分之一,那很好。

我已经尝试过以下方法。全部都很慢(在3 ^ 1000000上大约有80k滴答声)

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

编辑:“大小”是指“数值”,而不是“内存大小”。

c# biginteger
3个回答
1
投票

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

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


5
投票

首先优化是这里避免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的funny comment没错,除非您要处理大量数字,并且+/- 1000X(!!!)估计就足够了,那么您可以使用16字节的恒定大小(或32或64 ...)应该足以容纳一个非常大的整数(另请参见Arbitrarily large integers in C#)...



0
投票

首先,让我们仅考虑正BigInteger,因为负数需要一些附加条件才能正确计算(或可以取反并调用这些方法)。同样对于负值,根据上下文,可以将符号位视为额外位,也可以不考虑符号位...

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

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

不幸的是,这不是很有效,但肯定会击败幼稚的方法。

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的倍数进行搜索。

© www.soinside.com 2019 - 2024. All rights reserved.