Libro de algoritmos de software
Hacker's Delight es un libro de algoritmos de software de Henry S. Warren, Jr. publicado por primera vez en 2002. Presenta algoritmos aritméticos rápidos de nivel de bit y de bajo nivelpara tareas comunes como contar bits o mejorar la velocidad de la división mediante el uso de la multiplicación.
Fondo
El autor, un investigador de IBM que trabaja en sistemas que van desde el IBM 704 hasta el PowerPC , [1] recopiló lo que llamó "trucos de programación" a lo largo de su carrera. Estos trucos se refieren a la manipulación eficiente de bajo nivel de cadenas de bits y números. Según el prólogo del libro escrito por Guy L. Steele , el público objetivo incluye a los escritores de compiladores y a las personas que escriben código de alto rendimiento.
Resumen
Los ejemplos de programación están escritos en C y ensamblador para una arquitectura RISC similar, pero no idéntica a la de PowerPC . Los algoritmos se dan como fórmulas para cualquier número de bits; los ejemplos suelen ser para 32 bits.
Aparte de la introducción, los capítulos son independientes entre sí y cada uno se centra en un tema en particular. Muchos algoritmos del libro dependen de números enteros en complemento a dos .
El tema de la segunda edición del libro [1] incluye algoritmos para
- Algoritmos básicos para manipular bits individuales, fórmulas para identidades, desigualdades, detección de desbordamiento para operaciones aritméticas y desplazamientos.
- Redondeo hacia arriba y hacia abajo a un múltiplo de una potencia conocida de 2, la siguiente potencia de 2 y para detectar si una operación cruzó un límite de potencia de 2
- Comprobando límites
- Contar total , ceros iniciales y finales
- Buscando cadenas de bits
- Permutaciones de bits y bytes en una palabra
- Algoritmos de software para la multiplicación
- División de enteros
- División eficiente de números enteros y cálculo del resto cuando se conoce el divisor
- Raíces cuadradas y cúbicas de números enteros
- Sistemas numéricos inusuales, incluido el de base -2
- Transferencia de valores entre coma flotante y entero
- Comprobaciones de redundancia cíclica , códigos de corrección de errores y códigos Gray
- Curvas de Hilbert incluyendo un análisis de sus aplicaciones
Estilo
El estilo es el de un libro de texto matemático informal. Se utilizan fórmulas de forma profusa. Se ofrecen pruebas matemáticas para algunos algoritmos no obvios, pero no son el foco del libro.
Recepción
La recepción general ha sido generalmente positiva. [2] [3]
Historial de publicaciones
El libro fue publicado por Addison-Wesley Professional . La primera edición se publicó en 2002 [4] y la segunda en 2013. [1]
Véase también
Referencias
- ^ abc Warren Jr., Henry S. (2013). Hacker's Delight (2.ª edición). Addison Wesley - Pearson Education, Inc. ISBN 978-0-321-84268-8.
- ^ Baxter, Michael (1 de abril de 2003). "Hacker's Delight". Reseñas. Linux Journal . Archivado desde el original el 27 de septiembre de 2020. Consultado el 28 de agosto de 2021 .
- ^ Maxfield, Clive "Max" (5 de abril de 2012). "Reseña del libro: Engineer's Bookshelf - Hacker's Delight de Henry S. Warren, Jr". EE Times . Archivado desde el original el 2 de abril de 2017. Consultado el 2 de abril de 2017 .
- ^ Warren Jr., Henry S. (2002). Hacker's Delight (1.ª edición). Addison Wesley . ISBN 978-0-201-91465-8.
Lectura adicional
- Beeler, Michael; Gosper, Ralph William ; Schroeppel, Richard C. (abril de 1995) [29 de febrero de 1972]. "Artificial Intelligence Memo No. 239". En Baker, Henry Givens Jr. (ed.). HAKMEM (edición reescrita y convertida). Cambridge, Massachusetts, EE. UU.: Laboratorio de Inteligencia Artificial , Instituto Tecnológico de Massachusetts (MIT). Archivado desde el original el 8 de octubre de 2019. Consultado el 2 de enero de 2016 .
- Jones, Douglas W. (10 de septiembre de 2014) [1999]. "Tutoriales de aritmética". Iowa City, Iowa, EE. UU.: Universidad de Iowa, Departamento de Ciencias de la Computación. Archivado desde el original el 10 de julio de 2019. Consultado el 3 de enero de 2016 .
- Cowlishaw, Mike F. (2015) [1981, 2008]. "Aritmética decimal general". Archivado desde el original el 2 de noviembre de 2019. Consultado el 2 de enero de 2016 .
- Ingenoso, Tony (1999-02-03) [1998]. "Capítulo 11 - Más trucos en código C y ensamblador". Cómo hacer que el código funcione mejor: cómo minimizar el tamaño del código de 80x86 y, a veces, hacerlo más rápido (libro electrónico). Archivado desde el original el 2019-11-18 . Consultado el 2019-11-18 .
- Anderson, Sean Eron, ed. (2009-11-26) [1997]. "Bit Twiddling Hacks". Universidad de Stanford . Archivado desde el original el 2020-06-01 . Consultado el 2020-06-01 .
Enlaces externos
- Archivo del sitio web Hacker's Delight