Mais uma vez sobre o GCD, o algoritmo euclidiano e um pouco sobre a história dos algoritmos em geral. Claro que com exemplos Swift

Algoritmos são um dos tópicos centrais da programação , eles estão por toda parte (especialmente em entrevistas, haha).


(É possível fazer sem um acordeão de botão em um post?)

Um dos mais famosos é o chamado algoritmo euclidiano - talvez a maneira mais comum de encontrar o maior divisor comum (MDC) de dois números inteiros não negativos. Ele também costuma gostar de começar a estudar (e aprender) as seções relevantes de matemática e ciências da computação .

E Donald Knuth , o notório autor do tratado “A Arte da Programação ” (e não apenas), até considera o algoritmo o primeiro da história (pelo menos no que diz respeito às definições modernas). Porque, apesar do fato de o algoritmo ter sido inventado e usado antes, de fato, Euclides , que viveu nos séculos IV-III. BC (já foi mencionado por Aristóteles , que viveu um século antes), Euclides descreve o processo iterativamente , o que é consistente com o significado moderno da palavra.

A própria palavra "algoritmo" remonta ao nome do matemático persa Al-Khwarizmi , que viveu por volta dos séculos VIII-IX. já AD. E o início de seu uso, em um sentido próximo ao moderno, é considerado apenas o século 20, mais precisamente - suas primeiras décadas, o surgimento da tecnologia da informação.

Algoritmo Euclidiano

Por uma questão de curiosidade, sugiro que você se familiarize com a descrição euclidiana do algoritmo na edição de Knuth. É bastante longo, portanto, oculto sob o corte:



A descrição fornece duas maneiras de encontrar o MDC - por subtração e divisão. Na verdade, esses dois métodos de implementação do algoritmo são amplamente conhecidos hoje.

Aqui está um exemplo de uma função escrita em Swift que implementa o primeiro 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 // One of them is 0. } 

Aqui, para reutilização, por minha causa, trouxe uma função separada para os casos de pesquisa de GCD, quando é conhecido imediatamente, sem a necessidade de seguir qualquer algoritmo:

 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 } 

(Se dois números são iguais, então, naturalmente, seu GCD também é igual a eles. Se qualquer um dos números for zero, o GCD será igual ao segundo número, porque zero é divisível por qualquer número (com o resultado, é claro, também zero) .)

Somente valores não negativos podem ser usados ​​como entrada. Consequentemente, para o negativo, você pode usar os mesmos métodos, mas usando o módulo de números. (Sim, o fator comum também pode ser negativo, mas estamos procurando especificamente o GCD, e os números positivos são obviamente sempre mais do que negativos.)

E aqui pode parecer a implementação da versão do algoritmo por divisão:

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

A segunda versão hoje é considerada preferível, pois contém, em média, um número significativamente menor de etapas. No entanto, em um momento em que os computadores eram grandes e lentos, a operação de divisão poderia ser um procedimento complexo por si só. E então a primeira versão do algoritmo poderia ser mais eficaz.

Para compará-los um pouco, fiz várias medições usando meu método measure(_:) XCTestCase classe XCTestCase da estrutura "nativa" para testar código em XCTest XCTest Xcode .

Como entrada, usei uma matriz de pares de números aleatórios. As medições foram feitas, é claro, usando a mesma matriz para cada método. Eu levei o spread de números para pares de zero a 9999. As medições foram feitas no número de cálculos (pares de números): um, dez, 100, 1000, 10000, 100000, 1.000.000 e 10.000.000.Este último me fez esperar o resultado por vários minutos, então decidi. para parar

Aqui está um código simples de geração de entrada:

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

A medida em si é, por exemplo, assim:

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

E aqui estão os resultados do lançamento no meu computador:


(Subtração - subtração, divisão - divisão.)

Em geral, é bem visível quanto o método de subtração perde nos computadores modernos.

Versão "aprimorada" do algoritmo euclidiano

Na literatura, é possível encontrar uma versão do algoritmo em que um dos números em cada etapa, em vez do restante da divisão pelo segundo, é substituído pela diferença entre esse deslocamento e o segundo número, mas apenas se o restante da divisão for mais da metade do segundo número. Uma implementação desta versão pode ser assim:

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

Essa modificação reduz o número de etapas no algoritmo, mas, a julgar pelos resultados das medições no meu computador, cálculos e verificações adicionais em cada etapa neutralizam essa vantagem e ainda mais:


