# HP Forums

Full Version: Summation on HP 42S
You're currently viewing a stripped down version of our content. View the full version with proper formatting.
Pages: 1 2 3
I tried doing a simple summation of "x" from 1 to 100. I got it to work, and correctly come up with an answer of 5050. There must be a simpler way than the contorted way that I did.

Here's my program:

LBL "SUM"
1.1
STO "T"
0
ENTER
LBL "COUNT"
RCL "X"
ENTER
1
+
STO "X"
+
+
ISG "T"
GTO "COUNT"
.END.

I begin by storing 0 into "X".

What is a better way to accomplish this?
Code:
01 LBL "SUM" 02 0 03 LBL 00 04 RCL+ ST Y 05 DSE ST Y 06 GTO 00 07 END

Start with the end value in X: 100 XEQ "SUM" will do the sum of x from 100 down to 1 and return 5050.
Thanks! Amazing how I could make an easy problem so contorted!
100 in Y.
You could cheat:

Code:
LBL "SUM" X^2 LASTX + 2 / END

Thanks to Gauss!
A somewhat different approach using ∑+:
Code:
00 { 10-Byte Prgm } 01 CL∑ 02 0 03▸LBL 00 04 ∑+ 05 X≤Y? 06 GTO 00 07 SUM 08 END

Or then for $$n>0$$ simply:
Code:
00 { 7-Byte Prgm } 01 1 02 + 03 2 04 COMB 05 END

Cheers
Thomas
Neat stuff. For something a little more complex such as summation 1 through 100 of x^2 - 3*x,

I used the idea from post 2

LBL "SUM"
0
LBL 00
RCL "T"
X^2
STO+ "X"
RCL "T"
3
*
STO- "X"
RCL "T"
DSE "T"
GTO 00
RCL "X"
.END.

Store 100 in "T", 0 in "X", Produces 323,200 in ~25 seconds
Summation of same (x^2 - 3*x) using summation function on WP 34S takes ~3 seconds.
(09-23-2018 06:51 PM)lrdheat Wrote: [ -> ]100 in Y.

No, I 'm using the stack registers X & Y, not variables "X" or "Y". So before calling the program you enter 100 (it's in the stack register X), at step 02 in the program 0 is enter in the stack register X and 100 is pushed to stack register Y which is then used by the two other instructions: RCL+ ST Y and DSE ST Y.

(09-23-2018 09:25 PM)lrdheat Wrote: [ -> ]Neat stuff. For something a little more complex such as summation 1 through 100 of x^2 - 3*x,

I used the idea from post 2
[...]
Store 100 in "T", 0 in "X", Produces 323,200 in ~25 seconds

Here is a shorter way to do it. 100 XEQ SUM returns 323200 in ~11 seconds.

Code:
01 LBL "SUM" 02 0 03 LBL 00 04 RCL ST Y 05 3 06 - 07 RCL* ST Z 08 + 09 DSE ST Y 10 GTO 00 11 END

At step 04 we have the current sum in X and the current value of x in Y, so we recall Y to calculate x-3.
At step 07 we have x-3 in X, the current sum in Y and the current value of x in Z, so we recall and multiply Z to X to get x*(x-3) which is x^2 - 3*x. Then with + we get the updated sum in X and x moves down from Z to Y.

For more complex functions it may not be possible to use only the stack so variables may be needed to store x and the sum but with the stack it's generally shorter and faster.

Note: in your program you can remove the RCL "T" before the DSE, it's useless.
Thanks! I'm learning, thrilled that this mind can put something together that works, even if it is far from concise. Maybe conciseness will eventually follow!
(09-23-2018 09:25 PM)lrdheat Wrote: [ -> ]For something a little more complex such as summation 1 through 100 of x^2 - 3*x,

Let us rewrite this expression as:

\begin{align*} x^2 - 3x &= x^2 - x - 2x \\ &= x(x-1) - 2x \\ &= 2\frac{x(x-1)}{2} -2\frac{x}{1} \\ &= 2\binom{x}{2} - 2\binom{x}{1} \end{align*}

$$\sum_{x=1}^{n} 2\binom{x}{2} - 2\binom{x}{1} = 2\binom{n+1}{3} - 2\binom{n+1}{2} = 2\left ( \binom{n+1}{3}-\binom{n+1}{2} \right )$$

