Other examples of magical calculations

I have seen this topic here about John Carmack's magical way to calculate square root, which refers to this article: http://www.codemaestro.com/reviews/9. This surprised me a lot, I just didn't ever realized that calculating sqrt could be so faster.

I was just wondering what other examples of "magic" exist out there that computer games use to run faster.

UPDATE: John Carmack is not the author of the magic code. This article tells more. Thanks @moocha.

Answers


Bit Twiddling Hacks has many cool tricks.

Although some of it is dated now, I was awed by some of the tricks in "The Zen of Code Optimization" by Michael Abrash. The implementation of the Game Of Life is mind-boggling.


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)


Not exactly a mathematical hack, but I like this one about Roman Numerals in Java6:

public class Example {
    public static void main(String[] args) {
        System.out.println(
            MCMLXXVII + XXIV
        );
    }
}

will give you the expected result (1977 + 24 = 2001), because of a rewrite rule: class Transform extends TreeTranslator, an internal class of the Java compiler.

Transform visits all statements in the source code, and replaces each variable whose name matches a Roman numeral with an int literal of the same numeric value.

public class Transform extends TreeTranslator {
    @Override
    public void visitIdent(JCIdent tree) {
        String name = tree.getName().toString();
        if (isRoman(name)) {
            result = make.Literal(numberize(name));
            result.pos = tree.pos;
        } else {
            super.visitIdent(tree);
        }
    }
}

I'm a big fan of Bresenham Line, but man the CORDIC rotator enabled all kinds of pixel chicanery for me when CPUs were slower.


I have always been impressed from two classic 'magic' algorithms that have to do with dates:

Some (untested) code follows:

import math

def dayOfWeek(dayOfMonth, month, year):
    yearOfCentury = year%100
    century = year // 100

    h = int(dayOfMonth + math.floor(26.0*(month + 1)/10) + yearOfCentury \
         + math.floor(float(yearOfCentury)/4) + math.floor(float(century)/4) \
         + 5*century) % 7
    return ['Saturday', 'Sunday', 'Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday'][h]

def easter(year):
    a = year%19
    b = year%4
    c = year%7
    k = int(math.floor(float(year)/100))
    p = int(math.floor((13 + 8.0*k)/25))
    q = int(math.floor(float(k)/4))
    M = (15 - p + k - q)%30
    N = (4 + k - q)%7
    d = (19*a + M)%30
    e = (2*b + 4*c + 6*d + N)%7
    day1 =  22 + d + e 
    if day1 <= 31: return "March %d"%day1
    day2 = d + e - 9
    if day2 == 26: return "April 19"
    if day2 == 25 and (11*M + 11)%30 < 19: return "April 18"
    return "April %d"%day2  

print dayOfWeek(2, 12, 2008)  # 'Tuesday'
print easter(2008)            # 'March 23'

Need Your Help

Mxml and as3 confusion [simple]

flex actionscript-3 mxml

I was wondering i can call an as3 function defined in script from mxml code just like this:

ASP.NET MVC - View with master page, how to set title?

asp.net asp.net-mvc master-pages

What is prefered way of setting html title (in head) for view when using master pages?