Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

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