Encore une fois sur GCD, l'algorithme euclidien et un peu sur l'histoire des algorithmes en général. Bien sûr, avec des exemples Swift

Les algorithmes sont l'un des sujets centraux de la programmation , ils sont partout (surtout dans les interviews, haha).


(Est-il possible de se passer d'un accordéon à bouton dans un tel article?)

L'un des plus connus est l' algorithme dit euclidien - peut-être le moyen le plus courant de trouver le plus grand diviseur commun (GCD) de deux nombres entiers non négatifs. Il aime aussi souvent commencer à étudier (et apprendre) les sections pertinentes des mathématiques et de l' informatique .

Et Donald Knuth , l'auteur bien connu du traité «The Art of Programming » (et pas seulement), considère même que l'algorithme est le premier de l'histoire (du moins en ce qui concerne les définitions modernes). Parce que, malgré le fait que l'algorithme a été inventé et utilisé avant, en fait, Euclid , qui a vécu aux IV-III siècles. BC (il a déjà été mentionné par Aristote , qui a vécu un siècle plus tôt), Euclide décrit le processus de manière itérative , ce qui est cohérent avec le sens moderne du mot.

Le mot même «algorithme» remonte au nom du mathématicien persan Al-Khwarizmi , qui a vécu aux VIIIe et IXe siècles. déjà AD. Et le début de son utilisation dans un sens proche de celui moderne n'est considéré que le 20e siècle, plus précisément - ses premières décennies, l'essor des technologies de l'information.

Algorithme euclidien

Par curiosité, je vous suggère de vous familiariser avec la description euclidienne de l'algorithme dans l'édition de Knuth. Elle est assez longue, donc cachée sous la coupe:



La description donne deux façons de trouver GCD - par soustraction et division. En fait, ces deux méthodes de mise en œuvre de l'algorithme sont largement connues aujourd'hui.

Voici un exemple de fonction écrite en Swift qui implémente la première méthode:

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. } 

Ici, pour réutilisation, pour mon bien, j'ai apporté une fonction distincte de recherche de GCD, lorsqu'elle est connue immédiatement, sans avoir besoin de suivre un algorithme:

 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 } 

(Si deux nombres sont égaux, alors naturellement leur GCD est également égal à eux. Si l'un des nombres est zéro, alors le GCD sera égal au deuxième nombre, car zéro est divisible par n'importe quel nombre (avec le résultat, bien sûr, également zéro) .)

Seules les valeurs non négatives peuvent être utilisées comme entrée. En conséquence, pour le négatif, vous pouvez utiliser les mêmes méthodes, mais en prenant les nombres modulo. (Oui, le facteur commun peut également être négatif, mais nous recherchons spécifiquement le GCD, et les nombres positifs sont évidemment toujours plus que négatifs.)

Et ici, cela peut ressembler à l'implémentation de la version de l'algorithme par division:

 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. } 

La deuxième version est aujourd'hui considérée comme préférable, car elle contient, en moyenne, un nombre d'étapes significativement plus petit. Cependant, à une époque où les ordinateurs étaient gros et lents, l'opération de division pouvait être une procédure complexe en soi. Et puis la première version de l'algorithme pourrait être plus efficace.

Pour les comparer un peu, j'ai fait plusieurs mesures en utilisant la méthode measure(_:) de ma classe XCTestCase du framework "natif" pour tester le code dans les projets XCTest de XCTest .

En entrée, j'ai utilisé un tableau de paires de nombres aléatoires. Les mesures ont été faites, bien sûr, en utilisant le même tableau pour chaque méthode. J'ai pris la répartition des nombres pour les paires de zéro à 9999. Des mesures ont été faites sur le nombre de calculs (paires de nombres): un, dix, 100, 1000, 10000, 100000, 1 000 000 et 10 000 000. Ce dernier m'a fait attendre le résultat pendant plusieurs minutes, alors j'ai décidé arrêter.

Voici un code de génération d'entrée simple:

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

La mesure elle-même ressemble, par exemple, à ceci:

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

Et voici les résultats du lancement sur mon ordinateur:


(Soustraction - soustraction, division - division.)

En général, on voit très clairement combien la méthode de soustraction perd sur les ordinateurs modernes.

Version "améliorée" de l'algorithme euclidien

Dans la littérature, vous pouvez trouver une version de l'algorithme dans laquelle l'un des nombres à chaque étape, au lieu du reste de la division par la seconde, est remplacé par la différence entre ce décalage et le deuxième nombre, mais uniquement si le reste de la division est supérieur à la moitié du deuxième nombre. Une implémentation de cette version pourrait ressembler à ceci:

 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. } 

Une telle modification réduit le nombre d'étapes dans l'algorithme, mais à en juger par les résultats des mesures sur mon ordinateur, des calculs et des contrôles supplémentaires à chaque étape neutraliseront cet avantage et plus encore:


