A console app with Biginteger calculation freezes

Question

Issue

A console app with Biginteger calculation freezes

Details

I'm developing a console application in C# which tests whether very big numbers (10 to the power of several tens to hundreds) are prime. Since default integer types can deal with numbers only up to 10^19 (long, ulong), I'm using BitInteger class. But when I run the app in the debug mode in Visual Studio, the app freezes.

    static void Main(string[] args)
    {
        int exp = 100;
        var bi = BigInteger.Pow(10, exp);
        var sw = new Stopwatch();
        sw.Start();
        for (int i = 0; i < 1000; i++)
        {
            bi++;
            Console.WriteLine($"{i}th try : {bi} ({sw.Elapsed.ToString("mm\\:ss\\.ff")})");

            bool b = IsPrime(bi);
            if (b)
            {
                Console.WriteLine($"{bi} is a prime number");
            }

            //GC.Collect();
        }
        sw.Stop();

        Console.Read();
    }

    static private bool IsPrime(BigInteger n)
    {
        if (n <= 1)
            return false;
        else if (n <= 3)
            return true;
        else if (n % 2 == 0 || n % 3 == 0)
            return false;
        for (BigInteger i = 5; i * i <= n; i += 6)
        {
            if (n % i == 0 || n % (i + 2) == 0)
                return false;
        }

        return true;

    }

Whether the program freezes depends on the variable exp. I tested several values of exp.

• (the values of exp) : (i at which the program froze)
• 10 : didn't freeze (the app finished in less than a second
• 15 : didn't freeze (however the console window refreshes only every 2 seconds)
• 17 : didn't freeze (however the console window refreshes only every 17 seconds)
• 20 : 39
• 25 : 13
• 30 : 37
• 50 : 27
• 100 : 37

It's weird that i doesn't monotonically go up as exp increases. So I ran the program for exp = 100 three times but got the same results. The numbers seem to be reproducible and reliable.

I know there are algorithms to test primality better than this one but I will try them later. First, I'd like to check the entire behavior of the program.

I googled "biginteger console freeze c#" for this issue and found two articles.

1. MillerRabin primality test in C#
2. C# BigInteger and int How to save memory?

The first one says "freeze" and "Biginteger" but the answer wasn't much helpful. The second one referred to saving memory so I thought the issue is about garbage collection. Then I added GC.Collect() at the end of the for loop (the commented out line) but this didn't solve the issue. I got the same result.

How should I solve this issue?

Environment

• Windows 8
• Visual Studio 2017
• C#
• .NET Framework 4.6.1

Answer 1

Your algorithm basically says:

are you divisible by 2? what about 3? what about 5? 7? 11? 13? 17? 19?

etc etc

For small input values, checking all those permutations is fast. For large input values, it can be fast if the large input value has a small factor (e.g. 2, 3, 5 or 37).

But if the large input lacks a small factor (either because it is prime, or because its smallest factor is quite large), your algorithm has to do a lot of checking. Basically it has to check one in three (i.e. two out of every six) numbers up to the square root of the input (until it finds a match). For large numbers, this involves a lot of calculations.

If it is taking too long, you need to code a better / faster IsPrime algorithm. This answer may be helpful in that regard.

You could also consider storing a list of some of the known large prime numbers, to enable those numbers to be looked up quickly (e.g. from a database) rather than 'calculated'.

Re:

(however the console window refreshes only every 17 seconds)

This is because some of the inputs are indeed prime - and thus it takes 17 seconds or so to verify that (i.e. check every permutation). It looks to you like the console is refreshing only every 17 seconds, but instead it is calculating for 17 seconds. Then the subsequent ones calculate very quickly (since they aren't prime) - so it looks like they are coming out 'as a batch'.