function for summation

[Mellobuck]

Hello,

I am trying to find a single function that will perform the following function: for a given x, produce the sum of all the integers from 1 to x.

I know factorial will give me the product from 1 to x, but my memory for math functions escapes me on the sum, and it seems I will need the name of the concept before being able to search for the function...

I know of several ways to programmatically perform this, please see attached picture - the upper most branch was the existing code, and the lower two my (supposed) improvements to it. However, I feel that there ought to be one function, or a more elegant programming step, similar to the factorial, which performs all these steps at once, is this true?

Thanks,

Mello

Message Edited by Mellobuck on 04-28-2008 03:29 PM

[tst]

I don't feel like working out the whole mathematical proof, but I believe the formula is (0.5x+0.5)X.

[Daklu]

Summation is the correct operation but Labview does not support the mathematical notation as far as I know.  If you'll forgive the crude text format, roughly speaking the equation would be...

n

E(i)

i=1

I think your top vi is the best option, except I'd remove the Build Array primitive.  You don't need it and it will slow things down.

[johnsold]

If you put the increment function in line between x and the N terminal of the for loop, you only do the increment once. That should speed things up. The array has a zero element but that does not change the sum. I benchmarked the sum of array elements versus the shift register plus i. The shift register method is about 25% faster.

Lynn

[tst]

OK, proof by recursion:

1. The operation is correct for x=1.
2. Check correctness for x+1.

• 1+2...+x=(0.5x+0.5)x
• 1+2...+x+x+1=(0.5x+0.5+0.5)(x+1)
• Replace the first part on the left with our equation:
• (0.5x+0.5)x+x+1=(0.5x+0.5+0.5)(x+1)
• 0.5xx+1.5x+1=0.5xx+x+0.5x+1

3. The two are equal, so the proof works for x+1 and since it works for x=1, it also works for any other positive integer.

Message Edited by tst on 04-29-2008 12:03 AM

[Daklu]

Ahh, but did you benchmark tst's solution?  My money's on him. 

----------------

Assuming you want to sum all integers between 1-100, a more intuitive proof is...

0 + 100 = 100

1 + 99 = 100

2 + 98 = 100

3 + 97 = 100

  .

  .

  .

49 + 51 = 100

The above is simplified as 50 * 100, or 0.5*n*n.  The only number remaining is 50, or 0.5*n.

Therefore, the sum of integers 1-n is equal to 0.5*n*n + 0.5*n, or equivalently, n(0.5n+0.5).

Message Edited by Daklu on 04-28-2008 02:10 PM

[Mellobuck]

Thank you both for the explicit mathematical solutions. I refactored it to:

sum=(x+1)x*0.5

for implementation, but It works quite well. Kudos and 5-stars for you both!

-Mello says math is fun

[tst]

---

Mellobuck wrote:

I refactored it to:

sum=(x+1)x*0.5

---

Yes, I realized that's also correct and is much more elegant shortly after I left the computer. It also gives you the added benefit that you can use pure integer math by using Q&R or even bit shifting for performance and a clean diagram.

Another point is that the method I used is obviously called induction, not recursion. Don't know what I was thinking about. That's what you get when you do things in a hurry.

---

Daklu wrote:

Assuming you want to sum all integers between 1-100, a more intuitive proof is...

---

I don't think that can be considered a mathematical proof, since you only show it on a single number. You have to do it with n and show that it's correct.

[GerdW]

Hi Mellobuck,

the formula is the better approach here, but do you see the difference in these two implementations shown in the attachment?



(Infact this was my first thought when I saw your "existing code"...)

Message Edited by GerdW on 04-29-2008 09:44 AM

[Mellobuck]

GerdW,

Oh, absolutely. Don't want to be iterating numbers within a loop if not necessary, although incrementing once before the count(N) terminal (as above) seems even more elegant.

Plus I knew that build array in the loop was useless and an extra visit to the memory manager on each iteration.

Mea culpa: The code with the build array within it was given to me from an older project, but I was the one who left the increment inside the loop in the second, my main aim was to eliminate the array. Thanks again to everyone for the help.

-Mello