How to improve speed for couting a BigInteger to 2^256

Question

this small console application count a BigInteger and give me a feedback which exponent it hits.

Now I'm curious for some speed improvments. What can I do?

Thx for your suggestions!

using System;
using System.Collections.Generic;
using System.Numerics;

namespace Counter
{
    internal class Program
    {
        private static readonly Dictionary<BigInteger, int> Dic = new Dictionary<BigInteger, int>();

        private static void Main(string[] args)
        {
            Console.WriteLine("Start with counting ... from 1 to 2^256.");
            Console.WriteLine();

            CreateDict();

            var bigInteger = new BigInteger();

            Console.WriteLine("D:HH:mm:ss,ms      - fac.  - Number");
            Console.WriteLine("---------------------------------------------------");

            var startTime = DateTime.UtcNow;
            while (true)
            {
                bigInteger++;
                if (Dic.ContainsKey(bigInteger))
                {
                    Console.WriteLine("{0:G} - 2^{1,3} = {2:#,0}", (DateTime.UtcNow - startTime), Dic[bigInteger], bigInteger);
                }
            }
        }

        private static void CreateDict()
        {
            for (int i = 1; i <= 256; i++)
            {
                Dic.Add(BigInteger.Pow(2, i), i);
            }
        }
    }
}

output: http://pastebin.com/bMBntFsL

Progress

Working with BigInteger was not so good.

BigInteger 2^26 = 5s

Double 2^26 = 1,3s

Switching from Dict to direct compare was much faster to

            int i = 1;
            double pow = Math.Pow(2, i);
            while (true)
            {
                bigInteger++;
                if (bigInteger == pow)
                {
                    Console.WriteLine("{0:G} - 2^{1,3} = {2:#,0}", (DateTime.UtcNow - startTime), Dic[bigInteger], bigInteger);

                    i++;
                    pow = Math.Pow(2, i);
                }
            }

Dict 2^26 = 1,3s

"<" 2^26 = 0,5s

Not clear what you are asking or trying to achieve here. Why do you count at all? — Daniel Hilgarth, Oct 02 '13 at 13:57
Just playing around with BigInteger and i stock with ideas for speed improvments. Is a Dictionary the best way? If ContainsKey faster than run into a exception by Dic[bigInteger]. — hdev, Oct 02 '13 at 14:06
Dictionary is not the problem at all, why you have to increment bigInteger by 1? — Alessandro D'Andria, Oct 02 '13 at 14:07
The dictionary is fine. Using exceptions instead of `ContainsKey` is way slower, see [here](http://stackoverflow.com/questions/16101795/why-is-it-faster-to-check-if-dictionary-contains-the-key-rather-than-catch-the/16101815#16101815). — Daniel Hilgarth, Oct 02 '13 at 14:07

score 1 · Answer 1 · edited May 23 '17 at 12:06

1

If you really want to count up to 2^256 in a loop, do not use BigInteger.

From MSDN :

The other numeric types in the .NET Framework are also immutable. However, because the BigInteger type has no upper or lower bounds, its values can grow extremely large and have a measurable impact on performance.

Although this process is transparent to the caller, it does incur a performance penalty. In some cases, especially when repeated operations are performed in a loop on very large BigInteger values, that performance penalty can be significant

Since your desired value is big but not incredibly big, you can use a double instead. double value can go up to 1.7 × 10^308, so you're fine with 2^256 (which is 1.15 × 10^77). That should help a lot with the performance of your application.

An other improvement would be to use TryGetValue for your dictionary instead of ContainsKey, as you can see in this answer.

Because you're doing both ContainsKey(bigInteger) and Dic[bigInteger] you're doing the lookup twice.

So the code would become :

while (true)
{
    bigValue++;

    int exponent;
    if (Dic.TryGetValue(bigValue, out exponent))
    {
        Console.WriteLine("{0:G} - 2^{1,3} = {2:#,0}", (DateTime.UtcNow - startTime), exponent, bigValue);
    }
}

edited May 23 '17 at 12:06

Community

1
1

answered Oct 02 '13 at 14:06

Pierre-Luc Pineault

8,993
6
40
55

But the secound lookup is only when I hit an exponent. – hdev Oct 02 '13 at 14:17
1

@user1776231 You're still doing the job twice. And using a nicely named temp variable is cleaner than the Dic[bigInteger] in my opinion. – Pierre-Luc Pineault Oct 02 '13 at 14:21
1

It is true that a `double` can very easily hold the value `Pow(2, 256)` (which is `1.157920892373162E+77`). But it is not true that you can "count" from `0.0` to `Pow(2, 256)` with a `double` by incrementing with `++`. A `double` has a precision of only approximately 16 decimal figures. So if you take for example `d = 1E+18;` and try to increase it with `d++`, you will see that the number doesn't change. There is a "step" of `128` from `1E+18` to the next representable `double` which is `1.000000000000000128E+18`. – Jeppe Stig Nielsen Oct 24 '13 at 20:57
1

Is it just me or does nobody here realize that running a counter from zero to 2^256 is physically impossible? – Thomas Feb 19 '14 at 05:18

How to improve speed for couting a BigInteger to 2^256

1 Answers1