       Re: Re: Re: Re: fastest way to add up a billion numbers

```Certianly for small vaues explicit addition is performed, as can be
seen from:

Trace[Sum[i, {i, 1, n}] /. n -> 5]

Out=
{{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}, HoldForm[(5*6)/2], HoldForm}

In:=
Trace[Sum[i, {i, 1, 5}]]

Out=
{HoldForm[Sum[i, {i, 1, 5}]], {HoldForm[i], HoldForm},
{HoldForm[i], HoldForm}, {HoldForm[i], HoldForm},
{HoldForm[i], HoldForm}, {HoldForm[i], HoldForm},
HoldForm[1 + 2 + 3 + 4 + 5], HoldForm}

The second Trace certianly suggests explicit summation.

On the other hand, indeed we have:

In:=
Trace[Sum[i, {i, 1, 10^9}]]

Out=
{HoldForm[Sum[i, {i, 1, 10^9}]], {HoldForm[10^9],
HoldForm}, HoldForm}

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.

Andrzej Kozlowski

On 5 Mar 2007, at 17:20, Daniel Lichtblau wrote:

> Andrzej Kozlowski wrote:
>> If you compare these three timing (and particularly the last one)
>> you  will see that your suspision is wrong.
>> In:=
>> Timing[Sum[i, {i, 1, 10^9}]]
>> Out=
>> {0.11999199999999999*Second, 500000000500000000}
>> In:=
>> Timing[NSum[i, {i, 1, 10^9}]]
>> Out=
>> {0.0862520000000001*Second, 5.000000005*^17}
>> In:=
>> Timing[Sum[i, {i, 1, n}] /. n -> 10^9]
>> Out=
>> {0.02608200000000005*Second, 500000000500000000}
>> Only the last method (the fastest)  does what you suspected (which
>> is  why I do not think it a "legitimate" solution to the posted
>> problem).  The fastest method that actually adds up numbers uses
>> NSum (which of  course gives only an approaximate answer).
>> Andrzej Kozlowski
>> On 4 Mar 2007, at 05:53, Murray Eisenberg wrote:
>>> I wonder what the timing for a sum of the form Sum[n,
>>> {n,nstart,nend}]
>>> really indicates.  I suspect that Mathematica is not actually
>>> summing
>>> but rather just uses Gauss' well-known closed-form formula for
>>> such a
>>> sum of consecutive positive integers.
>>>  [...]
>
> None of these add all the numbers. Actually I am not absolutely
> certain of what NSolve does but I really doubt it is doing the
> arithmetic that fast. To see Sum speed when it does add everything
> try Sum[i, {i,10^6}] (I think Bill Rowe pointed this out in a
> previous response).
>
> I would guess the relative slowness of Out vs Out can be
> explained by a couple of things. One is that quite possibly some
> symbolic summation code is being loaded on that first invocation.
> Even accounting for this that sum will be slower than teh symbolic-
> with-replacement. I will speculate that the rest of the speed
> difference is from preprocessing. I suppose I could check the code
> but, well, I really don't want to.
>
> What I have wondered is why the original note avoided the explicit
> formula. If it was because the typical data set to be summed is
> huge but does not have structure amenable to symbolic methods, then
> something like Total will be needed. In this case I think one must
> split the input into chunks of manageable size, say 10^7 elements,
> so as to avoid running out of memory. But in this case it would be
> fairly clear that Sum cannot be used, because there would be no way
> to specify the general summand. Well, one could do Sum[hugetable
> [[j]],{j,10^9}] but if that were optimal nobody would need Total.
>
>
> Daniel Lichtblau
> Wolfram Research
>

```

• Prev by Date: Re: Transformation rules - explain please
• Next by Date: Re: Re: logical/set theoretic programming
• Previous by thread: Re: Re: Re: Re: fastest way to add
• Next by thread: Re: fastest way to add up a billion numbers