Gaming Your Way

May contain nuts.

Pythagorean Theorem, how quick are you ?

I'm becoming a bit of a speed testing slut with as3, and seeing how this function is used in so many games, I thought I'd have a play and see which actually is the quickest way to do this.

Point.distance() seems to have everything going for it, but does it ?

import flash.utils.getTimer;
import flash.geom.Point;

var time:Number;

var point1:Point=new Point(100,100);
var point2:Point=new Point(200,200);

var dist:Number;
var dx:Number;
var dy:Number;

function runPythagorean():void{
    time = getTimer();
    for (var i:int = 0; i < 10000000; i++) {
         dx = point2.x-point1.x;
         dy = point2.y-point1.y;
         dist = Math.sqrt(dx*dx + dy*dy);
    }
    trace("runPythagorean(): ", (getTimer()-time));
}

function runDistance():void{
    time = getTimer();
    for (var i:int = 0; i < 10000000; i++) {
         dist = Point.distance(point1,point2);
    }
    trace("runDistance(): ", (getTimer()-time));
}

runPythagorean();
runDistance();

Slap that into Flash, and be surprised at the huge difference between the two ( For those of you who prefer just to look rather than get involved, on my machine I got the following:

runPythagorean():  1452
runDistance():  10485

Not really neck and neck ).

So the distance method is a none starter ( What the hell does Flash do behind the scenes ? It's only returning a Number, it shouldn't need to be doing anything other that the code in the runPythagorean() method ).

Don't know if I've posted about it here before either, but avoid Rectangle.intersects() for the same reasons too.

Whilst I was testing I thought I'd do the old shortcut of:

var sq:Function=Math.sqrt;
dist = sq(dx*dx + dy*dy);

Again, another surprise,

runPythagorean():  1464
runPythagoreanWithShortCut():  2824

Finally, I finished off with some "quicker" versions of sqrt, ie

//---------------------------------------------------------------------------------------
function sqrt(w:Number):Number{
// Fast Math sqrt function from
// http://osflash.org/as3_speed_optimizations#as3_speed_tests
    var thresh    : Number = 0.002;
    var b:Number = w * 0.25
    var a:Number;
    var c:Number;
    
    if (w == 0) return 0;
    
    do {
        c = w / b;
        b = (b + c) * 0.5;
        a = b - c;
        if (a < 0) a = -a;
    }
    while (a > thresh);
    
    return b;
}
        
//---------------------------------------------------------------------------------------
function fsqrt(w:Number):Number{
// SUPA fast but not very accurate sqrt
// Fast Math sqrt function from
// http://osflash.org/as3_speed_optimizations#as3_speed_tests
    var thresh    : Number = 2;            //1
    var b:Number = w * 0.25
    var a:Number;
    var c:Number;
    
    do {
        c = w / b;
        b = (b + c) * 0.5;
        a = b - c;
        if (a < 0) a = -a;
    }
    while (a > thresh);
    
    return b;
}


I've got both of these in my MathX class, which is a collection of quicker alternatives to the built in methods and various other little math based utils.
This test made me think I was going a bit mental,

runPythagorean():  1452
runQuickSqrt():  3514
runQuickFSqrt():  3237

Now I've not done these tests over and over and averaged them out, 'cause to be honest the results really aren't close enough to warrant it. Please feel free to try these out yourselves and post the results back here. Maybe those last two methods should be inlined rather than wrapped in functions, but I've really not got the inclination to try it out.

Squize.

Comments (4) -

  • Panayoti

    8/25/2008 6:15:47 PM |

    Tasty goodness, Squize.

  • Zack Jordan

    8/26/2008 12:02:21 PM |

    Now that's interesting.  It's one of those things that you always take for granted until some guy does some speed tests.  Thanks for being that guy.

  • Jeff Fulton

    8/26/2008 5:06:06 PM |

    Great work, Squize.

    <spam>
    Free Replica golden watch underpants Paris naked feed blaster flash game Olympics girls swim suit beach volley ball rolando's girl friend Becks Posh Barack Obama \
    </spam>

    Also, I can't wait sound in FMAME! (even if Arcade sound was crap)

  • Squize

    8/27/2008 12:05:32 PM |

    Thanks guys ( btw Jeff, we've moved on from content spam now as our ranking seems to have dropped after trying it, although yours was of a high level, thanks :) ).

    I was thinking after posting the results that perhaps the "quicker" sqrt methods may benefit from JIT, and in my simple tests they may be slipping out of being compiled ( I'm sure that class constructors aren't compiled, maybe just dropping code straight onto a frame like I did for this test means the JIT doesn't pick them up ? ), so the results may improve, but it's really not something I can face doing again.

    I've been using a faster atan2 for a while that I found somewhere and ported to as3, maybe I'll re-test that and post that up here, as I'm finding I'm using that a lot in Orbs so it's handy to save ms where ever you can.

Comments are closed