Services & ResourcesWolfram ForumsMathGroup Archive

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

Re: fastest way to add up a billion numbers

• To: mathgroup at smc.vnet.net
• Subject: [mg74230] Re: fastest way to add up a billion numbers
• From: hemphill at hemphills.net
• Date: Thu, 15 Mar 2007 04:56:56 -0500 (EST)
• References: <es92b2$3oj$1@smc.vnet.net> <200703030555.AAA02643@smc.vnet.net> <200703040453.XAA25305@smc.vnet.net> <200703050946.EAA19233@smc.vnet.net> <45EC435A.30700@wolfram.com> <et54hq$atu$1@smc.vnet.net>
• Reply-to: hemphill at alumni.caltech.edu

Andrzej Kozlowski <akoz at mimuw.edu.pl> writes:

> Certianly for small vaues explicit addition is performed, as can be  
> seen from:
> 
> Trace[Sum[i, {i, 1, n}] /. n -> 5]
> 
> Out[9]=
> {{HoldForm[Sum[i, {i, 1, n}]],
>     HoldForm[(1/2)*n*(n + 1)]},
>    HoldForm[(1/2)*n*(n + 1) /. n -> 5],
>    HoldForm[(5*(1 + 5))/2], {HoldForm[1 + 5],
>     HoldForm[6]}, HoldForm[(5*6)/2], HoldForm[15]}
> 
> In[10]:=
> Trace[Sum[i, {i, 1, 5}]]
> 
> Out[10]=
> {HoldForm[Sum[i, {i, 1, 5}]], {HoldForm[i], HoldForm[1]},
>    {HoldForm[i], HoldForm[2]}, {HoldForm[i], HoldForm[3]},
>    {HoldForm[i], HoldForm[4]}, {HoldForm[i], HoldForm[5]},
>    HoldForm[1 + 2 + 3 + 4 + 5], HoldForm[15]}
> 
> The second Trace certianly suggests explicit summation.
> 
> On the other hand, indeed we have:
> 
> In[22]:=
> Trace[Sum[i, {i, 1, 10^9}]]
> 
> Out[22]=
> {HoldForm[Sum[i, {i, 1, 10^9}]], {HoldForm[10^9],
>     HoldForm[1000000000]}, HoldForm[500000000500000000]}
> 
> 
> If this is right, it sugges that the algorithm switches at some point  
> form explicit addition to using a formula. One could obviously find  
> out the point at which the algorithm switches form one approach to  
> the other, I suspect the number would b eunder 1000.

I have version 5.1 for Linux.  The algorithm switches approaches at
10^6+1.

Scott
-- 
Scott Hemphill	hemphill at alumni.caltech.edu
"This isn't flying.  This is falling, with style."  -- Buzz Lightyear

• Follow-Ups:
  • Re: Re: fastest way to add up a billion numbers
    • From: Andrzej Kozlowski <akoz@mimuw.edu.pl>

• References:
  • Re: fastest way to add up a billion numbers
    • From: "dimitris" <dimmechan@yahoo.com>
  • Re: Re: fastest way to add up a billion numbers
    • From: Murray Eisenberg <murray@math.umass.edu>
  • Re: Re: Re: fastest way to add up a billion numbers
    • From: Andrzej Kozlowski <akoz@mimuw.edu.pl>