Databases
StackOverflow2013
Postsdbo
POGCD computation issues with GNU MP Library
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POGCD computation issues with GNU MP Library
    text
    copied!<p>I have a question about GNU MP, could you please help me how to proceed with that. I using "The GNU Multiple Precision Arithmetic Library" Edition 5.1.1 on Windows. (MinGW\gcc + MSYS)</p> <p>There is an mpz_gcd function exist to calculate "gcd" of two integers.</p> <pre><code>void mpz_gcd (mpz_t rop, mpz_t op1, mpz_t op2); </code></pre> <p>As far as I get from documentation, there are couple of algorithms implemented in GNU MP for computation of Greatest Common Divisor. Among them:</p> <ul> <li>Binary GCD</li> <li>Lehmer’s algorithm</li> <li>Subquadratic GCD</li> </ul> <p>The algorithm that is used seems to be selected automatically, based on the input size of integers.</p> <blockquote> <p>Currently, the binary algorithm is used for GCD only when N &lt; 3.</p> <p>For inputs larger than GCD_DC_THRESHOLD, GCD is computed via the HGCD (Half GCD) function as a generalization to Lehmer’s algorithm.</p> </blockquote> <p>So, I guess there are at least three different approaches to get gcd(a, b). The main problem for me: I want to specify which algorithm to use by myself. I would compare time execution of these algorithms on the random large input (i.e. 10^5 bits) to find out some common trends: what is that point where using "Binary GCD" becomes worse than "Lehmer's method", is "HGCD-Lehmer generalization" is really better than straightforward Lehmer, etc.</p> <p>Is there any simple way to specify the algorithm you want to use? Any way to pull out this algorithm from the library, any way to modify some "#define" variables. Is it possible to do something like I want without library recompilation? I'm just beginner there and I don't feel able to figure out all sort of things inside the library.</p> <p>P.S. Probably somebody would be interested what's will come out of that. I've got some code on the github: <a href="https://github.com/int000h/gcd_gcc" rel="nofollow">https://github.com/int000h/gcd_gcc</a></p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload