|
   |
© 2000 Pedro Freire |
|
|
|
|
© 2000 Pedro Freire |
Esta é uma adenda à segunda parte do algoritmo da raiz quadrada. Contém submissões e sugestões enviadas por leitores. Eu revi-as, mas não perdi o tempo com elas como o que perdi com os meus algoritmos (a não ser que fossem mais rápidas, e nenhuma surgiu até agora). Isto significa que poderão existir erros ou imprecisões. Também significa que esta página irá apenas exibir os algoritmos sem os analisar. Por favor contacte os autores para mais informações.
Quando publiquei o meu algoritmo de raiz quadrada, houve um professor universitário norte-americano que me respondeu. Infelizmente respondeu-me para um endereço temporário que usei para publicar o anúncio do algoritmo nas Usenet News, e quando pude voltar a verificar esse endereço, a mensagem dele já tinha sido apagada pelo sistema.
Lembro-me no entanto da base do argumento dele. O meu algoritmo é iterativo. Verdade. E os algoritmos mais avançados de hoje em dia são sequenciais: o que de facto os torna mais rápidos. Mas... os algoritmos sequenciais usam várias operações que são inerentemente iterativas, ou muito onerosas de implementar sequencialmente em hardware: tome-se como exemplo mais simples a multiplicação.
A multiplicação é inerentemente iterativa: por cada dígito binário de um dos operandos, adicionamos ou não o outro operando (devidamente ajustado - shifted) ao resultado. Esta operação pode ser implementada por um circuito baseado em tabelas de Moore, o que a torna extremamente rápida (tipicamente 1 ciclo de relógio), mas ocupa muito espaço de silicone. O primeiro processador Alpha implementava a multiplicação desta forma, e metade do espaço de silicone do circuito (e do seu custo, portanto), era ocupado pela operação de multiplicação.
Isto quer dizer que as operações básicas dos algoritmos sequenciais de raiz quadrada existentes não são por si tão rápidas quanto isso. As operações básicas usadas no meu algoritmo são ANDs, ORs, adições e subtracções que podem ser facilmente implementadas em 1 ciclo de relógio cada. Tal como explico, o ciclo também pode ser desdobrado para se ter apenas metade das iterações, ou menos.
Seria bom ter podido argumentar com esse professor universitário sobre estas questões, mas ao ter perdido a mensagem dele, perdi todo e qualquer contacto do mesmo. Se você é ele, por favor entre em contacto comigo!
