# GPU vs CPU calculation

I've been working on calculating large factorials ($N>10^9$) and I was wondering if it wasn't faster to use the GPU to run the calculations on something like openCL. What I realized however was that, not only I didn't know if it was worth it in that case, I couldn't tell when it is or isn't appropriate to use a GPU for number crunching. So, basically, what are the pros and cons of using GPU and CPU for such large numbers ($10^9!$) or when is it worth it at all to do GPU implementation?

• Mathematical notation can be used in your posts here with MathJax and $\LaTeX$, although this is not supported on all StackExchange sites (nor on Meta.SciComp.SE).
– hardmath
Sep 27, 2015 at 8:32
• Stirling's approximation tells me $10^9!$ will have over eight and a half billion digits. If required, outputting the result in full would also take time regardless of how it is computed.
– hardmath
Sep 27, 2015 at 14:31
• @hardmath I'm aware it will take time hahaha. I'm preparing 128Gb of DDR4 plus 4 512Gb SSDs on RAID 0 configuration to handle all the data. My options are an i7 extreme or two GTX980's tho for the calculation. Sep 27, 2015 at 15:53
• Factorials are a bit too regular and predictable (usually people try $\pi$ or $\gamma$ - e.g., $\lfloor 10^{10^6}\pi\rfloor$). For example, $10^9!$ is divisible by $2^{10^9-13}$ and by $5^{(10^9-8)/4}$, so the least significant $\sim249,999,998$ decimal digits are just zeros - any computational effort on them is completely wasted. Sep 30, 2015 at 1:23
• @Arengorn Ah, okay. I looked it up at mathworld.wolfram.com/BrocardsProblem.html and it cites Berndt & Galway - but they computed $n!+1$ modulo some primes, and then established whether a solution existed via the Chinese remainder theorem. That is vastly more efficient than computing $n!$ directly. They seem to have been using mid-1990's hardware, so I bet this should be easy now. Can I recommend that you ask a separate question explicitly stating the goal and all the context? You might get more direct/helpful responses for your actual problem. Sep 30, 2015 at 1:35

This may have gone unnoticed in the comments under the original question, but computing $10^9!$ yields a number with 8.5 billion digits, that is it is on the order of $10^{9\cdot 10^9}$. Given that $10^{9\cdot 10^9}=1000^{3\cdot 10^9} \approx 1024^{3\cdot 10^9}=(2^{10})^{3\cdot 10^9}=2^{3\cdot 10^{10}}$, you need approximately $3\cdot 10^{10}$ bits, or around $4\cdot 10^9$ bytes to simply represent such a number. That's a sizable amount of memory.

Now imagine that you want to compute this number in parallel by having each processor compute a part of the factorial. For example, processor $p$ computes $Q_p=\prod_{k=N_{p-1}}^{N_p} k$, then the total can be computed by $N_P! = \prod_{p=1}^P Q_p$ if you choose $N_0=1$ and $P$ is the number of processors. But generally, each one of the $Q_p$ are going to be of the same order of magnitude as the final result (well, not quite, but you get the general idea), so if you have $P$ processors, you need to provision $P$ times as much memory as it takes to store the final result.

On a GPU, you have many processors, $P={\cal O}(1000)$. If each of the numbers you have to store already takes 4 GB of memory, then if you have to store it 1000 times over, you very quickly end up with an amount of memory that is not only not available on a typicaly GPU, but in fact not even in regular desktop computers.

I think what this means is that you are biting off more than you can likely chew if you try to compute $10^9!$.

It is a bit old, but the CUDA Multiprecision Arithmetic Library probably supports the operations you need, and reports 2-4x speed-ups vs a CPU socket. It claims to have a GMP-like interface, so porting you code could be straight-forward, relative to writing custom kernel code.

• 2x-4x is not that impressive if the comparsion cpu is a 4-core i7 Sep 28, 2015 at 1:42
• 2x-4x was against the dual socket opteron, which was the more relevant comparison in its day. The website, and all the hardware on it, is out of date. Sep 28, 2015 at 10:24
• Ah, ok, this is much more interesting, I hadn't read the website, thanks for explaining Sep 30, 2015 at 2:02
• If GPU folks claim a speed up less than 10x, it's probably useless, because the majority of their performance claims are wildly exaggerated and tailored towards cases where they win. Oct 4, 2015 at 22:14
• @Jeff do you have a specific criticism of their performance analysis? They avoid the cardinal sin of comparing to a single CPU core, which is the only way a GPU could ever top 10x, and they do a parameter sweep that includes some of the ramp-up region. I'd like to also see vector lengths that were lower and operations with higher arithmetic intensity, sure, but what they have done seems common enough and robust. Oct 5, 2015 at 11:11