This program can be used to calculate the sum:
Code:
00 { 18-Byte Prgm } 01 1 02 + 03 RCL ST X 04 3 05 COMB 06 X<>Y 07 2 08 COMB 09 - 10 2 11 × 12 END

Quote:Produces 323,200 in ~25 seconds

I haven't tested but I assume it's a bit faster than that.

Cheers
Thomas
(09-23-2018 09:25 PM)lrdheat Wrote: [ -> ]I used the idea from post 2

Code:
LBL "SUM" 0 LBL 00 RCL "T" X^2 STO+ "X" RCL "T" 3 * STO- "X" RCL "T" DSE "T" GTO 00 RCL "X" .END.

Store 100 in "T", 0 in "X", Produces 323,200 in ~25 seconds

(09-23-2018 10:03 PM)Didier Lachieze Wrote: [ -> ]Note: in your program you can remove the RCL "T" before the DSE, it's useless.

Another note: The 0 in the 2nd line is useless as well.
Unless you store it to initialise variable "X".
You might also store the X register of the stack to "T":

Code:
LBL "SUM" STO "T" 0 STO "X" LBL 00 RCL "T" …

This allows to run:

100
XEQ "SUM"

So you don't have to initialise variables "T" and "X".

Cheers
Thomas
(09-24-2018 12:56 AM)Thomas Klemm Wrote: [ -> ]The summation leads to:

$$\sum_{x=1}^{n} 2\binom{x}{2} - 2\binom{x}{1} = 2\binom{n+1}{3} - 2\binom{n+1}{2} = 2\left ( \binom{n+1}{3}-\binom{n+1}{2} \right )$$

This almost look like integration !
Any reference to show it is always true ?

