<html><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; ">Hi,<div><br></div><div>I'm a newbie to gmp, I've just started using it because I need to calculate large Combinations up to n = 400000.</div><div><br></div><div>I'm using an iterative method as factorials with mpz_fac_ui() are just too slow to calculate with numbers of this size.</div><div><br></div><div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; color: rgb(63, 110, 116); "><font class="Apple-style-span" color="#000000" face="Helvetica" size="3"><span class="Apple-style-span" style="font-size: 12px;">So to calculate C(400000, 200000) I would have:</span></font></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; color: rgb(63, 110, 116); "><br></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; color: rgb(63, 110, 116); "><br></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; "><font class="Apple-style-span" color="#000000">unsigned long n = 400000, k = 200000;</font></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; "><font class="Apple-style-span" color="#000000">mpz_t</font><span style=""><font class="Apple-style-span" color="#000000"> C;</font></span></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; "><span style=""><font class="Apple-style-span" color="#000000"><font class="Apple-style-span" color="#000000">mpz_init_set_ui</font><span style=""><font class="Apple-style-span" color="#000000">(C, n);</font></span> </font></span><font class="Apple-style-span" color="#000000">// start when k=1 C=n</font></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; "><span style=""><font class="Apple-style-span" color="#000000">for</font></span><font class="Apple-style-span" color="#000000">(</font><span style=""><font class="Apple-style-span" color="#000000">long</font></span><font class="Apple-style-span" color="#000000"> i=</font><span style=""><font class="Apple-style-span" color="#000000">2</font></span><font class="Apple-style-span" color="#000000">; i<=k; i++)</font></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; "><font class="Apple-style-span" color="#000000">{</font></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; "><span style=""><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" color="#000000"> </font></span></span><font class="Apple-style-span" color="#000000">mpz_mul_ui(C, C, <font class="Apple-style-span" color="#000000">n-(i-</font><span><font class="Apple-style-span" color="#000000">1</font></span><font class="Apple-style-span" color="#000000">)); </font></font></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; "><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" color="#000000"> </font></span><span style=""><font class="Apple-style-span" color="#000000">mpz_tdiv_q_ui</font></span><font class="Apple-style-span" color="#000000"> (C, C, i);</font></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; "><font class="Apple-style-span" color="#000000">}</font></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; "><br></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; "><font class="Apple-style-span" face="Helvetica" size="3"><span class="Apple-style-span" style="font-size: 12px;">I'm getting the correct result, but this loop of 200k multiply & divides is taking 15 seconds!</span></font></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; "><font class="Apple-style-span" face="Helvetica" size="3"><span class="Apple-style-span" style="font-size: 12px;">I haven't profiled it yet, but obviously, doing the same amount of multiply & divides with a double takes a fraction of a second.</span></font></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; "><font class="Apple-style-span" face="Helvetica" size="3"><span class="Apple-style-span" style="font-size: 12px;"><br></span></font></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; "><font class="Apple-style-span" face="Helvetica" size="3"><span class="Apple-style-span" style="font-size: 12px;">When I comment out the multiply, the problem disappears, so it is the multiply causing the slow down; I assume this is because the value of C is becoming so large.</span></font></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; "><font class="Apple-style-span" face="Helvetica" size="3"><span class="Apple-style-span" style="font-size: 12px;"><br></span></font></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; "><font class="Apple-style-span" face="Helvetica" size="3"><span class="Apple-style-span" style="font-size: 12px;">Is there anything I can do to resolve this problem?</span></font></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; "><font class="Apple-style-span" face="Helvetica" size="3"><span class="Apple-style-span" style="font-size: 12px;"><br></span></font></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; "><font class="Apple-style-span" face="Helvetica" size="3"><span class="Apple-style-span" style="font-size: 12px;">Thanks</span></font></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; "><font class="Apple-style-span" face="Helvetica" size="3"><span class="Apple-style-span" style="font-size: 12px;"><br></span></font></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; "><font class="Apple-style-span" face="Helvetica" size="3"><span class="Apple-style-span" style="font-size: 12px;">Steve</span></font></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; "><font class="Apple-style-span" face="Helvetica" size="3"><span class="Apple-style-span" style="font-size: 12px;"><br></span></font></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; "><font class="Apple-style-span" face="Helvetica" size="3"><span class="Apple-style-span" style="font-size: 12px;">P.S. using doubles the same calculation would be:</span></font></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; "><font class="Apple-style-span" face="Helvetica" size="3"><span class="Apple-style-span" style="font-size: 12px;"> <span class="Apple-style-span" style="font-family: Monaco; font-size: 10px; ">c</span> <font class="Apple-style-span" face="Monaco" size="2"><span class="Apple-style-span" style="font-size: 10px;"><font class="Apple-style-span" color="#000000">= ((double)(n-(i-1))/i)*c;</font></span></font></span></font></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; "><br></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; "><font class="Apple-style-span" face="Helvetica" size="3"><span class="Apple-style-span" style="font-size: 12px;">Am I right in thinking there's no way to do that on a single line using <span class="Apple-style-span" style="font-family: Monaco; font-size: 10px; ">mpz_t</span>?</span></font></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; "><font class="Apple-style-span" face="Helvetica" size="3"><span class="Apple-style-span" style="font-size: 12px;"><br></span></font></div></div></body></html>