sexta-feira, setembro 28, 2007

Será que o Excel 2007 Desaprendeu a Aritmética?

Esta semana foi descoberto um problema vexatório no Excel 2007, que apresenta um resultado completamente errado para uma conta simples. Esta descoberta tem gerado manchetes do tipo "Excel 2007 não sabe multiplicar", mas o que realmente se passa?

O Bug

O exemplo mais comum do problema consiste em entrar em um célula com a expressão "=77,1*850" (quem estiver com o Windows configurado para o padrão americano deve entrar com '.' no lugar da ','). O resultado apresentado é 100.000 ao invés do valor correto 65.535.

Como Isto Ocorre?

Da mesma forma que a maioria das planilhas e aplicativos que manipulam números, o Excel trabalha internamente com os números em um formato padronizado, o IEEE 754. Este formato é o mais comumente usado e é suportado diretamente pelos processadores atualmente em uso nos PCs.

Este formato é do tipo ponto flutuante, no qual o número é armazenado em duas partes: a mantissa (que é o número em si) e o expoente (que indica onde está a separação entre a parte inteira e fracionária). Uma das vantagens deste formato é suportar uma faixa grande de números em uma capacidade baixa de armazenamento. Por exemplo, vamos supor que vamos armazenar números decimais em três dígitos. Se usarmos um ponto fixo após o primeiro dígito, podemos trabalhar com números entre 0,00 e 9,99. Se considerarmos os dois primeiros dígitos são a mantissa e o terceiro é o expoente, podemos trabalhar com números entre 0,00 e 990.000.000. Uma desvantagem óbvia é que quando somamos números muito diferentes perdemos precisão.

Um outro ponto importante é que neste tipo de notação podemos armazenar somente um subconjunto dos números reais. No meu exemplo podemos armazenar 0,01 e 0,02 mas nenhum dos infinitos números entre eles.

Para complicar o entendimento, na notação IEEE 754 trabalhamos com potências de 2 e portanto temos um 'ponto binário' ao invés de 'ponto decimal'. Como consequência números 'triviais' na notação decimal não podem ser representados na notação binária e vice versa.

O que tem isto a ver com o bug? A primeira coisa é que 77,1 não possui representação exata no formato IEEE 754. Ao multiplicar este valor por 850 obtemos um valor que não é exatamente igual a 65.535 (mas extremamente próximo).

Ao contrário do indicado pelas manchetes, o Excel faz a conta direitinho (quem faz a conta é a CPU não o Excel). Aonde ele 'se borra' é na hora de apresentar o resultado na tela. Ou seja, ao converter a representação binária do resultado para caracteres.

É Grave?

Segundo a Microsoft, o erro na apresentação ocorre somente para 12 combinações das quase 10^19 possíveis. É claro que as operações que levam a estas combinações são também quase infinitas e independem dos números e operações envolvidos. Considerando o tempo que o Excel está no mercado, dá para ver como os casos reais são raros.

Como o erro está na apresentação e não no cálculo, se o valor for usado em outros cálculos o resultado final provavelmente vai ser apresentado corretamente. Quando a Microsoft liberar uma correção, bastará carregar a planilha para o resultado correto ser apresentado, não existe nada a corrigir na planilha em si.

Portanto o problema é mais grave para a imagem da Microsoft que para os seus clientes.

Mas Como Saiu Com Este Bug?

A pergunta chave é: como testar para pegar um bug destes?

Uma vez que o erro está na apresentação, testes automatizados que verifiquem o resultado em si e não o valor apresentado na tela não vão pegar o erro.

O lugar mais provável seria no teste unitário da rotina que converte o número da representação interna para o string apresentado. Considerando a quantidade quase infinita de casos a testar e o minúsculo número de casos problemáticos, fica fácil perceber que é difícil um teste não dirigido pegar este problema. As informações disponíveis são insuficientes para saber se o problema acontece em algum caso limite, por exemplo onde o algorítimo precisa escolher entre dois caminhos ou onde alguma variável pode sofrer overflow ou underflow. Em caso afirmativo, provavelmente faltou um caso de teste que verificasse o funcionamente correto nos dois lados do limite.

