# fastest way to calculate the sum of 1 to x

• 11-07-2010, 08:54 PM
imorio
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:

Code:

```public int addition(int input) {         int result=0         for(int i=1; i<=input; i++)         {                 result+=i;         }         return result; }```
Code:

```public int addition(int input) {         return (input*input+input)/2; }```
Code:

```public int addition(int input) {         return (input*(input++))/2; }```
The question boils down to, how does the '*' operator work?
• 11-07-2010, 09:03 PM
pbrockway2
The * operator multiplies two numeric quantities. But that's what is does, I have no idea how it works.

Quote:

I found 3 ways to do it
Code:

```public int addition(int input) {         return (input*(input++))/2; }```

Beware of stuff you find.

Quote:

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.

Quote:

The options are:

Oh no! I'm sure there are many more options.
• 11-07-2010, 09:45 PM
imorio
Quote:

Originally Posted by pbrockway2
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...-

Quote:

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.

Quote:

Oh no! I'm sure there are many more options.
Ofcourse, but these are the ones I found.
• 11-07-2010, 09:58 PM
pbrockway2
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?
• 11-07-2010, 10:08 PM
imorio
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:
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 }```
• 11-07-2010, 11:47 PM
pbrockway2
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.