2

When i do like this, it works well in my code...

...

for (i = 2; i <= sqrt(500000); i++)

...

But do like

for (i = 2; i < sqrt(500000) + 1; i++)

executes after compile, error occurs saying Segmentation fault (core dumped).

for loop body is:

for (i = 2; i <= sqrt(500000); i++) {
        summation[i * i] += i;
        for (j = i + 1; j <= 500000 / i; j++) {
            summation[i * j] += (i + j);
        }
    }

Is there any difference between the two for loops? Thanks

Jason
  • 3,237
  • 4
  • 26
  • 28

5 Answers5

8

Your second loop run once more: 500000 is not a perfect square, so i < sqrt(500000) and i <= sqrt(500000) are always equal and the +1 ensure another iteration.

AProgrammer
  • 51,233
  • 8
  • 91
  • 143
  • Yeap, that's the real answer. – sharptooth Mar 14 '11 at 11:01
  • 1
    @sharptooth the really real answer is to use `i*i <= 500000` – Jim Balter Mar 14 '11 at 17:14
  • @Jim Balter Thanks for your tip. – Jason Mar 15 '11 at 02:42
  • @Jim, pulling the computation of sqrt(500000) and keeping out of the loop is probably more benefical. – AProgrammer Mar 15 '11 at 08:43
  • 1
    @Jim, what makes you think that computing 700 or so multiplications are less costly than a single square root? Let's measure. `for (int i = 2; i < sqrt(argument) + 1; i++)` gave 8.0 micro seconds, for ` for (int i = 2; i < limit; ++i)` (with limit an int obviously) gave 0.76 micro seconds and for `for (int i = 2; i*i < argument; ++i)` gave 0.83 micro seconds. Looking at asm, I see no unwanted optimizations (well, for the final version; I learned that gcc was able to evaluate sqrt(constant) at compile time...). – AProgrammer Mar 15 '11 at 09:55
  • @Aprogrammer "what makes you think" -- Strawman. `i*i` is already calculated in the OP's loop. Too bad you didn't look at that. – Jim Balter Mar 15 '11 at 10:26
  • @JimBalter: Too bad you didn't actually explain that, rather than just saying "no, probably not" -- and, in fact, that you didn't explain that your recommendation was specific to this case where that was already calculated rather than being a general guideline. – Brooks Moses Feb 11 '12 at 19:50
  • @Brooks Too bad you're just trolling a year old conversation ... Here's what you don't get: AProgrammer wrote that something was "probably" true without providing any justification for it ... without doing any actual measurement or analysis of the code. People toss around the word "probably" to shore up their ungrounded opinions. My brief comment was an implicit criticism of that bad behavior. – Jim Balter Feb 24 '12 at 02:22
3

sqrt() will return a floating point number, so all comparisons are done for floating-point numbers and they are imprecise by design, so those two comparisons above can yield different results and thus in one of cases you'll have off-by-one and undefined behavior.

Community
  • 1
  • 1
sharptooth
  • 167,383
  • 100
  • 513
  • 979
1

I've tried your code with gcc 4.3.4 under cygwin.

  • In the first case, i loops up to 707.
  • In the second case, i loops up to 708.

I bet that this last value triggers a buffer overflow somewhere in the body of the loop.

mouviciel
  • 66,855
  • 13
  • 106
  • 140
1

As others have already explained, the + 1 causes the loop to iterate once too often. Then summation[i * i] or summation[i * j] accesses beyond the allocated size of summation. The solution is to either increase the allocated size accordingly or make sure that the condition is correct (not doing + 1) and you thus do not run over the end of the array.

But also, like others already said, you should not use a floating point value (result of sqrt) with an integer comparison as floating point values are... tricky. I'm not sure whether in this case the int gets casted to float or vice versa, but whichever way it's not the right thing to do.

DarkDust
  • 90,870
  • 19
  • 190
  • 224
-2

did you try this?

for (i = 2; i < (sqrt(500000) + 1); i++)

Is your i a floating pont variable?

Vijay
  • 65,327
  • 90
  • 227
  • 319