Thread: fastest way to calculate the sum of 1 to x

1. Senior Member
Join Date
Aug 2010
Posts
127
Rep Power
0

fastest way to calculate the sum of 1 to x

Hi, I'm making methode that adds all the numbers from 0 to the input. So if the input is 5, the methode returns 15 (=1+2+3+4+5). I found 3 ways to do it and was wondering what the most efficient one is. The options are:

Java Code:
```public int addition(int input)
{
int result=0
for(int i=1; i<=input; i++)
{
result+=i;
}
return result;
}```
Java Code:
```public int addition(int input)
{
return (input*input+input)/2;
}```
Java Code:
```public int addition(int input)
{
return (input*(input++))/2;
}```
The question boils down to, how does the '*' operator work?

2. Moderator
Join Date
Feb 2009
Location
New Zealand
Posts
4,712
Rep Power
15
The * operator multiplies two numeric quantities. But that's what is does, I have no idea how it works.

I found 3 ways to do it
Java Code:
```public int addition(int input)
{
return (input*(input++))/2;
}```

Beware of stuff you find.

and was wondering what the most efficient one is

You could write some code, I suppose, and time it. This turns out to be quite a difficult undertaking. You might want to seriously question whether it matters.

The options are:

Oh no! I'm sure there are many more options.

3. Senior Member
Join Date
Aug 2010
Posts
127
Rep Power
0
Originally Posted by pbrockway2
Java Code:
```public int addition(int input)
{
return (input*(input++))/2;
}```

Beware of stuff you find.
Did I make a mistake?
-edit: I'm an idiot...-

You could write some code, I suppose, and time it. This turns out to be quite a difficult undertaking. You might want to seriously question whether it matters.
I'm teaching myself for the moment and since in industry these things are very important, it seemed a fun thing to find out.

Oh no! I'm sure there are many more options.
Ofcourse, but these are the ones I found.

4. Moderator
Join Date
Feb 2009
Location
New Zealand
Posts
4,712
Rep Power
15
Personally I'd favour "return (input * (input + 1)) / 2;" but that's mostly because I know what it means when I see it. That raises a nice question about what "effeciency" means: do only cpu cycles matter? Or does the programmer's brain - or the programmers' brains if it is going to be maintained by a group of peope - count for something?

And then there's the question of what context it will be used in. After all - as the post increment thing shows - it has to be valid before it has any effeciency whatsoever. So will we have big integers with the danger of overflow? Do we expect negative values for input?

5. Senior Member
Join Date
Aug 2010
Posts
127
Rep Power
0
Fixing that isn't a problem. First find n in: (n*n+n)/2=d, where d is the largest possible positive value ints can have (around 2 billion). Then round n up and add an if-statement:
Java Code:
```if(input>=n||input<0)
{
return -1;//to show the methode can't work with that input
}
else
{
//one of the options of my first post
}```

6. Moderator
Join Date
Feb 2009
Location
New Zealand
Posts
4,712
Rep Power
15
Yes - but I wasn't really saying either circumstance was a problem. My point was that the method description - "adds all the numbers from 0 to the input" - would need to be clarified a little before accepting a proposed implementation as valid. And that efficiency presupposes validity.

So validity certainly is a more pressing concern than efficiency. You haven't addressed it, but maintainability might also be.

And here's a third. Supposed a user is entering input in the applications gui, then finding their mouse and clicking "OK" at which point we display the sum and allow them to enter another number. We can save all the picoseconds there are to be saved by efficient code ... but the program won't run any faster! The limiting factor lies elsewhere: in the gui, in the database, in the network or disk access etc. So there's another context hat must be take into account before "efficiency" is even meaningful.

It's not that I'm saying efficiency doesn't matter. But perhaps other things do. And perhaps they are more pressing.

Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•