Los algoritmos son uno de los temas centrales en la
programación , están en todas partes (especialmente en entrevistas, jaja).
(¿Es posible prescindir de un acordeón de botón en una publicación de este tipo?)Uno de los más famosos es el llamado
algoritmo euclidiano , quizás la forma más común de encontrar el
máximo divisor común (MCD) de dos enteros no negativos. A menudo también le gusta comenzar a estudiar (y aprender) las secciones relevantes de
matemáticas y
ciencias de la computación .
Y
Donald Knuth , el famoso autor del tratado "El
arte de la programación " (y no solo), incluso considera que el algoritmo es el primero en la historia (al menos con respecto a las definiciones modernas). Porque, a pesar de que el algoritmo fue inventado y utilizado antes, de hecho,
Euclides , que vivió en los siglos IV-III. BC (ya fue mencionado por
Aristóteles , que vivió un siglo antes), Euclides describe el proceso de forma
iterativa , lo cual es consistente con el significado moderno de la palabra.
La misma palabra "algoritmo" se remonta al nombre del matemático persa
Al-Khwarizmi , que vivió alrededor de los siglos VIII-IX. ya AD. Y el comienzo de su uso en un sentido cercano al moderno se considera solo el siglo XX, más precisamente, sus primeras décadas, el surgimiento de la tecnología de la información.
Algoritmo Euclidiano
En aras de la curiosidad, sugiero que se familiarice con la descripción euclidiana del algoritmo en la edición de Knuth. Es bastante largo, por lo tanto oculto debajo del corte:
Descripción del algoritmo euclidiano cercano al originalOferta Para dos enteros positivos dados, encuentre su máximo común divisor.
Sean A y C dos enteros positivos dados; Se requiere para encontrar su MCD. Si el número A es divisible por C, entonces el número C es un divisor común de los números C y A, ya que se divide. Y obviamente, será el mayor divisor, ya que no hay un número mayor que el número C que divide a C.
Pero si C no divide el número A, entonces restaremos continuamente el más pequeño de los números A y C del más grande hasta que obtengamos un número que divida por completo el restado anterior. Esto debería suceder tarde o temprano, porque si la diferencia es igual a uno, la unidad dividirá la resta anterior.
Ahora suponga que E es el resto positivo de dividir el número A por C; dejemos que F sea el resto positivo de dividir C entre E y dejemos que F divida a E. Dado que F divide a E y E divide a C - F, F también divide a C - F. Pero también se divide a sí mismo, entonces F divide a C, y C divide a A - E; por lo tanto, F también divide A - E, pero también divide E; por lo tanto, F divide a A. En consecuencia, F es un divisor común de los números A y C.
Ahora afirmo que también es un MCD. De hecho, si F no es el máximo común divisor de los números A y C, entonces hay un número mayor que dividirá estos dos números. Deje que ese número sea G.
Como el número G divide el número C y el número C divide A - E, G también divide el número A - E. El número G también divide el número entero A, por lo que divide el resto E. Pero E divide C - F, entonces G también divide C - F. Y el número G también divide el número entero C, ya que divide el resto de F; así, un número mayor divide a uno menor, y esto es imposible.
Por lo tanto, no hay un número mayor que F que divida A y C; por lo tanto, el número F es MCD.
Consecuencia Este razonamiento hace obvio el supuesto de que cualquier número que divide dos números divide su MCD. Rt
La descripción ofrece dos formas de encontrar GCD: por sustracción y división. En realidad, estos dos métodos de implementación del algoritmo son ampliamente conocidos hoy en día.
Aquí hay un ejemplo de una función escrita en
Swift que implementa el primer método:
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
Aquí, para su reutilización, por el bien de mi causa, introduje una función separada de casos de búsqueda de GCD, cuando se sabe de inmediato, sin la necesidad de seguir ningún algoritmo:
func simpleCasesGCD(_ firstNumber: Int, _ secondNumber: Int) -> Int? { if firstNumber == secondNumber { return firstNumber
(Si dos números son iguales, entonces, naturalmente, su MCD también es igual a ellos. Si alguno de los números es cero, entonces el MCD será igual al segundo número, porque cero es divisible por cualquier número (con el resultado, por supuesto, también cero) .)
Solo se pueden usar valores no negativos como entrada. En consecuencia, para lo negativo, puede usar los mismos métodos, pero tomando el módulo de números. (Sí, el factor común también puede ser negativo, pero estamos buscando específicamente el MCD, y los números positivos son obviamente siempre más que negativos).
Y aquí puede parecer la implementación de la versión del algoritmo por división:
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
La segunda versión hoy se considera preferible, ya que contiene, en promedio, un número significativamente menor de pasos. Sin embargo, en un momento en que las computadoras eran grandes y lentas, la operación de división podría ser un procedimiento complejo en sí mismo. Y luego la primera versión del algoritmo podría ser más efectiva.
Para compararlos un poco, hice varias mediciones utilizando el método
measure(_:) de mi clase
XCTestCase del marco "nativo" para probar código en proyectos
XCTest de
XCTest .
Como entrada, utilicé una matriz de pares de números aleatorios. Las mediciones se realizaron, por supuesto, utilizando la misma matriz para cada método. Tomé la distribución de números para pares de cero a 9999. Las mediciones se realizaron en la cantidad de cálculos (pares de números): uno, diez, 100, 1000, 10000, 100000, 1,000,000 y 10,000,000. Este último me hizo esperar el resultado durante varios minutos, así que decidí hacerlo. para parar
Aquí hay un código de generación de entrada simple:
let pairs = (0..<100).map { _ in (Int.random(in: 0..<10000), Int.random(in: 0..<10000)) }
La medida en sí se ve, por ejemplo, así:
func testSubstractionGCDPerformance() { measure() { _ = pairs.map { substractionGCD($0, $1) } } }
Y aquí están los resultados del lanzamiento en mi computadora:
(Resta - resta, división - división.)En general, es muy claramente visible cuánto pierde el método de sustracción en las computadoras modernas.
Versión "mejorada" del algoritmo euclidiano
En la literatura puede encontrar una versión del algoritmo en el que uno de los números en cada paso, en lugar del resto de dividir por el segundo, se reemplaza por la diferencia entre este desplazamiento y el segundo número, pero solo si el resto de la división es más de la mitad del segundo número. Una implementación de esta versión podría verse así:
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
Tal modificación reduce el número de pasos en el algoritmo, pero a juzgar por los resultados de las mediciones en mi computadora, los cálculos y verificaciones adicionales en cada paso neutralizarán esta ventaja y aún más:
(Mejorada es la versión "mejorada").Un poco más sobre la importancia del algoritmo euclidiano
El algoritmo también tiene una versión geométrica (para encontrar la medida más grande de dos segmentos).
El algoritmo fue, por supuesto, generalizado para encontrar GCD de cualquier número de números, no solo dos. En pocas palabras, la idea es la siguiente: si designamos la función de buscar el MCD de dos números como mcd (a, b), entonces, digamos, el MCD de tres números mcd (a, b, c) es igual a mcd (mcd (a, b), c). Y así sucesivamente, para cualquier número de números, se encuentra el MCD calculando secuencialmente el MCD del MCD del par de números anterior y el número siguiente. Aunque, por supuesto, esto se refiere a la búsqueda de GCD en general, y no solo al algoritmo euclidiano.
También hay una generalización del algoritmo para encontrar polinomios GCD. Pero esto ya está más allá del alcance de esta simple publicación, y hasta cierto punto, mi conocimiento de las matemáticas.
Algoritmo Euclidiano Complejidad
La complejidad temporal del algoritmo ha sido investigada durante mucho tiempo, no de manera rápida y por hombres mucho más eruditos que su humilde servidor. Sin embargo, la pregunta lleva mucho tiempo cerrada y se ha recibido una respuesta. En realidad, de vuelta a mediados del siglo anterior al pasado.
Gabriel Lame .
En resumen, la respuesta está formulada, de hecho, por el teorema de Lame relacionado con este algoritmo. El número de pasos en el algoritmo será igual al número de secuencia del número de
Fibonacci más grande más cercano
, el más pequeño de los dos números de parámetros de entrada menos 2. Usando una notación matemática un poco más tradicional, entonces si u> v (y v> 1), entonces el número de pasadas del algoritmo será n - 2 para v <Fn (Fn es el número de Fibonacci v más cercano, yn es su número de secuencia).
Los números de Fibonacci crecen exponencialmente, respectivamente, tenemos una función logarítmica del tiempo de ejecución del algoritmo (del menor de los dos números de entrada).
Los mismos cálculos muestran que los peores datos de entrada para el algoritmo son dos números consecutivos de Fibonacci.
Método binario para encontrar NOD
Hablando de la búsqueda de GCD, vale la pena mencionar el algoritmo propuesto ya en los años 60 del siglo pasado por cierto Joseph Stein sobre el cual no encontré ninguna información en la Web. Este (el algoritmo) está orientado a la
aritmética binaria y no contiene operaciones de división. El algoritmo funciona solo con comprobaciones de paridad y reducción a la mitad, lo cual es factible solo con las capacidades de la aritmética binaria.
El algoritmo se basa en cuatro hechos:
- Si u y v son ambos pares, entonces mcd (u, v) = 2 * mcd (u / 2, v / 2);
- Si u es par y v no lo es, gcd (u, v) = gcd (u / 2, v);
- gcd (u, v) = gcd (u - v, v) (esto se desprende del algoritmo euclidiano);
- Si u y v son impares, entonces u - v es par y | u - v | <max (u, v)
En Wikipedia puedes ver la versión recursiva del algoritmo (escrito en varias líneas en lenguajes de programación modernos), no lo reescribí en Swift. Y aquí les doy una implementación iterativa:
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 }
Habiendo hecho mediciones en los mismos datos, desafortunadamente, este algoritmo sofisticado en mi computadora no estuvo a la altura de las expectativas puestas en él. Por supuesto, todavía funciona dos veces más rápido que el algoritmo euclidiano por sustracción, pero es notablemente inferior a su versión de división clásica. Tabla resumen completa:
(Binario es un algoritmo binario).(No excluyo que el algoritmo se pueda escribir de manera más eficiente que yo, y esto afectará el resultado, pero ¿para qué necesitamos compiladores?
Por cierto, este algoritmo, que sin duda ganó sus 15 minutos de fama ya en la era de la tecnología de la información (en una parte anterior a la actual), era conocido en la antigua China. Su descripción se encuentra en obras que datan del siglo primero. AD Por supuesto, en términos como "media división" y resta. Y también en el contexto de la reducción de fracciones.
Conclusión
Honestamente, con esta simple "investigación" no iba a demostrar nada y no quería sacar conclusiones revolucionarias (¡y no lo hice!). Solo quería satisfacer mi curiosidad, mirar el trabajo de diferentes enfoques para resolver el problema clásico y estirar los dedos ligeramente. Sin embargo, ¡espero que también haya tenido curiosidad por observar los resultados!