I have an image manipulation routine that I wrote, and it is already pretty fast, but i could get another 5 FPS if I could eliminate the use of the sqaure-root function, and replace it with a simpler, less time-consuming equation. The two variables involved in the equation are incremented by 1, but p2x is only incremented every time p2y hits a certain number (the height of the image). Looking at the outputs of the function, it seems to me that there may be a pattern, I just can''t find it. If anyone can figure this out, or has some advice for the best way to go about looking for a pattern, please let me know! p2x and p2y are the two loops: p2x is the x axis, and p2y is the y axis. The equation is as follows:

R = Sqrt((p2x * p2x) + (p2y * p2y)) 

LOOK FOR A PATERN, FIND AN EQUATION! EVEN 5 MULTIPLICATIONS ARE FASTER THEN A SQRT FUNCTION CALL! The following is the output of the Sqrt function, given the different values of p2x and p2y, remember that thoughs two variables are squared (see formula above). R represents the result of the Sqrt function-call. p2x = 0, p2y = 0: R = 0 p2x = 0, p2y = 1: R = 1 p2x = 0, p2y = 2: R = 2 p2x = 0, p2y = 3: R = 3 p2x = 0, p2y = 4: R = 4 p2x = 0, p2y = 5: R = 5 p2x = 0, p2y = 6: R = 6 p2x = 0, p2y = 7: R = 7 p2x = 0, p2y = 8: R = 8 p2x = 0, p2y = 9: R = 9 p2x = 0, p2y = 10: R = 10 p2x = 0, p2y = 11: R = 11 p2x = 0, p2y = 12: R = 12 p2x = 0, p2y = 13: R = 13 p2x = 0, p2y = 14: R = 14 p2x = 0, p2y = 15: R = 15 p2x = 0, p2y = 16: R = 16 p2x = 0, p2y = 17: R = 17 p2x = 0, p2y = 18: R = 18 p2x = 0, p2y = 19: R = 19 p2x = 0, p2y = 20: R = 20 p2x = 0, p2y = 21: R = 21 p2x = 0, p2y = 22: R = 22 p2x = 0, p2y = 23: R = 23 p2x = 0, p2y = 24: R = 24 p2x = 0, p2y = 25: R = 25 p2x = 0, p2y = 26: R = 26 p2x = 0, p2y = 27: R = 27 p2x = 0, p2y = 28: R = 28 p2x = 0, p2y = 29: R = 29 p2x = 0, p2y = 30: R = 30 p2x = 0, p2y = 31: R = 31 p2x = 0, p2y = 32: R = 32 p2x = 0, p2y = 33: R = 33 p2x = 0, p2y = 34: R = 34 p2x = 0, p2y = 35: R = 35 p2x = 0, p2y = 36: R = 36 p2x = 0, p2y = 37: R = 37 p2x = 0, p2y = 38: R = 38 p2x = 0, p2y = 39: R = 39 p2x = 0, p2y = 40: R = 40 p2x = 0, p2y = 41: R = 41 p2x = 0, p2y = 42: R = 42 p2x = 0, p2y = 43: R = 43 p2x = 0, p2y = 44: R = 44 p2x = 0, p2y = 45: R = 45 p2x = 0, p2y = 46: R = 46 p2x = 0, p2y = 47: R = 47 p2x = 0, p2y = 48: R = 48 p2x = 0, p2y = 49: R = 49 p2x = 0, p2y = 50: R = 50 p2x = 0, p2y = 51: R = 51 p2x = 0, p2y = 52: R = 52 p2x = 0, p2y = 53: R = 53 p2x = 0, p2y = 54: R = 54 p2x = 0, p2y = 55: R = 55 p2x = 0, p2y = 56: R = 56 p2x = 0, p2y = 57: R = 57 p2x = 0, p2y = 58: R = 58 p2x = 0, p2y = 59: R = 59 p2x = 0, p2y = 60: R = 60 p2x = 0, p2y = 61: R = 61 p2x = 0, p2y = 62: R = 62 p2x = 0, p2y = 63: R = 63 p2x = 1, p2y = 0: R = 1 p2x = 1, p2y = 1: R = 1.4142135623731 p2x = 1, p2y = 2: R = 2.23606797749979 p2x = 1, p2y = 3: R = 3.16227766016838 p2x = 1, p2y = 4: R = 4.12310562561766 p2x = 1, p2y = 5: R = 5.09901951359278 p2x = 1, p2y = 6: R = 6.08276253029822 p2x = 1, p2y = 7: R = 7.07106781186548 p2x = 1, p2y = 8: R = 8.06225774829855 p2x = 1, p2y = 9: R = 9.05538513813742 p2x = 1, p2y = 10: R = 10.0498756211209 p2x = 1, p2y = 11: R = 11.0453610171873 p2x = 1, p2y = 12: R = 12.0415945787923 p2x = 1, p2y = 13: R = 13.0384048104053 p2x = 1, p2y = 14: R = 14.0356688476182 p2x = 1, p2y = 15: R = 15.0332963783729 p2x = 1, p2y = 16: R = 16.0312195418814 p2x = 1, p2y = 17: R = 17.0293863659264 p2x = 1, p2y = 18: R = 18.0277563773199 p2x = 1, p2y = 19: R = 19.0262975904404 p2x = 1, p2y = 20: R = 20.0249843945008 p2x = 1, p2y = 21: R = 21.0237960416286 p2x = 1, p2y = 22: R = 22.0227155455452 p2x = 1, p2y = 23: R = 23.0217288664427 p2x = 1, p2y = 24: R = 24.0208242989286 p2x = 1, p2y = 25: R = 25.0199920063936 p2x = 1, p2y = 26: R = 26.0192236625154 p2x = 1, p2y = 27: R = 27.0185121722126 p2x = 1, p2y = 28: R = 28.0178514522438 p2x = 1, p2y = 29: R = 29.0172362570938 p2x = 1, p2y = 30: R = 30.0166620396073 p2x = 1, p2y = 31: R = 31.0161248385416 p2x = 1, p2y = 32: R = 32.0156211871642 p2x = 1, p2y = 33: R = 33.0151480384384 p2x = 1, p2y = 34: R = 34.0147027033899 p2x = 1, p2y = 35: R = 35.0142828000232 p2x = 1, p2y = 36: R = 36.0138862107382 p2x = 1, p2y = 37: R = 37.0135110466435 p2x = 1, p2y = 38: R = 38.0131556174964 p2x = 1, p2y = 39: R = 39.0128184062623 p2x = 1, p2y = 40: R = 40.0124980474851 p2x = 1, p2y = 41: R = 41.0121933088198 p2x = 1, p2y = 42: R = 42.0119030752 p2x = 1, p2y = 43: R = 43.0116263352131 p2x = 1, p2y = 44: R = 44.0113621693308 p2x = 1, p2y = 45: R = 45.0111097397076 p2x = 1, p2y = 46: R = 46.0108682813094 p2x = 1, p2y = 47: R = 47.0106370941726 p2x = 1, p2y = 48: R = 48.0104155366312 p2x = 1, p2y = 49: R = 49.0102030193714 p2x = 1, p2y = 50: R = 50.0099990001999 p2x = 1, p2y = 51: R = 51.0098029794274 p2x = 1, p2y = 52: R = 52.0096144957834 p2x = 1, p2y = 53: R = 53.0094331227943 p2x = 1, p2y = 54: R = 54.0092584655631 p2x = 1, p2y = 55: R = 55.0090901579003 p2x = 1, p2y = 56: R = 56.0089278597618 p2x = 1, p2y = 57: R = 57.0087712549569 p2x = 1, p2y = 58: R = 58.0086200490927 p2x = 1, p2y = 59: R = 59.0084739677277 p2x = 1, p2y = 60: R = 60.00833275471 p2x = 1, p2y = 61: R = 61.0081961706786 p2x = 1, p2y = 62: R = 62.00806399171 p2x = 1, p2y = 63: R = 63.0079360080935 p2x = 2, p2y = 0: R = 2 p2x = 2, p2y = 1: R = 2.23606797749979 p2x = 2, p2y = 2: R = 2.82842712474619 p2x = 2, p2y = 3: R = 3.60555127546399 p2x = 2, p2y = 4: R = 4.47213595499958 p2x = 2, p2y = 5: R = 5.3851648071345 p2x = 2, p2y = 6: R = 6.32455532033676 p2x = 2, p2y = 7: R = 7.28010988928052 p2x = 2, p2y = 8: R = 8.24621125123532 p2x = 2, p2y = 9: R = 9.21954445729289 p2x = 2, p2y = 10: R = 10.1980390271856 p2x = 2, p2y = 11: R = 11.1803398874989 p2x = 2, p2y = 12: R = 12.1655250605964 p2x = 2, p2y = 13: R = 13.1529464379659 p2x = 2, p2y = 14: R = 14.142135623731 p2x = 2, p2y = 15: R = 15.1327459504216 p2x = 2, p2y = 16: R = 16.1245154965971 p2x = 2, p2y = 17: R = 17.1172427686237 p2x = 2, p2y = 18: R = 18.1107702762748 p2x = 2, p2y = 19: R = 19.1049731745428 p2x = 2, p2y = 20: R = 20.0997512422418 p2x = 2, p2y = 21: R = 21.095023109729 p2x = 2, p2y = 22: R = 22.0907220343745 p2x = 2, p2y = 23: R = 23.0867927612304 p2x = 2, p2y = 24: R = 24.0831891575846 p2x = 2, p2y = 25: R = 25.0798724079689 p2x = 2, p2y = 26: R = 26.0768096208106 p2x = 2, p2y = 27: R = 27.0739727413618 p2x = 2, p2y = 28: R = 28.0713376952364 p2x = 2, p2y = 29: R = 29.0688837074973 p2x = 2, p2y = 30: R = 30.0665927567458 p2x = 2, p2y = 31: R = 31.0644491340181 p2x = 2, p2y = 32: R = 32.0624390837628 p2x = 2, p2y = 33: R = 33.0605505096331 p2x = 2, p2y = 34: R = 34.0587727318528 p2x = 2, p2y = 35: R = 35.0570962859162 p2x = 2, p2y = 36: R = 36.0555127546399 p2x = 2, p2y = 37: R = 37.0540146272978 p2x = 2, p2y = 38: R = 38.0525951808809 p2x = 2, p2y = 39: R = 39.0512483795333 p2x = 2, p2y = 40: R = 40.0499687890016 p2x = 2, p2y = 41: R = 41.0487515035476 p2x = 2, p2y = 42: R = 42.0475920832573 p2x = 2, p2y = 43: R = 43.0464865000618 p2x = 2, p2y = 44: R = 44.0454310910905 p2x = 2, p2y = 45: R = 45.0444225182208 p2x = 2, p2y = 46: R = 46.0434577328854 p2x = 2, p2y = 47: R = 47.0425339453563 p2x = 2, p2y = 48: R = 48.0416485978573 p2x = 2, p2y = 49: R = 49.0407993409569 p2x = 2, p2y = 50: R = 50.0399840127872 p2x = 2, p2y = 51: R = 51.0392006206994 p2x = 2, p2y = 52: R = 52.0384473250308 p2x = 2, p2y = 53: R = 53.0377224247045 p2x = 2, p2y = 54: R = 54.0370243444252 p2x = 2, p2y = 55: R = 55.0363516232681 p2x = 2, p2y = 56: R = 56.0357029044876 p2x = 2, p2y = 57: R = 57.0350769263968 p2x = 2, p2y = 58: R = 58.0344725141876 p2x = 2, p2y = 59: R = 59.0338885725818 p2x = 2, p2y = 60: R = 60.0333240792145 p2x = 2, p2y = 61: R = 61.0327780786685 p2x = 2, p2y = 62: R = 62.0322496770833 p2x = 2, p2y = 63: R = 63.0317380372777

