# 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 '15 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 '15 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. – Bernardo Meurer Sep 27 '15 at 15:53
• Just out of curiosity, why do you need the exact value of the factorial of such a large number? – Hydro Guy Sep 28 '15 at 1:34
• @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. – Kirill Sep 30 '15 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 – Hydro Guy Sep 28 '15 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. – Max Hutchinson Sep 28 '15 at 10:24
• Ah, ok, this is much more interesting, I hadn't read the website, thanks for explaining – Hydro Guy Sep 30 '15 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. – Jeff Oct 4 '15 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. – Max Hutchinson Oct 5 '15 at 11:11