I normally just fit the data to search for the formula (assume I don't cheat by googling)
For sum(x^2 - 3*x), formula should be a cubic, with no constant term (sum=0 when n=0)

Try:
n = 1, sum = (1^2 - 3) = -2
n = 2, sum = -2 + (2^2 - 3*2) = -4
n = 3, sum = -4 + (3^2 - 3*3) = -4

3 equations, 3 unknowns (cubic coefficients), we get sum = n^3/3 - n^2 - 4/3*n

So, for n = 100, sum = n/3 * (n^2 - 3*n - 4) = 100/3 * 9696 = 323200
(09-24-2018 11:56 AM)Albert Chan Wrote: [ -> ]This almost look like integration !
Any reference to show it is always true ?

Just have a look at the definition of Pascal's triangle:

$${n \choose k}={n-1 \choose k-1}+{n-1 \choose k}$$

Or then just check the diagonals.
E.g. for $$k=2$$ the partial sum of the first elements is just below on the next line:

1 = 1
1 + 3 = 4
1 + 3 + 6 = 10
1 + 3 + 6 + 10 = 20
1 + 3 + 6 + 10 + 15 = 35

Quote:I normally just fit the data to search for the formula (assume I don't cheat by googling)
For sum(x^2 - 3*x), formula should be a cubic, with no constant term (sum=0 when n=0)

Try:
n = 1, sum = (1^2 - 3) = -2
n = 2, sum = -2 + (2^2 - 3*2) = -4
n = 3, sum = -4 + (3^2 - 3*3) = -4

3 equations, 3 unknowns (cubic coefficients), we get sum = n^3/3 - n^2 - 4/3*n

So, for n = 100, sum = n/3 * (n^2 - 3*n - 4) = 100/3 * 9696 = 323200

You might be interested in Newton's Forward Difference Formula:

$$f(x+a)=\sum_{n=0}^\infty{a \choose n}\Delta^nf(x)$$

Quote:the formula looks suspiciously like a finite analog of a Taylor series expansion

So for the given example we get:

x: 0 1 2 3 …
f: 0 -2 -4 -4 …
∆f: -2 -2 0 …
∆²f: 0 2 …
∆³f: 2

And so with $$x=0$$ we end up with: $$f(a)=2{a \choose 3} - 2{a \choose 1}$$

This leads to an even shorter program:
Code:
00 { 11-Byte Prgm } 01 RCL ST X 02 3 03 COMB 04 X<>Y 05 - 06 2 07 × 08 END

Conclusion: We don't really have to solve the linear system of equations.

Kind regards
Thomas

We don't even have to calculate the sum f but can only calculate ∆f:

x: 0 1 2 3 …
f: 0
∆f: -2 -2 0 …
∆²f: 0 2 …
∆³f: 2
for sum(x^2 - 3*x)

one could actually do:
sum(x^2 ) (closed formula) minus
3*sum(x) (closed formula).

namely here: https://brilliant.org/wiki/sum-of-n-n2-or-n3/

PS: brilliant has so much potential that they don't use. So many interesting problems buried by a poor layout sometimes.
(09-24-2018 01:52 PM)Thomas Klemm Wrote: [ -> ]
Quote:I normally just fit the data to search for the formula (assume I don't cheat by googling)
For sum(x^2 - 3*x), formula should be a cubic, with no constant term (sum=0 when n=0)

Try:
n = 1, sum = (1^2 - 3) = -2
n = 2, sum = -2 + (2^2 - 3*2) = -4
n = 3, sum = -4 + (3^2 - 3*3) = -4

3 equations, 3 unknowns (cubic coefficients), we get sum = n^3/3 - n^2 - 4/3*n

So, for n = 100, sum = n/3 * (n^2 - 3*n - 4) = 100/3 * 9696 = 323200

You might be interested in Newton's Forward Difference Formula:

I could never remember Forward Difference formula, without looking up.
Instead, I use the Lagrange formula, which work for uneven intervals too.

The formula look complicated, but it is very mechanical, easy to remember.
Fitting a cubic sum = n * quadratic,

sum / n
= (-2/1) $$(n-2)(n-3)\over(1-2)(1-3)$$ + (-4/2) $$(n-1)(n-3)\over(2-1)(2-3)$$ + (-4/3) $$(n-1)(n-2)\over(3-1)(3-2)$$
= -(n-2)(n-3) + 2(n-1)(n-3) - (2/3)(n-1)(n-2)
= (-n^2 + 5 n - 6) + (2 n^2 - 8 n + 6) + (-2/3 n^2 + 2 n - 4/3)
= n^2/3 - n - 4/3

sum = n * (n^2/3 - n - 4/3) = n/3 * (n^2 - 3 n - 4) = n(n+1)(n-4) / 3

Edit: Forward Difference Formula is very neat, without even evaluate sums.
(09-23-2018 07:40 PM)ijabbott Wrote: [ -> ]You could cheat:

<code snipped out>

Thanks to Gauss!

Excellent! I don't consider it a cheat at all. The problem said to add up the numbers from 1 to 100 (or whatever). Gauss's solution (which you nicely implemented) is compact, efficient, and much faster than the more obvious way (and least on paper or human brain... not sure for computers/calculators).

I was going to chime in with the classic story of Gauss's youthful brilliance here, but I assume most of the people (who humble me greatly) on this forum already know it. If not, look it up. It's one of my dad's favorite stories to tell young people. :-)
Challenge!

Write a program that multiplies natural numbers from 1 to 1000 (factorial) and overcomes the range limit of the HP42S. (The decimal approximation is a fully acceptable result.)

Cheers!
Frido
(09-25-2018 12:58 PM)burkhard Wrote: [ -> ]Gauss's solution (which you nicely implemented) is compact, efficient, and much faster than the more obvious way (and least on paper or human brain... not sure for computers/calculators).

This is true for computers if you want to calculate one such triangular number, which is the summation of the integers 1 through n. If you want a list of all triangular numbers from 1 through n (aka a cumulative sum), then the straightforward summation is faster because computing each new value requires only one addition.
(09-25-2018 01:59 PM)Frido Bohn Wrote: [ -> ]Write a program that multiplies natural numbers from 1 to 1000 (factorial) and overcomes the range limit of the HP42S. (The decimal approximation is a fully acceptable result.)

Simple. Add the (base 10) logs of 1...1000. The integer part of the sum is the tens exponent, 10^(fractional part) is the mantissa.

Code:
01 LBL "FCT" 02 0 03 LBL 01 04 RCL ST Y 05 LOG 06 + 07 DSE ST Y 08 GTO 01 09 IP 10 LASTX 11 FP 12 10^x 13 END

On Free42 (with 34 digit accuracy) this yields

2567
4,02387260077

So the result is 4,02387260077 E+2567.

Dieter
Pages: 1 2 3
Reference URL's
• HP Forums: https://www.hpmuseum.org/forum/index.php
• :