CODEWITHSUNDEEP
performancelanguage-agnosticmath
Paulo Guedes
Paulo Guedes

Reputation: 7259

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.

Upvotes: 13

Views: 1031

Answers (5)

AShelly
AShelly

Reputation: 35540

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.

Upvotes: 3

Federico A. Ramponi
Federico A. Ramponi

Reputation: 47075

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'

Upvotes: 3

VonC
VonC

Reputation: 1324093

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);
        }
    }
}

Upvotes: 5

Piotr Lesnicki
Piotr Lesnicki

Reputation: 9730

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)

Upvotes: 5

plinth
plinth

Reputation: 49179

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.

Upvotes: 4

Related Questions