GCD算法大整数 [英] GCD algorithms for a large integers

问题描述

我在寻找有关快速GCD计算算法的信息。 特别是，我想看看在所有实现。

I looking for the information about fast GCD computation algorithms. Especially, I would like to take a look at the realizations of that.

最有趣的对我来说： - 莱默GCD算法， - 加速GCD算法， - k元算法， - 克努特 - Schonhage与FFT。 我已经完全对加速GCD算法没有信息，我只是看到它被提到了最有效，最快速的GCD计算方法上的媒体投入了几篇文章（〜1000位）

The most interesting for me: - Lehmer GCD algorithm, - Accelerated GCD algorithm, - k-ary algorithm, - Knuth-Schonhage with FFT. I have completely NO information about the accelerated GCD algorithm, I just have seen a few articles where it was mentioned as the most effective and fast gcd computation method on the medium inputs (~1000 bits)

他们看起来好多我很难从理论上来看理解。 有谁请分享code（基于C preferable ++）与实现从列表中选择任何算法\部件或分享这样做的任何经验。我也将是AP preciate的任何信息，意见，建议，地方看看。我有一类具有大整数的工作，但我没有方法与它合作。除了，可以肯定，欧几里得和二进制GCD算法，这是看起来清楚，我现在;没有与它的问题。 最主要的我想获得最终：实现莱默GCD的code。 （它是从列表中更容易）

They looks much difficult for me to understand from the theory view. Could anybody please share the code (preferable on c++) with realization of any algorithm\parts from the list or share any experience of doing this. I will be also appreciate for any information, comments, advice, places to look into. I have a class to work with big integers, but I have no methods to work with it. Except, for sure, Euclid and Binary gcd algorithms, which is looks clear to me for now; there is no problems with it. The main thing I would like to get in the end: the code of realization lehmer gcd. (it is the easier from the list)

推荐答案

克努特探讨了GCD的长度的计算机程序设计的，第2卷，第4.5.2节的艺术。克努特给出算法E欧几里得的原始方法，算法A作为现代版的欧几里得算法，算法B作为二进制方法和算法L，以莱默的方法，以及扩展欧几里德算法算法十，我描述（用$ C $三）原来的欧几里德算法的的现代欧几里德算法的的二进制算法和href="http://programmingpraxis.com/2009/07/07/modular-arithmetic/">扩展欧几里德算法在我的博客的

Knuth explores the GCD at length in The Art of Computer Programming, Volume 2, Section 4.5.2. Knuth gives Algorithm E as the original method of Euclid, Algorithm A as the modern version of Euclid's algorithm, Algorithm B as the binary method and Algorithm L as Lehmer's method, as well as the extended Euclidean algorithm in Algorithm X. I describe (with code) the original Euclidean algorithm, the modern Euclidean algorithm, the binary algorithm, and the extended Euclidean algorithm at my blog.

本文给出了几个版本的SCH＆ouml一个很好的说明; nhage的算法，其中包括code。

This paper gives a good description of several versions of Schönhage's algorithms, including code.

这篇关于GCD算法大整数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！