Understanding sum/product algorithms

[Hobold]

Understading sum/product algorthms

Hello there,

I'm having a little trouble understanding sum/product algorithms. I can do single sum/product algorithms, but when it comes to multiple/combined summations or products I just can't follow.

Ex.:

\sum_{i=0}^n (a_i x + c_i)

Ok, this one was pretty simple, I have no problem in doing that. Though when it comes to things like

\sum_{i=0}^n \left ( \prod_{j=0}^i (a_i x + c_i) \right )

it gets hard. I have made a few algorithms, though I have no idea if they are right. I assume you can write using only one loop, but I have no idea how. Here's what I'd write for that one:

z = 0; y = 1;

for i = 0 to n do

   for j = 0 to i do
      z = z + a[i] * x + c[i];
   end for

   y = y*z;

end for

I can't work the other way around as well. When I notice some algorithm results in combined product/sum notation, I can't write it right, such as

v = a[0];
z = x;

for i = 1 to n do
   v = v +z*a[0];
   z = x*z;
end for

Could anyone help me understand? Or at least suggest any book or text on these?

 

[rcgldr]

The inner loop is a product loop, you should initialize z = 1, and then each step should be z = z * ... or the alternate form z *= ... . The outer loop is a summation, so initialze y = 0, and each step should be y = y + ... or y += ...

 

[Xitami]

sum:=0
for i:=0 to n do
	prod=1
	for j:=0 to i do
		prod:= prod * (a[i]*x + c[i])  // i?
	sum:= sum + prod

 

[Hobold]

Thanks, I got that...

What would

v = a[0];
z = x;

for i = 1 to n do
   v = v +z*a[0];
   z = x*z;
end for

be in sum/product notation?

I am curretly using "Numerical Mathematics and Computing" by W. Cheney and D. Kincaid. Though it doesn't explain anything about those algorithms, there are some exercises in which the authors ask you to transform from notation -> algorithm and vice-versa. In the answer section, there are answers I cannot interpret such as:

z = b[n] + 1;

for k = 1 to n-2 do
   z = z*b[n-k] + 1;
end for

stands for z = 1 + \sum_{i=2}^n \prod_{j=2}^i b_j

I have really no idea on how the author got to that answer.

 

[rcgldr]

I have really no idea on how the author got to that answer.

Try manually writing out the calculated terms for the first few loops, and you'll see why it works. As to how he figured it out, either he's clever or he copied the technique from yet another clever person.

z = b[n] + 1
z = (b[n] + 1) (b[n-1]) + 1 = b[n] b[n-1] + b[n-1] + 1
z = (b[n] b[n-1] + b[n-1] + 1) (b[n-2) + 1 = b[n] b[n-1] b[n-2] + b[n-1] b[n-2] + b[n-2] + 1
z = ...