Parallel for loop with BigINtegers

Question

So i am working on a program to factor a given number. you write a number in the command line and it gives you all the factors. now, doing this sequentially is VERY slow. because it uses only one thread, if i'm not mistaking. now, i thought about doing it with Parallel.For and it worked, only with integers, so wanted to try it with BigIntegers

heres the normal code:

public static void Factor(BigInteger f)
        {
            for(BigInteger i = 1; i <= f; i++)
            {
                if (f % i == 0)
                {
                    Console.WriteLine("{0} is a factor of {1}", i, f);
                }
            }
        }

the above code should be pretty easy to understand. but as i said, this Very slow for big numbers (above one billion it starts to get impractical) and heres my parallel code:

public static void ParallelFacotr(BigInteger d)
        {
            Parallel.For<BigInteger>(0, d, new ParallelOptions() { MaxDegreeOfParallelism = Environment.ProcessorCount }, i =>
            {
                try
                {
                    if (d % i == 0)
                    {
                        Console.WriteLine("{0} is a factor of {1}", i, d);
                    }
                }
                catch (DivideByZeroException)
                {
                    Console.WriteLine("Done!");
                    Console.ReadKey();
                    Launcher.Main();
                }

            });
        }

now, the above code (parallel one) works just fine with integers (int) but its VERY fast. it factored 1000.000.000 in just 2 seconds. so i thought why not try it with bigger integers. and also, i thought that putting <Biginteger> after the parallel.for would do it. but it doesn't. so, how do you work with bigintegers in parallel for loop? and i already tried just a regular parallel loop with a bigInteger as the argument, but then it gives an error saying that it cannot convert from BigInteger to int. so how do you

Answer 1

Improve your algorithm efficiency first.

While it is possible to use BigInteger you will not have CPU ALU arithmetical logic to resolve arbitrarily big numbers logic in hardware, so it will be noticeably slower. So unless you need bigger numbers than 9 quintillion or exactly 9,223,372,036,854,775,807 then you can use type long.

A second thing to not is that you do not need to loop over all elements as it needs to be multiple of something, so you can reduce

for(BigInteger i = 1; i <= f; i++)
for(long i = 1; i <= Math.Sqrt(f); i++)

That would mean that instead of needing to iterate over 1000000000 items you iterate over 31623.

Additionally, if you still plan on using BigInt then check the parameters:

It should be something in the lines of

Parallel.For(
   0,
   (int)d,
   () => BigInteger.Zero,
   (x, state, subTotal) => subTotal + BigInteger.One,

---

Just for trivia. Some programming languages are more efficient in solving problems than others and in this case, there is a languages Wolfram (previously Mathematica) when solving problems is simpler, granted that you know what you are doing.

However they do have google alternative that answers you directly and it has a decent AI that processes your natural language to give you an exact answer as best as it could.

So finding factors of numbers is easy as:

Factor[9223372036854775809]

or use web api https://www.wolframalpha.com/input/?i=factor+9223372036854775809

You can also call Wolfram kernel from C#, but terms and conditions apply.