Re: A programming puzzle.

*To*: mathgroup at smc.vnet.net*Subject*: [mg60845] Re: [mg60810] A programming puzzle.*From*: János <janos.lobb at yale.edu>*Date*: Fri, 30 Sep 2005 03:57:12 -0400 (EDT)*References*: <200509290941.FAA01111@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

On Sep 29, 2005, at 5:41 AM, jackgoldberg at comcast.net wrote: > Hello everyone, > > I have a simple problem for which I would like an "elegant" > solution. The problem is to convert the series > > a1*b1 + a2*b2 + a3*b3 + ... + an*bn > > into the equivalent series > > a1(b1 - b2) + (a1+a2)(b2 - b3) + ... +(a1 + a2 + ... + an-1)(bn-1 - > bn) + > (a1 + a2 + ... + an)bn > > This process, I believe, is called summation-by-parts. This > problem is not hard to do; one simply separates the ai's from the > bi's, constructs the "partial" sums for the ai series and the > differences for the bi series. Then a dot product gets the > answer. I am interested in a more elegant solution, if one exists. > Taking care of all special cases will probably make any solution > rather inelegant, so I am taking the liberty granted to all posers > of only allowing series which have at least two terms AND the bi's > are not constants and bi = bj is prohibited unless i = j. (This > is, in fact, the situation I am concerned with.) > > I think some of you will have fun connocting ingenious > solutions ... Let me know if you find any. Incidentally, timing > is not crucial in my applications of "summation-by-parts" nor is > storage of intermediate computations a problem. Thanks! > > Jack Goldberg Hi Jack, Here is a newbie approach. Let's first create the expression for n=5 In[1]:= n = 5 Out[1]= 5 In[2]:= arr = Table[ToExpression[ StringJoin["a", ToString[i]]], {i, 1, n}] Out[2]= {a1, a2, a3, a4, a5} In[3]:= brr = Table[ToExpression[ StringJoin["b", ToString[i]]], {i, 1, n}] Out[3]= {b1, b2, b3, b4, b5} In[4]:= exprr = Inner[Times, arr, brr, Plus] Out[4]= a1*b1 + a2*b2 + a3*b3 + a4*b4 + a5*b5 Now lets create two list to hold intermediate results In[5]:= xrr = Table[ToExpression[ StringJoin["x", ToString[i]]], {i, 1, n}] Out[5]= {x1, x2, x3, x4, x5} In[6]:= yrr = Table[ToExpression[ StringJoin["y", ToString[i]]], {i, 1, n}] Out[6]= {y1, y2, y3, y4, y5} Then do a little While loop to decompose the expression: In[7]:= i = 1; j = 0; In[9]:= While[i <= n, xrr[[i]] = exprr[[i,1]] + j; j = xrr[[i]]; yrr[[i]] = If[i < n, exprr[[i,2]] - exprr[[i + 1,2]], exprr[[i,2]]]; i++] Then put the new expression back into order: In[10]:= Inner[Times, xrr, yrr, Plus] Out[10]= a1*(b1 - b2) + (a1 + a2)* (b2 - b3) + (a1 + a2 + a3)* (b3 - b4) + (a1 + a2 + a3 + a4)* (b4 - b5) + (a1 + a2 + a3 + a4 + a5)*b5 How do you like it ? János ---------------------------------------------------- "If I were an animal, I wouldn't keep a man as a pet," --Miklós Jancsó

**References**:**A programming puzzle.***From:*jackgoldberg@comcast.net