Maths trick: doing fewer comparisons

Note: this is not an optimisation. It is just one more tool you should have in your toolbox when looking for optimisations. It may be useful.

This is the trick:

\[\min(x,y) = \dfrac{x + y - |x - y|}{2}\]
\[\max(x,y) = \dfrac{x + y + |x - y|}{2}\]

You can check for yourself that it is always true: when x > y, |x - y| is the same as x - y, etc.

What good is it for? There is often an implicit comparison in min or max. It might be interesting to replace it with a call to the branchless fabs.

Example usage

Consider the following code:

float a, b, c, d;
/* ... */
return (a > b) && (c > d);

That kind of code is often used eg. in collision checks, where a lot of tests can be done. This code does two comparisons. On some architectures, this means two branches. Not always something you want.

The test condition is equivalent to:

(a - b > 0) && (c - d > 0)

Now when are two given numbers both positive? That is if and only if the smallest is positive:

min(a - b, c - d) > 0

We may now use our trick:

(a - b) + (c - d) - |(a - b) - (c + d)| > 0

And so the code could be rewritten as such:

float a, b, c, d;
/* ... */
return (a - b) + (c - d) > fabsf((a - b) - (c - d));

We basically replaced the additional test with a call to fabsf and some additions/subtractions. It may be possible to reorganise the input data so that this second version performs better.

Comments

1. anonymous -- 2013-02-09 21:42

Thanks for this nice math trick. I am using something very similar in Matlab.. Tom

3. online -- 2016-12-05 15:00

So http://indian10cia.com/ , soft tabs generic don t blame unbelievers for how they feel.

24. cialis -- 2017-01-17 11:00

Must have a prescription for http://www.cheapills1c.com/ , .

25. JoshuaSom -- 2017-07-14 01:01

<a href=http://buyxvardenafil.com/>buy generic vardenafil </a> vardenafil buy online <a href=" http://buyxvardenafil.com/ ">buy vardenafil </a> vardenafil review

26. Willielep -- 2017-07-14 07:51

<a href=http://buyvpropecia.com/>buy propecia uk </a> where can i buy cheap propecia <a href=" http://buyvpropecia.com/ ">buy generic propecia online </a> buy propecia

27. JeffreyHaitA -- 2017-07-14 08:02

<a href=http://buyvmetformin.com/>buy metformin online </a> where to buy metformin <a href=" http://buyvmetformin.com/ ">buy metformin 500mg </a> can i buy metformin online

28. Danielliaks -- 2017-07-14 08:16

<a href=http://buyvclomid.com/>where to buy nolva and clomid </a> clomid buy online usa <a href=" http://buyvclomid.com/ ">where to buy clomid </a> buy clomid with no prescription

29. ScottLof -- 2017-07-18 02:11

<a href=http://howtoplayxblackjack.org/>play blackjack for free </a> play blackjack online for free <a href=" http://howtoplayxblackjack.org/ ">play free blackjack </a> play blackjack online free

34. Jordonkal -- 2017-07-20 16:11

<a href=http://bestonlinexslots.org/>vegas online slots </a> free online slots with bonuses <a href=" http://bestonlinexslots.org/ ">double down free online slots </a> free slots online

35. Williamgiz -- 2017-07-20 21:50

<a href=http://orderxmodafinil.com/>order modafinil online </a> order modafinil online india <a href=" http://orderxmodafinil.com/ ">order modafinil from india </a> order modafinil from india

36. Robertethef -- 2017-07-20 21:54

<a href=http://orderxxanax.com/>order xanax from canada </a> what happens to you if you order xanax online <a href=" http://orderxxanax.com/ ">order xanax bars online overnight </a> order xanax online

37. JerryMup -- 2017-07-20 22:11

<a href=http://buyxxanax.com/>buy xanax online with a prescription </a> buy xanax online no perscription <a href=" http://buyxxanax.com/ ">buy xanax no prescription </a> buy 2mg xanax online

38. MarvinBiags -- 2017-07-21 08:30

<a href=http://orderxtramadol.com/>tramadol order by mail </a> order tramadol free shipping <a href=" http://orderxtramadol.com/ ">order tramadol online without script </a> order tramadol online without prescription

39. Williamgiz -- 2017-07-21 08:30

<a href=http://orderxmodafinil.com/>order modafinil online usa </a> order modafinil online risk <a href=" http://orderxmodafinil.com/ ">order online modafinil mexico </a> order modafinil from india

40. Robertethef -- 2017-07-21 08:31

<a href=http://orderxxanax.com/>order xanax bars online </a> xanax order canada <a href=" http://orderxxanax.com/ ">buy xanax with money order </a> order xanax

41. Alfredsag -- 2017-07-21 08:31

<a href=http://cheapxxanax.com/>buy cheap xanax overnight shipping online </a> cheap xanax pill press <a href=" http://cheapxxanax.com/ ">cheap xanax for sale online </a> cheap xanax

42. BryanMisee -- 2017-07-21 08:31

<a href=http://buyxmodafinil.com/>best place to buy modafinil </a> how to buy modafinil <a href=" http://buyxmodafinil.com/ ">buy modafinil australia </a> smart drugs modafinil buy online

43. LarryPsync -- 2017-07-21 08:31

<a href=http://buyvtramadol.com/>buy tramadol online uk </a> buy tramadol online <a href=" http://buyvtramadol.com/ ">buy tramadol 50mg </a> best place to buy tramadol online

44. JerryMup -- 2017-07-21 08:32

<a href=http://buyxxanax.com/>where can i buy xanax </a> buy xanax online <a href=" http://buyxxanax.com/ ">how to buy real xanax online </a> buy xanax without doctor consultation

45. BobbyMeept -- 2017-07-21 08:32

<a href=http://buyxphentermine.com/>where can i buy phentermine online </a> where to buy phentermine online <a href=" http://buyxphentermine.com/ ">buy real phentermine online </a> where can i buy phentermine on line

46. Donaldmag -- 2017-07-21 21:00

<a href=http://orderprednisonexonline.com/>can i order prednisone online </a> order prednisone online <a href=" http://orderprednisonexonline.com/ ">order prednisone overnight </a> order prednisone for dogs

47. Michaelunlok -- 2017-07-21 21:01

<a href=http://xenicalxcost.com/>xenical 120 mg price uk </a> cost of xenical pills <a href=" http://xenicalxcost.com/ ">xenical price </a> buy xenical online cheap

48. Larrycus -- 2017-07-21 23:31

<a href=http://buyxclomid.com/>buy clomid online </a> where to buy nolva and clomid <a href=" http://buyxclomid.com/ ">clomid buy </a> clomid buy

67. Georgepenue -- 2017-08-19 10:38

how to order levitra online <a href="http://levitramqo.com/#">levitra price</a> buy levitra australia <a href=http://levitramqo.com/#>levitra online</a> cheap generic levitra online

Add New Comment