O que um algoritmo de 300 a.C. tem a ver com boa programação?

Algoritmos em JavaScript e Python com a pura e antiga matemática.

Algoritmo bom é aquele que considera o tempo de processamento e memória utilizada. Se um problema tende a ter crescimento de complexidade exponencial, o código para resolvê-lo precisa ser elegante para obter sucesso mesmo com alta carga de processamento, é o que demonstro com a abordagem Euclidiana abaixo. É bom lembrar que o motivo do algoritmo existir é executar uma tarefa. Considerar seus recursos é uma prática excelente e sempre bem vinda.

Fato é que a programação é extremamente poderosa, mesmo que você não saiba como resolver um problema, muito provavelmente ele ainda pode ser resolvido computacionalmente. Algoritmos de força bruta são muito utilizados, são martelos gigantes que resolvem a maioria dos problemas e, assim como várias outras coisas na computação, se apoiam na lei de Moore e efetivamente encontram o resultado esperado. Porém, frequentemente não são os mais eficientes no sentido de reduzir custo computacional, que pode ser medido por quão rápido um programa executa ("complexidade de tempo") ou quanto de memória é necessário ("complexidade de espaço").

O problema

O Mínimo Múltiplo Comum é um problema matemático maravilhoso para resolvermos com o poder da programação. Muitos de nós lembramos de resolver MMCs e MDCs com lápis e papel. O problema é escrever um programa que retorne o mínimo multiplicador comum de um conjunto de números inteiros composto pelo maior e menor número e todos os números inteiros entre eles. Ou seja f_mmc(1,4) retorna o mmc de [1,2,3,4]. Como objetos de controle que podem ser verificados aqui, o MMC esperado do conjunto [18,19,20,21,22,23] é 6056820, e do conjunto [15,16,18,19,20,21,22,23] é 411863760.

Força Bruta:

JavaScript - bad algorithm:

const {performance} = require('perf_hooks'); //Para contar o tempo var iter; // Contador de iterações. function f_mmc(x,y){ // Classifica x e y e encontra o menor e o maior let arr = [x,y]; arr.sort( (a,b)=>{return a>b}); // Cria 'arre' uma lista com todos os números inteiros entre X e Y inclusive. let arre = []; for(let i=arr[0];i<=arr[1];i++){ arre.push(i); } console.log('O MMC do conjunto: [' + arre + '] é:'); // Define (pior) como o produto de todos elementos do array let pior = arre.reduce( (a,b)=>{return a*b}); /** Verifica se o J q é múltiplo do maior elemento do conjunto é também múltiplo de todos os outros inteiros do conjunto, caso negativo J é incrementado pelo maior elemento do conjunto, se positivo J é o mínimo multiplicador comum. */ let v_lcm = false; iter = 0; for(let j=arre[arre.length-1];j<=pior;j+=arre[arre.length-1]){ let v_lcm = true; iter++; for(let e in arre){ iter++; if(j%arre[e]!==0){ v_lcm = false } } if(v_lcm==true){ return j; } } } // Marca início da execução var t0 = performance.now(); console.log(f_mmc(23,18)); // Marca final da execução var t1 = performance.now(); console.log("A execução de 'f_mmc' durou " + (t1 - t0) + " milissegundos."); console.log("A execução de 'f_mmc' teve " + iter + " iterações.");

O tempo de execução pode alterar de acordo com o ambiente onde o código será executado. De toda forma, o número de iterações contabilizadas nos loops mais ativos indica o custo computacional para alcançar o resultado. No meu caso, 770 milissegundos para 1843380 iterações, pode parecer um esforço quase imperceptível mas esconde um perigo escalonável. Para retornar o MMC do conjunto [15,16,17,18,19,20,21,22,23] seriam necessárias mais de 179 milhões de iterações e aproximadamente 1 minuto de execução até o retorno com esse bad algorithm.

A elegância Euclidiana:

Para este problema proposto, a elegância Euclidiana está em entender relações como: subtrair os restos entre dois inteiros para encontrar o MDC, utilizar o MDC para encontrar o MMC e a clássica recursividade.

JavaScript - good algorithm

const {performance} = require('perf_hooks'); //Para registro do tempo var iter=0; // Contador de iterações. // Função recursiva q retorna o MDC de dois inteiros. function mdc(a,b){ iter++; if (b == 0){ return a; }else{ return mdc(b , a % b); } } // Função q utiliza o MDC para retornar o MMC de dois números inteiros. function mmc(a,b){ iter++; return ((a * b) / mdc(a,b)); } // Função com método recursivo que retorna o MMC de um conjunto de inteiros. function f_euclides_mmc(a,b){ // Ordena e cria (arre) com o conjunto de inteiros let arr = [a,b].sort( (a,b)=> a > b); let arre = []; for(let i=arr[0];i<=arr[1];i++){ arre.push(i); } console.log('O MMC do conjunto: [' + arre + '] é:'); // Função recursiva para retorno do MMC // Dado que mmc(a,b,c) = mmc(mmc(a,b)c) function f_mmc(cnj){ iter++; if (cnj.length == 2){ return mmc(cnj[0],cnj[1]); }else{ ar = [mmc(cnj[0],cnj[1]),...cnj.slice(2)]; return f_mmc(ar); } } return f_mmc(arre); } var t0 = performance.now(); console.log(f_euclides_mmc(23, 15)); var t1 = performance.now(); console.log('A execução de f_euclides_mmc durou '+ (t1-t0) + ' milissegundos.'); console.log("A execução de 'f_euclides_mmc' teve " + iter+ " iterações.");

Escrevi em Python esses mesmos algoritmos e eles podem ser editados e executados direto do navegador nesse notebook aqui.

Clique em 'Run' para executar ambos os códigos e verificar os resultados. Observe que mesmo utilizando um exemplo com maior carga, a função com a matemática Euclidiana se mostra excepcionalmente mais eficiente, apenas 49 iterações para retornar corretamente o MMC de [15,16,17,18,19,20,21,22,23]: 411863760 em aproximadamente 3 milissegundos.

O importante aqui não é decorar determinado algorítimo ou competir por milésimos de segundo de execução, mas entender que existem milhares de abordagens para resolver qualquer problema. A abordagem Euclidiana pode nem mesmo ser o método mais eficiente para o problema aqui proposto, mas ela considera o custo computacional. Encontrar abordagens elegantes depende de um olhar minucioso sobre as relações matemáticas existentes congruentes com o problema. Não se engane, no fundo toda programação é matemática.

Plante uma árvore!