Summation on HP 42S

[lrdheat]

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?

[Didier Lachieze]

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.

[lrdheat]

Thanks! Amazing how I could make an easy problem so contorted!

[lrdheat]

100 in Y.

[ijabbott]

You could cheat:

Code:

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

Thanks to Gauss!

[Thomas Klemm]

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

[lrdheat]

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

[lrdheat]

Summation of same (x^2 - 3*x) using summation function on WP 34S takes ~3 seconds.

[Didier Lachieze]

(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.

[lrdheat]

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!

[Thomas Klemm]

(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*}\)

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 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

[Thomas Klemm]

(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

[Albert Chan]

(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

[Thomas Klemm]

(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 …

[pier4r]

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.

[Albert Chan]

(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.

[burkhard]

(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. :-)

[Frido Bohn]

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

[John Keith]

(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.

[Dieter]

(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