(Amélioré est la version "améliorée".)

Un peu plus sur la signification de l'algorithme euclidien

L'algorithme a également une version géométrique (pour trouver la plus grande mesure de deux segments).

Bien entendu, l'algorithme a été généralisé pour trouver un GCD d'un nombre quelconque de nombres, pas seulement deux. En un mot, l'idée est la suivante: si nous désignons la fonction de recherche du GCD de deux nombres comme pgcd (a, b), alors, disons, le GCD de trois nombres pgcd (a, b, c) est égal à pgcd (pgcd (a, b), c). Et ainsi de suite, pour tout nombre de nombres, le GCD est trouvé en calculant séquentiellement le GCD du GCD de la paire de nombres précédente et du nombre suivant. Bien que, bien sûr, cela concerne la recherche de GCD en général, et pas seulement l'algorithme euclidien.

Il existe également une généralisation de l'algorithme de recherche des polynômes GCD. Mais cela dépasse déjà le cadre de ce simple post, et dans une certaine mesure, ma connaissance des mathématiques.

Complexité de l'algorithme euclidien

La complexité temporelle de l'algorithme a été étudiée depuis longtemps, pas rapidement et par des hommes beaucoup plus érudits que votre humble serviteur. Cependant, la question est close depuis longtemps et une réponse a été reçue. En fait, au milieu du siècle avant-dernier. Gabriel Lame .

En bref, la réponse est formulée, en fait, par le théorème de Lame lié à cet algorithme. Le nombre d'étapes dans l'algorithme sera égal au numéro de séquence du plus grand nombre de Fibonacci le plus proche , le plus petit des deux nombres de paramètres d'entrée moins 2. En utilisant une notation mathématique légèrement plus traditionnelle, alors si u> v (et v> 1), alors le nombre de passes de l'algorithme sera n - 2 pour v <Fn (Fn est le nombre v Fibonacci le plus proche et n est son numéro de séquence).

Les nombres de Fibonacci croissent de façon exponentielle, respectivement, nous avons une fonction logarithmique du temps d'exécution de l'algorithme (à partir du plus petit des deux nombres d'entrée).

Les mêmes calculs montrent que les pires données d'entrée pour l'algorithme sont deux nombres de Fibonacci consécutifs.

Méthode binaire pour trouver NOD

Parlant de la recherche de GCD, il convient de mentionner l'algorithme proposé déjà dans les années 60 du siècle dernier par un certain Joseph Stein sur lequel je n'ai trouvé aucune information sur le Web. Il (l'algorithme) est orienté vers l' arithmétique binaire et ne contient pas d'opérations de division. L'algorithme ne fonctionne qu'avec des contrôles de parité et une réduction de moitié, ce qui est possible avec les capacités de l'arithmétique binaire seule.

L'algorithme est basé sur quatre faits:

1. Si u et v sont tous les deux pairs, alors pgcd (u, v) = 2 * pgcd (u / 2, v / 2);
2. Si u est pair et v ne l'est pas, gcd (u, v) = gcd (u / 2, v);
3. gcd (u, v) = gcd (u - v, v) (cela découle de l'algorithme euclidien);
4. Si u et v sont tous deux impairs, alors u - v est pair et | u - v | <max (u, v)

Sur Wikipédia, vous pouvez voir la version récursive de l'algorithme (écrite en plusieurs lignes dans les langages de programmation modernes), je ne l'ai pas réécrite sur Swift. Et ici, je donne une implémentation itérative:

 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 } 

Ayant fait des mesures sur les mêmes données, malheureusement, cet algorithme sophistiqué sur mon ordinateur n'a pas répondu aux attentes placées sur lui. Bien sûr, il fonctionne toujours deux fois plus vite que l'algorithme euclidien par soustraction, mais il est nettement inférieur à sa version de division classique. Tableau récapitulatif complet:


(Le binaire est un algorithme binaire.)

(Je n'exclus pas que l'algorithme puisse être écrit plus efficacement que moi, et cela affectera le résultat, mais pourquoi avons-nous besoin de compilateurs?!

Soit dit en passant, cet algorithme, qui a sans aucun doute gagné ses 15 minutes de gloire déjà à l'ère des technologies de l'information (dans une partie antérieure à l'actuelle), était connu dans la Chine ancienne. Sa description se trouve dans des œuvres datant du 1er siècle. AD Bien sûr, en termes de "demi-division" et de soustraction. Et aussi dans le cadre de la réduction des fractions.

Conclusion

Honnêtement, avec cette simple «recherche», je n'allais rien prouver et je ne voulais pas tirer de conclusions révolutionnaires (et je ne l'ai pas fait!). Je voulais juste satisfaire ma curiosité, regarder le travail de différentes approches pour résoudre le problème classique et étirer légèrement mes doigts. J'espère néanmoins que vous étiez également curieux d'observer les résultats!