6

How can I speed-up this loop (in C)?

unsigned int x = 50000000;
double a= 0.9;
double b= -0.9;
for ( unsigned int i = 1; i <= x; i++)
{
    a *= 0.9; //power
    b -=  a/i;
}

Execution time: 14.000 s

I don't know why, but when I add this 2 lines in code, execution time is only 1.000 s. 

unsigned int x = 50000000;
double a= 0.9;
double b= -0.9;
for ( unsigned int i = 1; i <= x; i++)
{
    a *= 0.9; //power
    a += 10e250;
    a -=10e250;
    b -=  a/i;
}

Thanks for any help

Mysticial
  • 464,885
  • 45
  • 335
  • 332
Joozty
  • 460
  • 2
  • 12
  • 40
  • Just guessing but 10e250 cause overflow which can end in having "a" equal zero. Which is probably faster to divide. What is value of "a" before executing `b -= a/i;`? – libik Nov 25 '15 at 11:34
  • http://stackoverflow.com/questions/9314534/why-does-changing-0-1f-to-0-slow-down-performance-by-10x/9314926#9314926 –  Nov 25 '15 at 23:01

2 Answers2

6

First, the most likely reason why your code is running slower than expected is that a becomes a denormalised number. And denormalised numbers are a special case that may run a lot, lot slower. It is also possible that by adding 10^251 and subtracting it again you change a to 0 and dividing zero by anything is faster (since the result doesn't need to be calculated).

But the real speed up comes from not stupidly adding tiny, tiny numbers that have no effect whatsoever. When x = a few hundred, a will be so small that subtracting a/i from b will not make any difference. So instead of b -= a/i; you write

double old_b = b;
b -= a / i;
if (b == old_b) break;

and your time will change from seconds to much less than a millisecond.

gnasher729
  • 51,477
  • 5
  • 75
  • 98
0

Adding that 10e250 it exceeds the limit of digits the double variable can support and when subtracting it will always become 0. Not sure about this but multiplication should take more time than addition so it's slowing it down, ex. if you try this :

for ( unsigned int i = 1; i <= x; i++)
{
  a ++; //power
  b -=  a/i;
}

You will see that it will run like the second time. I guess that when you add that 10e250 and after making a = 0; the multiplication with 0 is faster then with other non-zero variable.

Ardit Meti
  • 571
  • 5
  • 22
  • 1
    On modern processors, all multiplications take the same amount of time unless there's denormals involved. So multiplication by zero is not faster than multiplication by anything else. – Mysticial Nov 25 '15 at 15:52
  • Yea I wasn't sure about that. How can you explain that changing that line: a*=0.9; to a++; makes it faster? – Ardit Meti Nov 25 '15 at 16:40