Referências

Fiquei sabendo do problema no Joel On Software. Joel que, não por acaso, foi gerente de projeto do Excel (no milênio passado).

A descrição do problema pelos projetistas do Excel pode ser vista aqui.

segunda-feira, setembro 17, 2007

PC Assembler: A Odisséia

Como comentei no post anterior, ao escrever o post sobre a minha nova impressora eu tive a idéia de postar o texto do livro PC Assembler. Parecia fácil, mas foi uma verdadeira odisséia!

Procurando a Midia

Eu estava certo de ter uma cópia no HD. Não achei. Bem, com certeza está um dos muitos CDs de backup. Também não. Nos disquetes? Nada.

Hora de enfrentar o pó da última gaveta do armário de roupas, onde escondi algumas lembranças para escapar do lixo. E achei o disco aí ao lado. Alguns vão reconhecer que é um disquete de 5 1/4", mas poucos vão perceber que tem o corte de desproteção contra gravação nos dois lados. Para quem não entende de arqueologia, este é um disquete de Apple ][.
Parenteses: o mundo em geral pode idolatrar o Steve Jobs mas para os engenheiros Steve Wozniac é o cara. Uma das suas maiores criações foi a interface de disco do Apple ][, que permitiu a comercialização da unidade de disco por um preço extremamente baixo para a época (mesmo com a margem imensa colocada pelo Jobs). Embora a unidade seja para disquetes de face simples, o fato dela não usar o furo de índice (o furo pequeno redondo à direita do centro), permitia usar o segundo lado fazendo o corte na lateral e colocando o disco de ponta cabeça.

O Micro

Na época que eu escrevi o livro, meu computador principal era um Unitron apII TI. Alguns anos depois, evoluí para um TK3000//e da Microdigital que corresponde ao Apple //e. Foi este segundo equipamento que fui buscar na casa do meu pai para ler o disquete. Na foto ao lado, ele já foi devidamente limpo (?).

Uma das várias idéias que o Apple ][ popularizou (e a IBM seguiu) foi o uso de slots para placas de expansão. Como pode ser visto na foto ao lado, o meu micro tem uma quantidade grande de placas.

Separada das demais, na esquerda, está a placa "80 colunas" (o default do Apple ][ é apresentar na tela 40 caracteres por linha). No slot 1 a interface para impressora paralela. No slot 4 um clone do Softcard Z80, um dos primeiros hardwares de sucesso da Microsoft (essencial pois o disco está em formato CPM/80). No slot 6 a mencionada interface de disco, Por último, no slot 7, a minha expansão de memória de 128 KBytes (uma extravagância, que eu usava como RamDisk).

Para completar, o meu primeiro monitor: uma TV muito mal adaptada (fiz a adaptação de forma provisória quando cheguei em casa com o Unitron, funcionou e ficou deste jeito até hoje). No lado direito, duas unidades de disco.

Hora de cruzar os dedos, colocar um disco de CP/M e ver o que acontece. Ao lado está o resultado, aquele "A>" lembra alguma coisa?

Exceto por um monte de maus contatos (principalmente no teclado), está tudo funcionando!

Obs.: Para o caso de alguém estar prestando a atenção, a tela está com 40 colunas, devido a um mau-contato na placa "80 colunas". Neste momento a placa Z80 estava no slot 3 (esquecimento meu). Quando a placa "80 colunas" passou a funcionar a Z80 parou. Perdi pelo menos uma hora, até lembrar que a placa Z80 devia ir no slot 4 para não conflitar com a "80 colunas".

Recuperando os Dados

Ok, eu consigo ler os disquetes antigos, e agora? É hora de transferir os dados pela serial. A placa ao lado é uma ICA (Interface de Comunicação Assíncrona), lembrança dos tempos da Humana Informática e dos posts nas BBSs, comunicando a 300 bps ou nos esquisitos 1200/75 bps.

Com a placa no slot 2, é hora de usar o meu programa de comunicação (reparar no copyright na tela ao lado). O programa trabalha no capenga Xmodem Checksum, o que exige um pouco de esforço do Hyperterminal (que insiste em tentar primeiro o Xmodem CRC e só passa para o Checksum depois de um l_o_n_g_o tempo). Após alguns arquivos a paciência acabou e preferí alterar um dos meus inúmeros utilitários de PC para suportar o Xmodem Checksum.

Mas, Espere: Isto Não É Tudo!

Ao final tenho 20 arquivo recebidos no PC (como no CP/M são apenas 56K de Ram, o texto era quebrada em pedaços de no máximo 20K para evitar que o editor ficasse acessando o disco o tempo todo). A tela ao lado mostra (em hexa) o início de um deles (clique para ampliar). Que codificação é essa? Os textos foram gerados com o WordStar, que era um editor WYSIWYG... se você está escrevendo em inglês numa impressora não gráfica. À medida que o texto é editado, o WordStar automaticamente distribui espaços para justificar o texto dentro das margens. Para isto ele usa o bit 7 dos caracteres para marcar o final das palavras e os espaços, hifens e quebras de linha introduzidos. O que realmente estraga tudo é que para gerar as acentuações eu digitava sequências "caracter backspace acento" (felizmente tanto o Unitron como o TK3000 tinham teclados programáveis, o que me permitia digitar estas sequências de uma forma mais automática).

Reparar também no ".he xxxx". A formatação para impressora era um passo separado, as linhas começando com '.' são comandos para definir cabeçalho, rodapé, pular página, etc. Para conseguir obter um TXT com o conteúdo foi preciso fazer um programa para limpar tudo isto.

Lembrando, o resultado final pode ser baixado daqui.

01/08/13: O texto, em formato de eBook pode ser baixado  do SkyDrive através do ícone no alto à direita ("Arquivos do Blog") ou pelos ícones abaixo:



PC Assember Volume I

Ao escrever o post sobre a minha nova impressora, me veio à lembrança o motivo para a compra da minha primeira impressora: eu estava escrevendo um livro.
Um Breve Histórico

Nos idos de 1985, eu era um alegre proprietário de um TK-82C. Em um encontro de usuários, conheci o Nelson Santos que trabalhava como editor na Editora Campus. A idéia inicial, o livro "Jogos em Linguagem de Máquina para a Linha Sinclair" não foi em frente e o Nelson perguntou se eu tinha alguma idéia para um outro livro. Mencionei que estava trabalhando com o PC IBM e que talvez existisse interesse em um livro sovre programação assembly para ele. Assim nasceu o livro PC Assembler, que deu origem a mais outros três livros ("Usando o BIOS", "Usando o DOS" e "Gráficos e Sons").

O Conteúdo

O livro descreve a programação em Assembly no 8086/8088 (naquilo que hoje em dia se chama de "real mode 16 bits"). A maior parte é uma descrição detalhada de cada uma das instruções disponíveis.

As Vendas

No total foram impressos 6253 livros e vendidos 6066 exemplares, em quatro edições. o gráfico abaixo mostra a evolução das vendas semetrais, do segundo semestre de 86 até o primeiro semestre de 93, quando a Editora Campus decidiu não mais reeditar a obra e me devolveu os direitos de publicação.


Para minha total surpresa, o livro foi até considerado um "best-seller":


O Texto

Existe uma longa história sobre a recuperação deste texto, o que será assunto do próximo post.

Estou disponibilizando o texto do livro aqui. Aviso que (por enquanto?) está em formato texto (TXT) pré formatado e falta a listagem do programa exemplo.

30/06/2010: Finalmente o texto completo e devidamente formatado está no blog: veja aqui.

quarta-feira, setembro 12, 2007

Lista: Onze Utilitários "Free"

Segue um levantamento (incompleto) dos utilitários "free" que utilizo no meu dia-a-dia (no Windows). Alguns são "free as in free beer" (grátis) e outros são "free as in free speach" (livres). Alguns são manjados outros talvez não tanto. É provável que existam alternativas melhores, vários deles foram adotados mais por acaso do que por uma comparação sistemática. O único critério relevante é que podem ser usados gratuitamente.
  • Mozilla Firefox: adotei quando a Microsoft tinha perdido o interesse no IE e os hackers do mal faziam a festa. Continua sendo meu navegador principal, embora ache que o IE7 tenha algumas vantagens (como na parte de impressão e uma nova aba sempre a um único click de distância). Nos add-ons uso o DownThemAll! (impressionante como o download default do Firefox e do IE são limitados) e o Html Validator (por enquanto mais como curiosidade, já que praticamente não desenvolvo para Web). Livre.
  • NSIS: fazer um instalador só perde para escrever o manual na lista de tarefas ingratas do desenvolvedor típico. O NSIS é um gerador de instaladores muito esperto. Na sua forma bruta é mais voltado para quem gosta de escrever scripts que para a turma do "arrasta e clica" (ou pior ainda, "next, next, finish"). Está na lista uma série de posts sobre ele. Livre.
  • Sonique: já não lembro mais porque comecei a usar este media player, mas ele está sempre lá na área de notificação (vulgo "system tray"). Eu cheguei até a fazer um plugin de visualização (inútil pois sempre deixo ele minimizado). De qualquer forma, um media player é uma ferramente indispensável para a maioria dos programadores, garantindo uma barreira sonora contra as interrupções externas. Grátis e abandonado.
  • ToDoList: o maior gerador de tráfego no feed do CodeProject, com versões novas a todo instante. Eu só criei coragem para testar após a propaganda do Caloni. Ainda estou me acostumando, minha tradição era fazer a lista em papel para ter o gostinho de riscar as tarefas concluídas. Livre.
  • WinMerge: outra ferramenta básica do desenvolvedor é um comparador de arquivos. Livre.
  • Frhed: todo programador baixo nível gosta de editar arquivos binário e este é um muito bom. Livre.
  • BareTail: uma das coisas mais úteis para depuração no *nix é p "tail -f". Para quem não conhece, o tail é um utilitário que mostra as últimas linhas de um arquivo. A opção -f faz com que sejam mostradas as últimas linhas à medida em que elas são acrescentadas no final. Perfeito para ver log de coisas ocorrendo em "tempo real". O BareTail é excelente, exceto pelo splash screen na versão grátis. Está na lista tentar fazer um utilitário destes. Grátis.
  • SciTE: a ferramenta mais básica de todas: um editor de programas. A internet está cheia de opções e este realmente foi escolhido ao acaso. E depois que você acostuma com um editor, resiste a mudar. Livre.
  • DOSBox: embora mais voltado para jogos antigos, uso também este emulador de DOS para rodar um compilador arcáico que se não gosta do XP. Livre.
  • Doxygen: o lugar da documentação do código fonte é no fonte! A partir de comentários formatados de forma não muito especial, o Doxygen gera a documentação em formato HTML, CHM e PDF. Livre.
  • PDF995: um driver de impressora que gera arquivos PDF. Os anúncios da versão grátis são chatos, mas acho a qualidade do PDF melhor que a gerada pelo OpenOffice (que não coloquei na lista pois uso raramente)
Sintam-se à vontade para explicar nos comentários como este programas são muito piores que outros que eu nem conheço!

Livro de Agosto: State of Fear

Michael Crichton é o conhecido autor de Jurassic Park e um dos criadores da serie ER. Dentre os seus livros, apreciei muito The Andromeda Strain, Jurassic Park, Rising Sun e Airframe. Outros livros não me agradaram tanto: The Terminal Man, Congo, Sphere, Disclosure, Timeline e Prey.

No caso de State of Fear, fiquei com o pé atrás pelas críticas não muito boas e pela fama de ser um livro que nega o aquecimento global. Talvez por isto o livro tenha parado nas pechinchas da Amazon, por um terço do preço de capa. Isto me animou a comprar e tentar deixar de lado o preconceito inicial.

O Livro

O livro é um techno thriler muito bom, daqueles que prende o leitor. Embora um personagem fique frequentemente pregando as teorias do autor, isto não chega a comprometer o rítmo. Tem algumas cenas de ação exageramente forçadas e um trecho um pouco chocante envolvendo antropofagia, mas os filmes de ação da sessão da tarde tem coisa pior.

Como um bonus, as menções a computador não são do tipo que reviram o estômago de quem trabalha com tecnologia.

A posição de Michael Crichton quanto ao Aquecimento Global

O livro possui no final uma Mensagem do Autor, onde ele lista a suas posições. Quem preferir pode ver uma entrevista recente, onde ele reforça os mesmos pontos, que resumo abaixo:
  • as temperatura médias subiram no último século.
  • é discutível quais as causas deste aquecimento e quanto se deve à ação do homem e especificamente à emissão de dióxido de carbônio. A opinião pessoal de Michael Crichton é que o dióxido de carbônio é um fator menor.
  • previsões de aquecimento futuro são baseadas em modelos computacionais. Michael Crichton considera que isto vale pouco mais que um chute e oferece o seu: 0,812436 C nos próximos cem anos.
  • previsões de catástrofes estão sendo usadas para justificar gastos imensos em programas urgentes.
  • ele está certo que existe certeza demais no mundo.
  • todos tem uma agenda. Exceto ele.
Para reforçar tudo isto, existem inúmeras notas de rodapé e várias páginas de referência.

Dois sites (encontrados meio ao acaso) para ver algumas reações a esta posição:
O Veridito

State of Fear é um bom livro como diversão. Pode-se (e deve-se) questionar as posições do autor. Por outro lado, é preocupante a facilidade com que as pessoas desprezam o livro e a posição do autor simplesmente por serem contra o "senso comum".

terça-feira, setembro 11, 2007

Algorítmos de Ordenação - parte VIII

Para fechar a série de posts, um exemplo um pouco mais completo.

O programa Ordena é um utilitário de ordenação, comandado pela linha de comando (o que é bem apropriado, visto que a operação de ordenação é algo inerentemente "batch" e não interativa). Como características importantes, destaco:
  • Escrito em C ANSI para maior portabilidade (testei no Windows com o Visual C 6 e no GCC 3.2. sob Linux).
  • Ordenação de arquivos texto, com chaves alfanuméricas: o programa ordena linhas finalizadas por CR LF (LF no Linux). Para reduzir a movimentação na memória, ordena os registros indiretamente através de um vetor de ponteiros.
  • Suporte a múltiplas chaves: como comentei na introdução, basta comparar as chaves uma a uma até achar a primeira que tenha diferença.
  • Ordena arquivos maiores que a memória: o arquivo é ordenado em blocos, que depois são combinados (merge). O tamanho do bloco pode ser definido na linha de comando (útil para exercitar esta parte do programa).
  • Suporta os algorítmos BubbleSort, HeapSort, QuickSort e ShellSort.
Os fontes estão comentados de forma compatível com o Doxygen, o que permite gerar documentação em formatos HTML e CHM.

O programa pode ser baixo daqui.

segunda-feira, setembro 10, 2007

Algoritmos de Ordenação - Atualização

Como comentei na introdução, escrevi os artigos e o primeiro programa de demonstração dos algorítmos de ordenação há muito tempo atrás. No caso do programa eu apenas dei uma acertada nos comentários antes de publicar.

Ao fazer o segundo programa de demonstração, tive a desagradável surpresa de encontrar dois bugs:
  • no Bubble Sort, em um ponto eu me confundi quanto ao índice inicial dos dados a ordenar.
  • no QuickSort, o algorítmo (adaptado do Knuth) assumia que valores especiais eram colocados antes e depois dos dados para "segurar" os índices nas pontas. E eu não coloco estes valores.
A versão revisada está aqui.