Geek asks and answers

GCD Algorithms for Large Integers

I am looking for information on fast GCD calculation algorithms. Moreover, I would like to take a look at the implementation of this.

The most interesting thing for me: - Lehmer GCD algorithm, - Accelerated GCD algorithm, - k-ary algorithm, - Knut-Schonhage with FFT. I don’t have ANY information about the accelerated GCD algorithm, I just saw several articles where it was mentioned as the most efficient and fastest method for calculating gcd at the inputs of the environment (~ 1000 bits)

It is very difficult for me to understand from the theory of view. Can someone please share the code (preferably in C ++) with the implementation of any algorithm / parts from the list or share experience. I would also appreciate any information, comments, tips, places to study. I have a class for working with large integers, but I have no methods for working with it. Except, of course, the Euclid and Binary gcd algorithms, which now seem clear to me; there is no problem with that. The main thing I would like to get at the end: lehmer gcd implementation code. (this is easier on the list)

+3
source share
2 answers

GCD " ", 2, 4.5.2. , , , X. ( ) , , .

Sch & ouml; nhage, .

+6

user448810. . . longnum lib, ​​ , /

longnum gcd(longnum x,longnum y)
    {
    x.sig=+1; x.integer(); // x=abs(int(x))
    y.sig=+1; y.integer(); // y=abs(int(y))
    longnum z; int x0,y0,sh=0;
    for (;;)
        {
        if (x.iszero()) { z=y; break; } // if (!x) ...
        if (y.iszero()) { z=x; break; } // if (!y) ...
        x0=x.a[_longnum_a1]&1; // x0=x&1
        y0=y.a[_longnum_a1]&1; // y0=y&1
        if ((!x0)&&(!y0)) { x>>=1; y>>=1; sh++; continue; }
        if (!x0) { x>>=1; continue; }
        if (!y0) { y>>=1; continue; }
        if (x<y) y-=x;
        else     x-=y;
        }
    return (z<<sh);
    }
+1

More articles:


All Articles