See what's going on with flipcode!




This section of the archives stores flipcode's complete Developer Toolbox collection, featuring a variety of mini-articles and source code contributions from our readers.

 

  Little Math Trick
  Submitted by



For what its worth here's a cool little thing I 'discovered' recently.

We all know that loops take up most of program execution. Reducing time in loops can go a long way in optimizing your code. In the spirit of optimizing loop times I'll point your attention to a situation where you are multiplying an accumulator by a constant value (a geometric sequence for you math guys). Generally you would do this:

float result, r;
int i;

result = 3.0f; r = 2.0f; for (i=0; i<SOME_VALUE; i++) result *= r;



Thats spectacular, but isn't addition faster? Why yes, but how can we add if we're multiplying? Like this:

float result, r;
int i;

result = log(3.0f); r = log(2.0f); for (i=0; i<SOME_VALUE; i++) result += r; result = exp(result);

Now we're adding instead of multipying!

I've tested this, and it works. You introduce error into the result, but any floating point op on a computer does that. Here are my results from a little test proggie I wrote:

Start conditions:
Initial value: 1.000000e+064
Multiplier: 9.99999999999e-1
# Reps: 1000000000

Without optimization:
Result: 9.990005e+063
Time: 10144

Result: 9.990057e+063
With optimization:
Result: 9.990057e+063
Time: 6059


Percent error: 0.000005
Performance increase: 1.674204

Not bad. If you have multiple geometric sequences in a single loop your savings are doubled. Of course if you're doing a small number of repetitions then the cost of using two log()'s and an exp() probably won't make it worth the trouble, but for larger, tight loops it can give you a significant speed boost.

Mike Reid aka "Leon Rauis" aka "Promiscuous Robot"

The zip file viewer built into the Developer Toolbox made use of the zlib library, as well as the zlibdll source additions.

 

Copyright 1999-2008 (C) FLIPCODE.COM and/or the original content author(s). All rights reserved.
Please read our Terms, Conditions, and Privacy information.