(Melhorado é a versão "aprimorada".)

Um pouco mais sobre a importância do algoritmo euclidiano

O algoritmo também possui uma versão geométrica (para encontrar a maior medida de dois segmentos).

O algoritmo foi, é claro, generalizado para encontrar GCD de qualquer número de números, não apenas dois. Em poucas palavras, a idéia é a seguinte: se designarmos a função de procurar o MDC de dois números como gcd (a, b), então, digamos, o MDC de três números gcd (a, b, c) seja igual a gcd (gcd (a, b), c). E assim por diante, para qualquer número de números, o GCD é encontrado calculando sequencialmente o GCD do GCD do par anterior de números e do próximo número. Embora, é claro, isso diga respeito à pesquisa de GCD em geral, e não apenas ao algoritmo euclidiano.

Há também uma generalização do algoritmo para encontrar polinômios GCD. Mas isso já está além do escopo deste post simples e, até certo ponto, do meu conhecimento de matemática.

Complexidade do algoritmo euclidiano

A complexidade temporal do algoritmo é investigada há muito tempo, não de forma rápida e por homens muito mais instruídos que seu humilde servo. No entanto, a pergunta está encerrada há muito tempo e uma resposta foi recebida. Na verdade, em meados do século antes do passado. Gabriel Lame .

Em suma, a resposta é formulada, de fato, pelo teorema de Lame relacionado a esse algoritmo. O número de etapas no algoritmo será igual ao número de seqüência do número Fibonacci maior mais próximo , o menor dos dois números de parâmetros de entrada menos 2. Usando uma notação matemática um pouco mais tradicional, se u> v (e v> 1), o número de passagens do algoritmo será n - 2 para v <Fn (Fn é o número mais próximo de v Fibonacci e n é o número de sequência).

Os números de Fibonacci crescem exponencialmente, respectivamente, temos uma função logarítmica do tempo de execução do algoritmo (a partir do menor dos dois números de entrada).

Os mesmos cálculos mostram que os piores dados de entrada para o algoritmo são dois números consecutivos de Fibonacci.

Método binário para encontrar NOD

Falando sobre a busca pelo GCD, vale a pena mencionar o algoritmo proposto já nos anos 60 do século passado por um certo Joseph Stein sobre o qual não encontrei nenhuma informação na Web. Ele (o algoritmo) é orientado à aritmética binária e não contém operações de divisão. O algoritmo opera apenas com verificações de paridade e metade, o que é possível apenas com os recursos da aritmética binária.

O algoritmo é baseado em quatro fatos:

1. Se u e v forem pares, então gcd (u, v) = 2 * gcd (u / 2, v / 2);
2. Se u é par e v não é, gcd (u, v) = gcd (u / 2, v);
3. gcd (u, v) = gcd (u - v, v) (segue o algoritmo euclidiano);
4. Se u e v são ímpares, u-v é par e | u-v | <máx (u, v)

Na Wikipedia você pode ver a versão recursiva do algoritmo (escrita em várias linhas nas linguagens de programação modernas), não a reescrevi no Swift. E aqui eu dou uma implementação 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 } 

Tendo feito as medições nos mesmos dados, infelizmente, esse algoritmo sofisticado no meu computador não atendeu às expectativas nele estabelecidas. Obviamente, ele ainda funciona duas vezes mais rápido que o algoritmo euclidiano por subtração, mas é notavelmente inferior à sua versão de divisão clássica. Tabela de resumo completa:


(Binário é um algoritmo binário.)

(Não excluo que o algoritmo possa ser escrito com mais eficiência do que eu, e isso afetará o resultado, mas para que precisamos então de compiladores?!

A propósito, esse algoritmo, que sem dúvida conquistou seus 15 minutos de fama já na era da tecnologia da informação (em uma parte anterior à atual), era conhecido na China antiga. Sua descrição é encontrada em obras que datam do século I. AD Claro, em termos como "meia divisão" e subtração. E também no contexto de redução de frações.

Conclusão

Honestamente, com essa simples "pesquisa" eu não ia provar nada e não queria tirar conclusões revolucionárias (e não o fiz!). Eu só queria satisfazer minha curiosidade, observar o trabalho de diferentes abordagens para resolver o problema clássico e esticar meus dedos um pouco. No entanto, espero que você também tenha curiosidade em observar os resultados!