3

Doing very complex BigInteger operations are very slow e.g.

BigInteger.Pow(BigInteger(2),3231233282348);

I was wondering if there is any way I could multi thread any of these basic math functions.

Joe Thomas
  • 5,807
  • 6
  • 25
  • 36
  • 1
    The answer will contain about 1e12 digits; do you really want that answer? – Dmitry Bychenko May 05 '14 at 05:22
  • oh no, It was simply an example. I'm not calculating stuff that large. I just want to know If I can multithread any of these operations. – Joe Thomas May 05 '14 at 05:25
  • 2
    2^bigint n is the same as 1<> which are parallelisable ( * with Karatsuba or use of NTT) see http://stackoverflow.com/q/18577076/2521214 and http://stackoverflow.com/q/18465326/2521214. btw even POW is parallelisable if you use x^y = exp2(y*log2(x)) .. can parallelise multiplication – Spektre May 05 '14 at 07:08

3 Answers3

2

It depends on the math function but I really can't see how you could speed up basic math functions. For these sort of calculations the next step in the process would typically depend on the previous step in the process. Threading would only really help where you have portions of a calculation that can be calculated independently. These could then be combined in a final step to produce the result. You would need to break up these calculations yourself into the portions that can run concurrently.

For example:

If you had a formula with 2 * 3 + 3 * 4. You could run two threads, the first calculating 2 * 3 and the second 3 * 4. You could then pull the results together at the end and sum the two results. You would need to work out how to break down the calculation into something smaller and then thread those accordingly.

In your example with power you could work out the following in 4 threads and then combine the results at the end by multiplying the results:

BigInteger.Pow(BigInteger(2),807808320587);
BigInteger.Pow(BigInteger(2),807808320587);
BigInteger.Pow(BigInteger(2),807808320587);
BigInteger.Pow(BigInteger(2),807808320587);

This would not save you any time at all because all 4 cores would be thrashing around trying to work out the same thing and you would just multiple them by each other at the end which is what a single threaded solution would do anyway. It would even be much slower on some processors as they will often speed up one core if the others are idle. I broke this up using the same thing as breaking up a 2^5 into 2^2 * 2^3.

Graymatter
  • 6,529
  • 2
  • 30
  • 50
  • 1
    To have an example for this take faculty. One thread can calculated `1*2*3*4...` while the other one while `10*11*12`. (Yeah faculity creates great numbers soon but just an example for splitting) In the end both results must be multiplied. You could also make it possible that every thread get the next multiplier when it needs one to *serve* the payload well between them. If you cannot split it, bad luck. – ZoolWay May 05 '14 at 06:26
  • 1
    parallellizing multiplication is trivial to say the least (look up karatsuba's algorithm) haven't thought this through for other operations but I guess such a blanket statement well be wrong for those as well (division may be interesting though). Splitting the power function is rather simple as well considering the basic math a^(n+m) = a^n *a^m etc. – Voo May 05 '14 at 13:44
  • _"This would not save you any time at all because all 4 cores would be thrashing around trying to work out the same thing"_ -- please explain that statement. It's math, not memory operations, so I don't see how there would be any contention between threads. The real problem is that the exponent value results in a number far too large to be of practical use. But in theory, the basic operation is easily parallelized. – Peter Duniho Jun 02 '17 at 17:19
0

The answer of 

 BigInteger.Pow(BigInteger(2), 3231233282348);

will contain 

  Log(2)/Log(10) * 3231233282348 == 9.727e11

digits; so it requires 900 GB to write the answer. That's why it that slow

Dmitry Bychenko
  • 180,369
  • 20
  • 160
  • 215
  • 1
    It was just an example. See also: The comments on the question. –  May 05 '14 at 05:26
  • 1
    I don't see how it answers the question. The question was NOT why it is slow, but how to speed it up using multithreading. – amit May 05 '14 at 05:51
-2

If you're using .NET 4.5 read about async await:

http://blog.stephencleary.com/2012/02/async-and-await.html

TamerM
  • 722
  • 7
  • 25