Rozkosz hakerów
Hacker's Delight to książka algorytmów oprogramowania autorstwa Henry'ego S. Warrena Jr., opublikowana po raz pierwszy w 2002 roku. Przedstawia szybkie algorytmy arytmetyczne na poziomie bitowym i niskiego poziomu do typowych zadań, takich jak liczenie bitów lub zwiększanie szybkości dzielenia za pomocą mnożenia.
Tło
Autor, badacz IBM pracujący nad systemami od IBM 704 do PowerPC , zbierał w trakcie swojej kariery coś, co nazwał „sztuczkami programistycznymi”. Te sztuczki dotyczą wydajnej niskopoziomowej manipulacji ciągami bitów i liczbami. Zgodnie z przedmową do książki Guya L. Steele'a , grupa docelowa obejmuje autorów kompilatorów i osoby piszące wysokowydajny kod.
Streszczenie
Przykłady programowania są napisane w C i asemblerze dla architektury RISC podobnej, ale nie identycznej z PowerPC . Algorytmy podaje się w postaci formuł dla dowolnej liczby bitów, przykłady zwykle dla 32 bitów.
Poza wstępem rozdziały są od siebie niezależne, a każdy z nich poświęcony jest innej tematyce. Wiele algorytmów w książce opiera się na uzupełnionych do dwóch .
Tematyka drugiego wydania książki obejmuje algorytmy dla
- Podstawowe algorytmy manipulowania poszczególnymi bitami, wzory na tożsamości, nierówności, wykrywanie przepełnienia dla operacji arytmetycznych i przesunięć
- Zaokrąglanie w górę i w dół do wielokrotności znanej potęgi 2, następnej potęgi 2 oraz do wykrywania, czy operacja przekroczyła granicę potęgi 2
- Sprawdzanie granic
- Liczenie sumy , wiodących i końcowych zer
- Wyszukiwanie ciągów bitów
- Permutacje bitów i bajtów w słowie
- Algorytmy oprogramowania do mnożenia
- Dzielenie całkowite
- Efektywne dzielenie liczb całkowitych i obliczanie reszty ze znanego dzielnika
- Całkowite pierwiastki kwadratowe i sześcienne
- Niezwykłe systemy liczbowe, w tym podstawa -2
- Transfer wartości między liczbami zmiennoprzecinkowymi a liczbami całkowitymi
- Cykliczne kontrole redundancji , kody korygujące błędy i kody Graya
- Krzywe Hilberta , w tym omówienie zastosowań
Styl
Styl przypomina nieformalny podręcznik do matematyki. Formuły są szeroko stosowane. Dowody matematyczne podano dla niektórych nieoczywistych algorytmów, ale nie są one tematem książki.
Przyjęcie
Ogólny odbiór był ogólnie pozytywny.
Historia publikacji
Książka została opublikowana przez Addison-Wesley Professional . Pierwsza edycja ukazała się w 2002 roku, a druga w 2013 roku.
Zobacz też
Dalsza lektura
- Beeler, Michael; Gosper, Ralph William ; Schroeppel, Richard C. (kwiecień 1995) [1972-02-29]. „Notatka dotycząca sztucznej inteligencji nr 239” . W Baker, Henry Givens Jr. (red.). HAKMEM (przepisany i przekonwertowany red.). Cambridge, Massachusetts, USA: Laboratorium Sztucznej Inteligencji , Massachusetts Institute of Technology (MIT). Zarchiwizowane od oryginału w dniu 2019-10-08 . Źródło 2016-01-02 .
- Jones, Douglas W. (10.09.2014) [1999]. „Poradniki arytmetyczne” . Iowa City, Iowa, USA: University of Iowa, Wydział Informatyki. Zarchiwizowane od oryginału w dniu 2019-07-10 . Źródło 2016-01-03 .
- Cowlishaw, Mike F. (2015) [1981, 2008]. „Ogólna arytmetyka dziesiętna” . Zarchiwizowane od oryginału w dniu 2019-11-02 . Źródło 2016-01-02 .
- Ingenoso, Tony (1999-02-03) [1998]. „Rozdział 11 - Więcej sztuczek w kodzie C i asemblerze” . Sprawienie, by kod działał lepiej - Jak zminimalizować rozmiar kodu 80x86, a czasem go przyspieszyć (e-book). Zarchiwizowane od oryginału w dniu 2019-11-18 . Źródło 2019-11-18 .
- Anderson, Sean Eron, wyd. (2009-11-26) [1997]. „Hacki do kręcenia bitów” . Uniwersytet Stanforda . Zarchiwizowane od oryginału w dniu 2020-06-01 . Źródło 2020-06-01 .