Parallel implementation of Schönhage's integer GCD algorithm
After giving a summary of methods for finding the greatest common divisor \((a,b)\) of two given integers \(a\), \(b\), the author concentrates on Schönhage's method, which works with quotients rather than remainders. This method is also particularly applicable to the extended problem in which integers \(s\), \(t\) are found such that \((a,b)= sa+ tb\). Tests with consecutive members of the Fibonacci sequence (\(a= F_n\), \(b= F_{n-1}\)) show that Schönhage's method is less effective than other methods for small values of \(n\), but much more effective for larger values, say \(n> 10^6\). Parts of the algorithm are set out in \(C++\) notation. It is then shown how parts of the implementation can be parallelized, and tables show the results of experiments with randomly chosen \(a\), \(b\) of about the same length: using 4 processors makes a noticeable improvement, but the further improvement with more processors is slight. For the entire collection see [Zbl 0891.00022].
- Parallel implementation of the accelerated integer GCD algorithm
- An improved parallel algorithm for integer GCD
- A parallel extended GCD algorithm
- Two fast parallel GCD algorithms of many integers
- On a parallel Lehmer-Euclid GCD algorithm
- scientific article; zbMATH DE number 554529
- scientific article; zbMATH DE number 4165009
- scientific article; zbMATH DE number 708866
- Some parallel algorithms for integer factorisation
- Regularity of the Euclid algorithm; application to the analysis of fast GCD algorithms
- An algorithm reminiscent of Euclidean-gcd for computing a function related to pinwheel scheduling
- Parallel implementation of the accelerated integer GCD algorithm
- An extended Jebelean-Weber-Sedjelmaci GCD algorithm
- \((1+i)\)-ary GCD computation in \(\mathbb Z[i]\) as an analogue to the binary GCD algorithm.
This page was built for publication: Parallel implementation of Schönhage's integer GCD algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3840151)
