1

I am currently using the following method to get a magnitude estimate of a BigInteger. I would be interested to know if anyone can suggest a method which does not required use of BigInteger.ToByteArray();

 public static long MagnitudeEstimate(BigInteger value)
 {

     byte[] array = value.ToByteArray();

     if (array.Length == 0 || (array.Length == 1 && (array[0] == 0 || array[0] == 1)))
         return 0;
     else
         return (long)(array.Length * 2.408239965);
 }
2
  • When posting code, use the {} code button - you'd marked yours up as a quote, which made the formatting odd for the first and last lines Oct 12, 2012 at 9:10
  • 2
    Also, are you not just asking for the Log of some kind? Oct 12, 2012 at 9:11

4 Answers 4

1

Casting to double and taking the logarithm seems like one simple way to do it.

Math.Log10((double)bigInt)

or simply the built in

BigInteger.Log10(bigInt)

I haven't benchmarked it, so I don't know how fast it is.

1
  • Many thanks for the suggestion but unfortunately I'd already considered Logarithm approaches (apologies for not mentioning in the OP). I've just done the comparison again and my current approach is twice as fast as BigInteger.Log10. Unfortunately I can't cast to double before as my values are order > 10000.
    – MarcF
    Oct 12, 2012 at 9:23
1

A hackish solution. I wouldn't use this.

BigInteger bi = new BigInteger(long.MaxValue);

var fieldInfo = typeof(BigInteger).GetField("_bits", BindingFlags.Instance | BindingFlags.NonPublic);

var arr = (uint[])fieldInfo.GetValue(bi);
var size =  arr.Length * sizeof(uint);
0

Combining both my original version and that from L.B I've settled on the following. Although it is no faster than my original version it is more accurate.

Many thanks for everyone's input.

public static long MagnitudeEstimate(BigInteger value)
{
      var fieldInfo = typeof(BigInteger).GetField("_bits", BindingFlags.Instance | BindingFlags.NonPublic);
      var arr = (uint[])fieldInfo.GetValue(value);
      if (arr != null)
      {
            int totalNumBytes = arr.Length * sizeof(uint);
            int zeroBytes = 0;
            for (int i = arr.Length - 1; i >= 0; i--)
            {
                  if (arr[i] == 0)
                  {
                        zeroBytes += 4;
                        continue;
                  }
                  else if (arr[i] <= 0xFF)
                        zeroBytes += 3;
                  else if (arr[i] <= 0xFFFF)
                        zeroBytes += 2;
                  else if (arr[i] <= 0xFFFFFF)
                        zeroBytes += 1;

                  break;
            }

            return (long)((totalNumBytes - zeroBytes) * 2.408239965);
      }
      else return 0;
}
0

Starting from .NET Core 2.1 there's a new API: public int GetByteCount (bool isUnsigned = false);

It will won't copy anything and can be used as a very precise estimate of your number.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.