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 bits y de bajo nivelpara tareas comunes como contar bits o mejorar la velocidad de división mediante 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 números y cadenas de bits. Según el prólogo del libro de Guy L. Steele , el público objetivo incluye escritores de compiladores y 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 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.
- Redondear 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
- Contando ceros totales , iniciales y finales
- Buscando cadenas de bits
- Permutaciones de bits y bytes en una palabra.
- Algoritmos de software para la multiplicación.
- División entera
- División entera eficiente y cálculo del resto cuando se conoce el divisor
- Raíces enteras cuadradas y cúbicas
- Sistemas numéricos inusuales, incluida la base -2
- Transferencia de valores entre punto flotante y entero
- Comprobaciones de redundancia cíclica , códigos de corrección de errores y códigos Gray
- Curvas de Hilbert que incluyen una discusión sobre aplicaciones.
Estilo
El estilo es el de un libro de texto de matemáticas informal. Las fórmulas se utilizan ampliamente. Se dan demostraciones matemáticas para algunos algoritmos no obvios, pero no son el tema central del libro.
Recepción
La recepción general ha sido positiva en términos generales. [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]
Ver también
Referencias
- ^ abc Warren Jr., Henry S. (2013). El placer del hacker (2 ed.). Addison Wesley - Pearson Education, Inc. ISBN 978-0-321-84268-8.
- ^ Baxter, Michael (1 de abril de 2003). "El placer del hacker". Reseñas. Diario de Linux . 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: estantería del ingeniero: el placer del hacker por Henry S. Warren, Jr". Tiempos EE.UU. Archivado desde el original el 2 de abril de 2017 . Consultado el 2 de abril de 2017 .
- ^ Warren Jr., Henry S. (2002). El placer del hacker (1 ed.). Addison Wesley . ISBN 978-0-201-91465-8.
Otras lecturas
- Beeler, Michael; Gosper, Ralph William ; Schroeppel, Richard C. (abril de 1995) [29 de febrero de 1972]. "Memorando de Inteligencia Artificial nº 239". En Baker, Henry Givens Jr. (ed.). HAKMEM (edición reescrito 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 (3 de febrero de 1999) [1998]. "Capítulo 11 - Más trucos en código C y ensamblador". 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 18 de noviembre de 2019 . Consultado el 18 de noviembre de 2019 .
- Anderson, Sean Eron, ed. (26 de noviembre de 2009) [1997]. "Trucos poco complicados". Universidad Stanford . Archivado desde el original el 1 de junio de 2020 . Consultado el 1 de junio de 2020 .
enlaces externos
- Archivo del sitio web de Hacker's Delight