thegoodfellas/blogset-br huggingface dataset:
Um tempo atras o Karlisson teve uma ideia muito boa: criar uma coletanea com os 1001 algoritmos que voce deve implementar antes de morrer. O objetivo e fazer uma implementacao de referencia, em python, para todos os algoritmos classicos, desde os simples como o Bubblesort ate os complexos como o Edmonds-Karp.Se voce tambem quiser participar, e so fazer um fork do repositorio no github. E um otimo exercicio para quem e iniciante, e para os veteranos e uma boa oportunidade de praticar o habito de fazer code reviews. Ja que no post anterior eu falava de parabolas, vamos aproveitar pra revisar um dos codigos do projeto: uma funcao que acha as raizes reais da equacao de segundo grau:def bhaskara(a, b, c): delta = b ** 2 - 4 * a * c if delta < 0: return None else: raizes = [] m1 = math.sqrt(delta) r1 =(-b + m1) / (2 * a) raizes.append(r1) r2 =(-b - m1) / (2 * a) raizes.append(r2) return raizesA funcao e uma implementacao direta da formula:Conferindo com a formula, o codigo parece correto. Porem, olhando com cuidado, ele tem tres problemas!Primeiro problema: API inconsistenteO problema mais imediato do codigo e que ele faz uma divisao por zero quando a e igual a zero. Mas isso e um bug de verdade? A intencao do codigo era resolver equacoes do segundo grau, mas, se a e nulo, entao a equacao nao e de segundo grau, e de primeiro!Eu interpreto isso como um problema na API. Se a ideia do codigo e resolver somente equacoes de grau 2, entao, antes de sair fazendo conta, ele deveria verificar se as entradas sao validas (ou seja, se a e nao-nulo). Por outro lado, se a intencao e resolver equacoes de grau 2 ou inferior, entao ele poderia retornar [-c/b] quando a for zero. Nos dois casos, faltou sinalizar exatamente qual o proposito da API.A API ainda tem uma segunda falha, que e o valor de retorno. O que exatamente ele vai retornar? Eu poderia, por exemplo, dizer que a funcao sempre retorna uma lista com as solucoes existentes. Nesse caso, quando o delta e negativo, o correto seria retornar uma lista vazia, ao inves de retornar None.Alem disso, o que devemos retornar quando o delta e exatamente zero? As duas possibilidades sao retornar uma lista com uma unica raiz, [-b/2a], ou entao retornar uma lista com duas raizes iguais, ou seja, [-b/2a,-b/2a]. Qual resposta faz mais sentido?A escolha correta vem do Teorema Fundamental da Algebra, que diz que o numero de raizes complexas de uma equacao polinomial e igual ao grau da equacao. O motivo de considerarmos que algumas equacoes tem multiplas raizes iguais e pra fazer esse teorema ser valido em todas as situacoes.Mas o teorema so vale para raizes complexas! Como estamos trabalhando com raizes reais, entao eu acho que o mais correto e retornar uma lista com um unico elemento mesmo.Voce tambem poderia argumentar que o nome da funcao nao e apropriado, porque esta descrevendo a implementacao (formula de Bhaskara) ao inves de descrever a interface (solucao da
equacao quadratica). Mas ai nos chegamos no segundo problema...Segundo problema: Bhaskara quem?Certamente voce ouviu na escola que a solucao da equacao quadratica chama-se formula de Bhaskara. Mas, curiosamente, e so no Brasil que a formula tem esse nome!Pode conferir: a wikipedia em ingles nem cita o Bhaskara. Talvez na wikipedia em hindi? Nada de Bhaskara la tambem, na India eles chamam a equacao de formula de Sridhar Acharya. Nos outros paises a formula nem tem nome, e simplesmente "equacao quadratica" ou "formula a-b-c".Na verdade, os babilonicos ja sabiam resolver alguns tipos de equacoes quadraticas ha pelo menos 4000 anos. Os gregos conheciam solucoes geometricas. E a formula em si, e do Bhaskara mesmo?Bem, uma maneira de resolver a duvida e procurando exatamente o que ele escreveu. O texto mais importante do Bhaskara foi o livro que dedicou a filha, Lilavati. O original era em sanscrito, mas tem uma traducao em ingles online para quem quiser ler. Eu procurei pela solucao da quadratica, e o mais proximo que achei foi a proposicao 63:Uma quantidade, incrementada ou decrementada de sua raiz quadrada multiplicada por algum numero, e dada. Entao adicione o quadrado de metade do multiplicador da raiz ao numero dado, e extraia a raiz quadrada da soma. Adicione metade do multiplicador, se a diferenca foi dada; ou subtraia, se a soma for dada. O quadrado do resultado e a quantidade procurada.Em notacao moderna, o que o Bhaskara escreveu foi:Eu nao acho que seja correto creditar ao Bhaskara a solucao da equacao quadratica. A formula acima e bem parecida com a que usamos, mas note o detalhe: ela so fornece uma raiz! Para considerar a solucao como correta, eu acho que ele deveria ter explicitado que algumas equacoes vao ter duas raizes.Pois bem, podemos entao mudar o nome da funcao, de bhaskara() para algo mais apropriado, como quadratic_roots(). Mas ainda resta o ultimo problema...Terceiro problema: Instabilidade numericaVamos testar o codigo original com a seguinte equacao: x2-2000000000x+4=0. As raizes sao aproxidamadamente 2e9 e 2e-9. Porem, olhe so o resultado:>>> bhaskara.bhaskara(1, -2e9, 4)[2000000000.0, 0.0]Como assim zero? Cade a solucao 2e-9? Essa raiz foi vitima de um problema que nem todo mundo presta atencao: muito cuidado com a perda de precisao em ponto flutuante. Em especial, quando voce subtrai dois numeros de magnitude similar, a resposta pode nao ter precisao suficiente para dar o resultado correto. Para a equacao dada, o codigo original tem os valores b e m1 muito proximos, e a subtracao perde a menor raiz.A solucao e evitar a subtracao. Voce inspeciona o sinal de b, e escolhe m1 com o mesmo sinal, de modo que os modulos sao sempre somados, achando assim a primeira raiz x1. Tendo x1, voce pode achar x2 usando a formula de Viete para o produto de raizes:Dessa maneira a subtracao problematica some, e chegamos na versao final do programa corrigido:def quadratic_roots(a, b, c): """Find all real roots of a quadratic equation. Args: a, b, c: Coefficients of the quadratic, a*x*x+b*x+c=0 Returns: A list with all real roots. Raises: ValueError if a==0 (the equation is not quadratic). """ if
not a: raise ValueError delta = b * b - 4 * a * c if delta < 0: return [] if not delta: return [-b / (2 * a)] if b < 0: x1 = (-b + delta ** 0.5) / (2 * a) else: x1 = (-b - delta ** 0.5) / (2 * a) x2 = c / (a * x1) return [x1, x2]Conferindo:>>> roots.quadratic_roots(1, -2e9, 4)[2000000000.0, 2.0000000000000001e-09]Nice!Voce pode se perguntar se esse exemplo que eu dei nao e artificial demais, e se coisas assim acontecem na pratica. Mas acontecem sim! Um exemplo comum onde esse erro acontece e na implementacao da busca binaria.Por exemplo, suponha que voce quer resolver a equacao ln(x)+sqrt(x)=5. A funcao ln() e monotonica, o sqrt() tambem, entao da pra achar a raiz por busca binaria:def search(epsilon): inf, sup = 0.0, 1e10 while sup - inf > epsilon: med = (sup + inf) / 2 x = math.log(med) + math.sqrt(med) if x > 5.0: sup = med else: inf = med return infVamos testar essa rotina para varias precisoes:>>> binary.search(1e-4)8.3093709690729156>>> binary.search(1e-10)8.3094326941933723>>> binary.search(1e-15)Oops! Quando epsilon vale 1e-15, a rotina trava! De novo, o problema e perda de precisao. Nesse caso, as variaveis sup e inf tem valores muito proximos, entao a media med nao sai do lugar, ficando presa no valor do inf para sempre.A solucao, novamente, e sumir com a subtracao. Ao inves de controlar os extremos do intervalo, voce usa uma variavel para o valor inicial e outra para o tamanho do intervalo:def smart_search(epsilon): inf, delta = 0.0, 1e10 while delta > epsilon: delta /= 2 med = inf + delta x = math.log(med) + math.sqrt(med) if x < 5.0: inf += delta return infConferindo:>>> binary.smart_search(1e-4)8.3093709690729156>>> binary.smart_search(1e-10)8.309432694193374>>> binary.smart_search(1e-15)8.3094326942315693>>> binary.smart_search(1e-30)8.3094326942315693Agora sim!No fim das contas, e importante voce ter a matematica sempre afiada, mas tambem e igualmente importante conhecer os limites impostos pela computacao do mundo real.(Agradecimentos ao Karlisson, ao Henrique, ao Wladimir, ao Chester e ao povo da lista eng-misc pela ajuda na pesquisa!)
No ultimo post eu falava de variacoes em jogos, ai lembrei de uma variacao divertida em um jogo bem conhecido. Quem assistia Topa Tudo Por Dinheiro certamente deve se lembrar do Jogo do Pim. O objetivo e enumerar os naturais pelo maior tempo possivel, trocando os multiplos de quatro pela palavra "pim":1,2,3,pim, 5,6,7,pim, 9,10,11,pim...Parece simples, mas na pratica muita gente se confundia e errava antes mesmo de chegar ao quarenta!Uma variacao mais dificil desse jogo foi inventada pelo Juca uns anos atras: o Jogo do Pi. Dessa vez voce ainda precisa enumerar os naturais, mas precisa falar "" toda vez que passar um multiplo inteiro de pi. Os primeiros multiplos inteiros sao aproximadamente 3.14, 6.28 e 9.42, entao a sequencia comeca assim:1,2,3,, 4,5,6,, 7,8,9,...Parece o mesmo jogo ne? Voce conta tres numeros, fala , conta mais tres, fala , e assim por diante. Mas se voce seguir essa estrategia, vai perder! Olha o que acontece se voce continuar:..., 16,17,18,, 19,20,21,, 22,23,24,25,,...A estrategia de contar de tres em tres falha! Entre 7 e 8 tem quatro naturais ao inves de so tres.Bem, sera que nao da pra melhorar a estrategia? Podemos contar quantos numeros tem entre os multiplos de pi. Com sorte, o padrao e 33333334 e depois repete. Nesse caso, o padrao do Jogo do Pi e oito vezes maior que o padrao do Jogo do Pim. Infelizmente, se voce fizer as contas, esse padrao tambem e quebrado apos 112.Sera que devemos procurar um padrao de padroes entao? Nessa altura nao ja compensa fazer as contas na mao, melhor deixar o python achar o periodo pra gente:Script em python para tentar achar um periodoMas noticias: o script acha padroes maiores e maiores, sem parar. Nao tem como concluir se existe ou nao um padrao so analisando a saida do programinha.O jeito de resolver essa duvida, entao, e usando matematica! Se voce tem medo de teoria dos numeros, pule o quadro azul:Antes de mais nada, vamos colocar nosso problema na notacao correta. Nos queremos descobrir se a quantidade de numeros entre multiplos inteiros consecutivos de pi formam uma sequencia periodica. Vamos primeiro escrever a sequencia explicitamente:Isso gera a sequencia que queremos. Agora vamos supor que essa sequencia tem um periodo p. Das duas uma: ou a gente acha o valor de p, ou batemos em uma contradicao pelo caminho.Se nos somarmos todos os primeiros n termos dessa sequencia, temos uma soma telescopica e um resultado curto:Isso vale para todo n, inclusive no caso onde n e um multiplo inteiro do periodo p:Mas, nesse caso, podemos fazer a somatoria de outro jeito. Ao inves de somar direto de 0 a kp, podemos somar k vezes o periodo p. Ai, como a sequencia e periodica, um dos termos some:O termo mais interno da somatoria nao varia mais com i, entao essa somatoria esta somando k vezes a mesma coisa:A conclusao e que, quando p e o periodo da sequencia, podemos jogar um k inteiro de dentro para fora do piso. Podemos agora abrir a definicao de piso para kp:Dividindo todo mundo por kp, temos:Agora, para
todo real > 0, podemos escolher um k grande o suficiente tal que seja maior que 1/kp. Logo:Pelo teorema do sanduiche, concluimos que:Note que o numerador dessa funcao e um piso, logo e um inteiro. Sabemos tambem que p e um inteiro, logo a fracao e um racional. Mas pi e irracional, portanto chegamos a uma contradicao, e a sequencia nao tem periodo.Ou seja, concluimos matematicamente que o Jogo do Pi nao tem periodo. Outra maneira de dizer a mesma coisa e que o periodo do Jogo do Pi e infinito, e portanto o Jogo do Pi e infinitamente mais dificil que o Jogo do Pim!Agradecimentos ao povo do Math Stack Exchange pela ajuda na demonstracao
Essa e uma pergunta classica em entrevistas: qual foi o bug mais dificil que voce ja consertou? No meu caso, o bug mais dificil que resolvi deu um trabalhao para encontrar, e por um motivo bastante curioso: o bug nao era no programa, mas sim na pecinha entre a cadeira e o teclado!A historiaEssa historia se passa em agosto de 1998. Nessa epoca, eu estava escrevendo um emulador de MSX, e tomando dois cuidados na implementacao: o emulador tinha que ser rapido o suficiente para rodar em full speed nas maquinas da epoca, e tinha que ser preciso o suficiente para ser indistinguivel de um MSX real.O primeiro objetivo eu atingi escrevendo o emulador inteiramente em Assembly, o segundo atraves de uma metodologia de testes solida. Na epoca eu ainda nao fazia unit testing, mas, para cada feature adicionada, eu sempre fazia um programa de teste e comparava a execucao dele no emulador e na maquina real.As primeiras versoes do emulador eram mudas, eu emulava so a CPU e o chip de video. Quando esses dois ficaram estaveis, eu comecei a escrever a emulacao do chip de audio: o AY-3-8912 da General Instrument, tambem conhecido como PSG. Esse chip tinha capacidade de produzir tres canais de som e um canal de ruido, sendo que o ruido era usado para fazer efeitos sonoros (como tiros e explosoes), e tambem para fazer sons de percursao (como baterias).Para testar se a minha implementacao do canal de ruido estava boa, eu fiz o seguinte programinha em MSX BASIC:10 SOUND 7,18320 SOUND 8,1530 FOR I=8 TO 1 STEP -140 SOUND 6,I50 PRINT I60 FOR J=0 TO 300: NEXT J,I70 BEEPOs numeros magicos no codigo assustam, mas o funcionamento e simples: o registro 7 e o mixer, com o valor de 183 eu ligo o gerador de ruido no canal A e desligo todo o resto. O registro 8 e o volume do canal A, que eu setei para 15, ou seja, volume maximo. Por fim, eu faco um loop alterando o valor do registro 6, que e a frequencia do ruido.Portanto, o que se espera desse programinha e que ele toque um barulhinho de volume constante, comecando grave e ficando cada vez mais agudo. Isso na teoria. Na pratica, aconteceu outra coisa!O bugEu resolvi repetir o experimento da epoca e filmar. No video abaixo voce pode ouvir esse programinha rodando em um MSX real, e depois rodando no meu emulador (eu usei o dosbox para compilar a versao de 1998, antes do bug ser corrigido):Olha que curioso, embora eu tenha programado o volume para ficar constante, no MSX real o volume abaixa sensivelmente no final. E pior, no emulador isso nao acontece!A diferenca e sutil, sera que eu estava viajando? Um jeito de confirmar e capturando os dois sinais e jogando no Octave para comparar (quer dizer, na epoca ainda nao tinha o Octave, entao eu usava o Matlab mesmo):De olho parece realmente que o turboR vai diminuindo, mas e dificil comparar. Um jeito mais eficiente e notando que a grandeza que perceptualmente nos sentimos como volume,
fisicamente e causada pela potencia do sinal. E potencia a gente sabe calcular, e a integral do quadrado da forma de onda. Jogando isso no Octave:Olha la! Nao era viagem nao, nos dois ultimos passos realmente o volume do turboR fica menor que o do emulador! Mas por que isso acontece? Talvez eu tivesse alguma pista analisando o hardware com cuidado.O circuitoPara entender o funcionamento do PSG, nao adianta usar o esquematico do MSX e nem pegar o datasheet do AY-3-8912, porque nenhum dos dois explica o que acontece dentro do chip. Em teoria daria para abrir o chip e tentar ler a pastilha com um microscopio eletronico, mas como eu nao tinha acesso a um, o jeito foi apelar para engenharia reversa mesmo.Os canais de som do PSG foram faceis de modelar. Ele tem tres geradores de onda quadrada, e cada um funciona da seguinte forma:O clock de entrada do contador e o clock do MSX dividido por 16, ou seja, 223506Hz. A cada pulso, o contador incrementa de um, e o resultado e comparado com o valor do registro que determina a frequencia. Quando o valor e igual, o contador reseta e um flip-flop tipo T inverte de estado, gerando assim a onda quadrada desejada.Mas e o gerador de ruido? Na epoca ninguem sabia como funcionava, uns chutavam que era ruido termico de resistor, outros que era shot noise na juncao de algum semicondutor.Mas a verdade era muito mais simples, o PSG tinha um gerador pseudo-aleatorio! Para ser mais exato, tinha um gerador de onda quadrada igual ao descrito acima, e a cada transicao na saida ele fazia uma iteracao em um Linear Feedback Shift Register.Nos sabemos que todo LFSR gera um sinal periodico, entao, capturando um periodo inteiro do gerador, da para deduzir qual e o polinomio caracteristico dele. Fazendo o experimento, o polinomio era o maximal de tamanho 17, ou seja, x17+x14+1.Eu conhecia a forma de onda gerada, e conhecia ate o exato LFSR que era usado. Ainda assim, isso nao explicava por que o volume abaixava. Sera que eu tinha implementado errado?A implementacaoUm dos meus requisitos era rodar o emulador a toda velocidade nas maquinas da epoca. Em 1998, isso significava emular esse circuito inteiro em um Pentium 1, e ainda sobrar tempo para emular a CPU e o VDP. A coisa era tao apertada que simplesmente escrever em Assembly nao era suficiente, eu tinha que garantir que o inner loop rodasse inteiramente em registros.O problema e que os meros 7 registros de uso geral do x86 nao eram suficientes. Minha primeira solucao foi apelar feio: durante a emulacao do PSG, eu desligava as interrupcoes e usava o stack pointer como registro! Na minha casa isso funcionava bem, mas em casa eu usava DOS. A maioria dos meus usuarios a epoca usava Windows 95, e ai essa abordagem de mexer no esp fazia a maquina travar.Vamos para a solucao dois entao. Tinha um monte de variaveis que mudavam a cada nota tocada pelo PSG, mas eram constantes durante o inner loop. Sendo assim, era uma boa oportunidade
para usar codigo auto-modificavel: eu "recompilava" o inner loop cada vez que alguem mudasse um registro do PSG. Essa solucao funcionava ate no Windows e era rapida o suficiente.Porem, ela era rapida, mas bastante complexa. Voce pode ver esse codigo no github, nao e a coisa mais legivel do mundo, nem a mais facil de entender. Entao, seria de se esperar que o volume nao estivesse abaixando por conta de algum erro de implementacao.Mas apos pensar um pouco, eu conclui que a minha implementacao deveria estar correta. Se ela estivesse errada, entao esse erro deveria aparecer so no meu emulador. Mas na epoca exisitiam outros emuladores, e em todos os outros esse mesmo problema aparecia.Se varias implementacoes diferentes tinham o mesmo problema, entao o erro nao era no codigo, tinha que ser conceitual. E se e conceitual, entao talvez eu conseguisse alguma pista analisando matematicamente o sinal.A transformadaHora de fazer a modelagem do sinal entao! Vamos considerar que os bits de saida do LFSR formam uma sequencia discreta {di}, e que a cada bit 1 na entrada nos mandamos para saida uma forma de onda s(t). Dessa maneira, se a largura do pulso for T, entao o ruido do PSG pode ser computado como:Da teoria de processos estocasticos, nos sabemos que a densidade espectral de potencia do sinal, nesse caso, vale:...onde Gd(f) e a densidade espectral de potencia da sequencia {di}, e S(f) e a transformada de Fourier de s(t). Se admitirmos que o ruido em questao seja ruido branco, entao o Gd(f) e uma constante. Ja a forma de onda s(t) e um pulso retangular, cuja transformada e a funcao sinc. Portanto, a d.e.p. do sinal tem a forma de um sinc ao quadrado. O caso que da problema no emulador e quando o registro 6 vale 1, ou seja, quando T=8.98s. Assim, a densidade espectral de potencia da saida e a abaixo:Novamente, aquilo que perceptualmente nos percebemos como volume e a potencia do sinal, e, pelo teorema de Parseval, a potencia e a area abaixo do grafico acima.Depois de olhar um tempo para esse grafico, finalmente caiu a ficha!A solucaoNo fim, o problema todo estava entre a cadeira e o teclado! Mais especificamente, no fato de que tinha um ser humano entre a cadeira e o teclado! O sistema auditivo humano so consegue ouvir frequencias ate 20kHz, e esse sinal estava espalhando potencia para faixas inaudiveis! De fato, um humano so consegue perceber como volume essa parcela da potencia:A integral do sinc ao quadrado nao da para resolver analiticamente, mas da para calcular numericamente. Eu posso, por exemplo, fazer uma tabela com a potencia audivel dividida pela potencia total, para cada um dos valores de frequencia que eu usei no programinha em BASIC:Registro 6Porcentagem da potencia audivel80.9970.9960.9950.9940.9930.9620.8310.50Se voce comparar com o grafico de potencia do emulador versus turboR, da pra notar que a porcentagem acima e exatamente o que falta para tornar a volume do emulador igual a maquina real! Adicionando essa atenuacao no emulador, ele finalmente ficou fiel ao original como eu queria.Leitores que estejam prestando atencao, a essa
altura devem estar se perguntando: "Mas perai, se o problema e puramente sensorial, entao porque o grafico de potencia medido no Octave mostra a perda de volume?". A resposta e que isso tambem e um artefato do sistema auditivo humano, mas indiretamente.Quando eu pluguei o turboR na entrada de microfone do meu notebook, a placa de som fez a captura do audio em qualidade de CD, ou seja, com amostragem de 44100Hz. E os projetistas da placa de som sao espertos, eles sabem que antes de amostrar voce precisa passar o sinal em um filtro passa-baixas com corte na frequencia de Nyquist, para evitar o aliasing. E essa frequencia foi calculada exatamente para jogar fora o que os humanos nao ouvem, gerando o mesmo problema.Se voce quiser refazer o experimento, coloquei no github os scripts em Octave que usei para gerar as imagens e tabelas do post:Scripts em Octave para analise de ruidoPor fim, esse bug deu um trabalhao para resolver, e no final desconfio que a diferenca era tao sutil que ninguem alem de mim notou a diferenca :)