再一次介绍GCD，欧几里得算法和一般算法的历史。 当然有Swift的例子

算法是编程的中心主题之一，它们无处不在（尤其是在访谈中，哈哈）。


（在这样的帖子中是否可以在没有按钮手风琴的情况下进行操作？）

最著名的方法之一就是所谓的欧几里得算法 -也许是找到两个非负整数的最大公约数（GCD）的最常用方法。 他还经常喜欢开始学习（和学习） 数学和计算机科学的相关部分。

著名的“ 编程艺术 ”一书的作者唐纳德·努斯 （不仅如此）甚至认为该算法是历史上第一个（至少就现代定义而言）。 因为尽管实际上是算法的发明者和先驱者 ，但实际上居住在IV-III世纪的Euclid还是这样 。 欧几里得（BC）（居住在一个世纪以前的亚里斯多德已经提到过），欧几里得反复地描述了这一过程，这与该词的现代含义是一致的。

“算法”这个词可以追溯到波斯数学家Al-Khwarizmi的名字，后者居住在八至九世纪。 已经公元。 而且，从某种意义上讲，它的使用开始接近现代，而更确切地说，它只是20世纪-最初的几十年，即信息技术的兴起。

欧几里得算法

为求好奇，我建议您熟悉Knuth编辑中对该算法的欧几里得描述。 它很长，因此隐藏在切口下：



描述提供了两种查找GCD的方法-减法和除法。 实际上，这两种实现算法的方法如今已广为人知。

这是用Swift编写的实现第一个方法的函数的示例：

