CODEWITHSUNDEEP
c#algorithmoptimizationbiginteger
Daniel
Daniel

Reputation: 7714

Fastest way to get the first 5 digits of a BigInteger

Suppose n is a BigInteger and I want its first 5 digits. I'm thinking in 2 ways:

  1. Dividing n by 10 log10(n)-5 times (so only the first 5 digits would remain).
  2. Get the Substring(0, 5) of n's string.

I have no idea which one is faster or if there is another option that may be better than these.

I would like to hear considerations about it before I test these options (what do you think of them, if there is something better, etc.).

Upvotes: 2

Views: 582

Answers (1)

Dmitrii Bychenko
Dmitrii Bychenko

Reputation: 186803

If we want to find out first 5 leading digits, we can exploit integer division:

   123     / 1   == 123
   12345   / 1   == 12345
   1234567 / 100 == 12345

Naive approach is to divide original value by 10 while it is bigger or equal 1_000_000:

   1234567 => 123456 => 12345

However, division is expensive especially if we have a huge number (if we have a number with ~1000000 digits we have to divide this number ~1000000 times). To create a faster solution we can compute an appropriate power of 10 (power computation is fast) and then divide just once:

  1234567 / Pow(10, Log10(1234567) - 5 + 1)

So the raw idea is

  result = source / BigInteger.Pow(10, (int)BigInteger.Log10(source) - 4);

There are two difficulties here:

  1. Negative numbers (we should take absolute value of source at least when we computing logarithms)
  2. Rounding errors for huge source (what if we have rounding up and have just 4 digits?)

To cope with both problems I compute Log10 myself as Log10(2) * Log2(source):

  value.GetBitLength() * 0.30102999566398

this guarantees that I have at least 5 digits but may be 6 in case of rounding errors (note 0.30102999566398 < Log10(2)).

Combining all together:

private static int FirstDigits(BigInteger value) {
  if (value.IsZero)
    return 0; 

  int digits = 5;

  int result = (int)(value / 
    BigInteger.Pow(10, (int)(value.GetBitLength() * 0.30102999566398 - digits + 1)));

  while (result >= 1_000_000 || result <= -1_000_000)
    result /= 10;  

  return result;   
}

Upvotes: 4

Related Questions