You need the square root here. You can't get around it for finding the distance (which is what R is). I'm sure that a pattern exists between your results, but I'm also sure that the pattern is in terms of a square root

However, there are plenty of ways you can minimize the number of square roots you have to perform. For example, sqrt(7² + 5²) = sqrt(5² + 7²). In other words, if p2x = 5 and p2y = 7, then when p2x = 7 and p2y = 5, you get the same result! You only have to do the calculation for half the points and mirror it for the other half.

[edited by - Zipster on October 8, 2002 12:23:04 PM]

I dunno about that, it seems to me that the result for each number is in some sort of pattern that could be achieved using a simple multiplication and division formula, maybe... but maybe you''re right, i just hope not!!

Anyone else have a different oppinion (hopefully one that i want to hear )
- Tim

Use a lookup table.

Note that if f = 1.m*2^e (IEEE float format), then sqrt(f) = sqrt(1.m*2^e₀)*2^|e/2| where e₀ is the low bit of the exponent.

Also make sure you''re not squaring R later ...

Documents [ GDNet | MSDN | STL | OpenGL | Formats | RTFM | Asking Smart Questions ]
C++ Stuff [ MinGW | Loki | SDL | Boost. | STLport | FLTK | ACCU Recommended Books ]

ALSO, as it is i only use 1 sqrt function-call... but its used for every pixel, and i dont see a way around that. So i''d rather find a different way of getting the same result.

Ah, but you don''t have to do it for every pixel! Only half of them

Hey there''s a good idea for an optimization!!! Thanks!

STILL, if I can just do away with it altogether that would be GREAT

Store values of squares for x and y being prime numbers (ie 1, 2, 3, 5, 7, ...)

This should allow you to know all multiples of these numbers, for instance (4, 4), (4, 6), (4, 10)...

Indeed, R(kx, ky) = kR(x, y)

Better solution: Store values of x = prime, y and x prime with each other... this will allow you to get most numbers on other rows...

Best solution is a lookup table.

I see you are calculating a radius... What are you going to use it for? Maybe we could help further if we could mix both formulaes...

Extatica is coming soon!
Check it out on:
http://www.extatica.com02.com

You can not only speed up by factor two, but by factor eight.

given r(x,y) = sqrt((x*x)+(y*y)), this will be true, too:

r(x,y) = r(-x,y) = r(x, -y) = r(-x, -y) = r(y,x) = r(-y,x) = r(y,-x) = r(-y,-x)

squareroots on my pc have 5 cycles. so what?

"take a look around" - limp bizkit
www.google.com