func subtractionGCD(_ firstNumber: Int, _ secondNumber: Int) -> Int { if let simpleGCD = simpleCasesGCD(firstNumber, secondNumber) { return simpleGCD } var firstNumber = firstNumber var secondNumber = secondNumber while firstNumber != 0, secondNumber != 0 { if firstNumber > secondNumber { firstNumber = firstNumber - secondNumber } else { secondNumber = secondNumber - firstNumber } } return firstNumber + secondNumber // One of them is 0. } 

为了重用，为了我的缘故，我引入了一个单独的函数案例，当立即知道GCD时便搜索GCD，而无需遵循任何算法：

 func simpleCasesGCD(_ firstNumber: Int, _ secondNumber: Int) -> Int? { if firstNumber == secondNumber { return firstNumber // Any. } if firstNumber == 0 { return secondNumber } if secondNumber == 0 { return firstNumber } return nil } 

（如果两个数字相等，那么它们的GCD自然也等于它们。如果任何数字为零，则GCD将等于第二个数字，因为零可以被任何数字整除（结果当然也为零） ）

仅非负值可以用作输入。 因此，对于负数，您可以使用相同的方法，但对模取数字。 （是的，公因子也可以为负，但是我们正在专门寻找GCD，正数显然总是大于负数。）

在这里，它看起来像是除法算法版本的实现：

 func divisionGCD(_ firstNumber: Int, _ secondNumber: Int) -> Int { if let simpleGCD = simpleCasesGCD(firstNumber, secondNumber) { return simpleGCD } var firstNumber = firstNumber var secondNumber = secondNumber while firstNumber != 0, secondNumber != 0 { if firstNumber > secondNumber { firstNumber = firstNumber % secondNumber } else { secondNumber = secondNumber % firstNumber } } return firstNumber + secondNumber // One of them is 0. } 

今天，第二个版本被认为是更可取的，因为它平均包含的步骤数量要少得多。 但是，在计算机又大又慢的时候，除法运算本身可能是一个复杂的过程。 然后，该算法的第一个版本可能会更有效。

为了比较它们，我使用“本机”框架的XCTestCase类的measure(_:)方法进行了几次测量，以测试XCTest的Xcode项目中的XCTest 。

作为输入，我使用了随机数对数组。 当然，每种方法使用相同的阵列进行测量。 我采用了从零到9999的成对数字分布。对计算数量（成对数字）进行了测量：1、10、100、1000、10000、100000、1,000,000和10,000,000。后者使我期望结果持续几分钟，所以我决定了停下来

这是一个简单的输入生成代码：

 let pairs = (0..<100).map { _ in (Int.random(in: 0..<10000), Int.random(in: 0..<10000)) } // Generates 100 pairs. 

测量本身看起来像这样：

 func testSubstractionGCDPerformance() { measure() { _ = pairs.map { substractionGCD($0, $1) } } } 

这是在我的计算机上启动的结果：


（减法-减法，除法-除法。）

通常，在现代计算机上可以清楚地看到减法损失了多少。

欧几里得算法的“改进”版本

在文献中，您可以找到一种算法的版本，其中每个步骤中的一个数字而不是除以第二个数字的余数，而是由此偏移量和第二个数字之间的差代替，但前提是除法的余数大于第二个数字的一​​半。 此版本的实现可能如下所示：

 func improvedDivisionGCD(_ firstNumber: Int, _ secondNumber: Int) -> Int { if let simpleGCD = simpleCasesGCD(firstNumber, secondNumber) { return simpleGCD } var firstNumber = firstNumber var secondNumber = secondNumber while firstNumber != 0, secondNumber != 0 { if firstNumber > secondNumber { let firstNumberClaim = firstNumber % secondNumber if firstNumberClaim > secondNumber / 2 { firstNumber = abs(firstNumberClaim - secondNumber) } else { firstNumber = firstNumberClaim } } else { let secondNumberClaim = secondNumber % firstNumber if secondNumberClaim > firstNumber / 2 { secondNumber = abs(secondNumberClaim - firstNumber) } else { secondNumber = secondNumberClaim } } } return firstNumber + secondNumber // One of them is 0. } 

这样的修改减少了算法中的步骤数量，但是从我计算机上的测量结果来看，每一步的额外计算和检查将抵消这种优势，甚至更多：


（改进的是“改进的”版本。）

关于欧几里得算法的意义的更多信息

该算法还有一个几何版本（用于找到两个部分的最大度量）。

当然，该算法被通用化以找到任意数量的GCD，而不仅仅是两个。 简而言之，想法是这样的：如果我们将搜索两个数字的GCD的功能指定为gcd（a，b），那么说三个数字gcd（a，b，c）的GCD等于gcd（gcd（a，b），c）。 依此类推，对于任何数量的数字，通过依次计算前一对数字和下一个数字的GCD的GCD来找到GCD。 当然，尽管这通常涉及对GCD的搜索，而不仅仅是欧几里得算法。

查找GCD多项式的算法也有一个概括。 但这已经超出了本篇简单文章的范围，并且在某种程度上还超出了我的数学知识。

欧氏算法复杂度

该算法的时间复杂性已经研究了很长时间，没有比您的谦卑仆人更快，学识渊博的人来研究。 但是，这个问题早已结束，并且已经收到答复。 实际上，早在上世纪中叶之前。 加布里埃尔·莱姆（Gabriel Lame） 。

简而言之，答案实际上是由与此算法相关的Lame定理提出的。 算法中的步数将等于最接近的较大斐波那契数的序号，即输入参数的两个数中的最小数减去2。使用稍微更传统的数学符号，则如果u> v（且v> 1），则算法的通过次数将为n-2 v <Fn（Fn是最接近的v斐波那契数，n是其序列号）。

斐波那契数分别呈指数增长，我们有一个算法执行时间的对数函数（来自两个输入数中较小的一个）。

相同的计算表明，该算法最差的输入数据是两个连续的斐波那契数。

查找NOD的二进制方法

说到搜索GCD，值得一提的是某位约瑟夫·斯坦（Joseph Stein）在上个世纪60年代就已经提出了该算法，但我根本没有在网上找到任何信息。 它（算法）面向二进制算术 ，不包含除法运算。 该算法仅通过奇偶校验和减半操作，仅通过二进制算术功能就可以实现。

该算法基于四个事实：

1. 如果u和v均为偶数，则gcd（u，v）= 2 * gcd（u / 2，v / 2）;
2. 如果u是偶数而v不是，则gcd（u，v）= gcd（u / 2，v）;
3. gcd（u，v）= gcd（u-v，v）（根据欧几里得算法得出）；
4. 如果u和v均为奇数，则u-v为偶数，| u-v | <max（u，v）

在Wikipedia上，您可以看到该算法的递归版本（以现代编程语言用几行编写），但我并未在Swift上对其进行重写。 在这里，我给出一个迭代的实现：

 func binaryGCD(_ firstNumber: Int, _ secondNumber: Int) -> Int { if let simpleGCD = simpleCasesGCD(firstNumber, secondNumber) { return simpleGCD } var firstNumber = firstNumber var secondNumber = secondNumber var shift = 0 while (firstNumber | secondNumber) & 1 == 0 { shift += 1 firstNumber >>= 1 secondNumber >>= 1 } while firstNumber & 1 == 0 { firstNumber >>= 1 } repeat { while secondNumber & 1 == 0 { secondNumber >>= 1 } if firstNumber > secondNumber { swap(&firstNumber, &secondNumber) } secondNumber -= firstNumber } while secondNumber != 0 return firstNumber << shift } 

不幸的是，在对相同数据进行测量之后，我计算机上的这种复杂算法未能实现对它的期望。 当然，通过减法，它的工作速度仍然是欧几里得算法的两倍，但明显不如其经典除法版本。 完整摘要表：


（二进制是二进制算法。）

（我不排除算法的编写效率比我高，这会影响结果，但是我们需要编译器做什么？！

顺便说一句，这种算法在信息技术时代无疑已经获得了15分钟的成名（比现在的算法早），在中国古代就广为人知。 他的描述出现在可追溯到1世纪的作品中。 广告 当然，用“半除法”和减法之类的术语来说。 并且在减少分数的情况下。

结论

老实说，通过这个简单的“研究”，我不会证明任何事情，也不想做出任何革命性的结论（而且我没有！）。 我只是想满足我的好奇心，研究解决经典问题的不同方法的工作，并稍微张开手指。 不过，希望您也很好奇观察结果！