Results 1 to 6 of 6
  1. #1
    imorio is offline Senior Member
    Join Date
    Aug 2010
    Posts
    127
    Rep Power
    0

    Default 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. #2
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,565
    Rep Power
    12

    Default

    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. #3
    imorio is offline Senior Member
    Join Date
    Aug 2010
    Posts
    127
    Rep Power
    0

    Default

    Quote Originally Posted by pbrockway2 View Post
    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. #4
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,565
    Rep Power
    12

    Default

    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. #5
    imorio is offline Senior Member
    Join Date
    Aug 2010
    Posts
    127
    Rep Power
    0

    Default

    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. #6
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,565
    Rep Power
    12

    Default

    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.

Similar Threads

  1. What's the fastest way to store data?
    By gilbertsavier in forum JDBC
    Replies: 0
    Last Post: 08-05-2009, 10:41 AM
  2. How do you test the fastest methods?
    By MuslimCoder in forum New To Java
    Replies: 4
    Last Post: 02-09-2009, 03:34 PM
  3. Replies: 1
    Last Post: 12-28-2008, 10:25 AM
  4. calculate fft
    By ram.west in forum Advanced Java
    Replies: 2
    Last Post: 08-27-2008, 03:05 AM
  5. Calculate what e1 and e2 should be
    By Legoland in forum New To Java
    Replies: 11
    Last Post: 07-02-2007, 06:01 PM

Posting Permissions

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