Hacker's Delight

Author: Henry S. Warren
4.6
All Stack Overflow 33

Comments

by Piotr Lesnicki   2017-08-20

There is a book which gathers many of those 'magic tricks' and that may be interesting for you: The Hacker's Delight.

You have for example many tricks like bit twiddling hacks etc... (you have several square root algorithms for example that you can see on the google books version)

by anonymous   2017-08-20

HD probably refers to Hacker's Delight by Henry S. Warren. Indeed, this formula appears on page 11, section 2-1.

by anonymous   2017-08-20

I don't understand why all the answers to that question are the same.

There are several ways to calculate the square root from a number. One of them was proposed by Isaac Newton. I'll only write one of the simplest implementations of this method. I use it to improve the accuracy of double's square root.

// x - a number, from which we need to calculate the square root
// epsilon - an accuracy of calculation of the root from our number.
// The result of the calculations will differ from an actual value
// of the root on less than epslion.
public static decimal Sqrt(decimal x, decimal epsilon = 0.0M)
{
    if (x < 0) throw new OverflowException("Cannot calculate square root from a negative number");

    decimal current = (decimal)Math.Sqrt((double)x), previous;
    do
    {
        previous = current;
        if (previous == 0.0M) return 0;
        current = (previous + x / previous) / 2;
    }
    while (Math.Abs(previous - current) > epsilon);
    return current;
}

About speed: in the worst case (epsilon = 0 and number is decimal.MaxValue) the loop repeats less than a three times.

If you want to know more, read this (Hacker's Delight by Henry S. Warren, Jr.)

by BlackJack   2017-08-19
I'm a rising junior at Yale, and I know Sean well and we both took systems programming together. We definitely covered bit manipulation and bit tricks, as well as number representation and lots of other stuff.

Sean's an incredibly bright guy but he's more interested in building world-changing apps and web dev. as opposed to low-level systems programming. There are other classes here where you have to code in assembly and do all sorts of bit manipulation (OS's comes to mind). The core CS sequence in our school is also in C, which differs notably from other places that use Python, Java, etc.

For anyone who wants to learn more about bit manipulation, Henry Warren's "Hacker's Delight" is a terrific book (http://www.amazon.com/Hackers-Delight-Henry-S-Warren/dp/0201...).

by azanar   2017-08-19
Another great resource for tidbits like this is _Hacker's Delight_, by Henry S. Warren, Jr. It covers a number of other tricks outside of bit twiddling, as well. Worth checking out for anyone who finds this sort of stuff fascinating.

Link: http://www.amazon.com/Hackers-Delight-Henry-S-Warren/dp/0201...

by axod   2017-08-19
Clever stuff. If you're interested in such things, best book I've seen is "Hackers Delight" http://www.amazon.com/Hackers-Delight-Henry-S-Warren/dp/0201...

Author covers really clever techniques to count bits, count non zero bytes like this etc etc. Bit manipulation at its best.