Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.soft-sys.math.mathematica > #10075 > unrolled thread

unexpected behaviour of Sum

Started byperplexed <yudumbo@gmail.com>
First post2012-05-14 05:34 +0000
Last post2012-05-16 08:25 +0000
Articles 5 — 3 participants

Back to article view | Back to comp.soft-sys.math.mathematica


Contents

  unexpected behaviour of Sum perplexed <yudumbo@gmail.com> - 2012-05-14 05:34 +0000
    Re: unexpected behaviour of Sum A Retey <awnl@gmx-topmail.de> - 2012-05-15 08:53 +0000
      Re: unexpected behaviour of Sum perplexed <yudumbo@gmail.com> - 2012-05-18 09:23 +0000
      Re: unexpected behaviour of Sum Murray Eisenberg <murray@math.umass.edu> - 2012-05-19 09:53 +0000
    Re: unexpected behaviour of Sum Murray Eisenberg <murray@math.umass.edu> - 2012-05-16 08:25 +0000

#10075 — unexpected behaviour of Sum

Fromperplexed <yudumbo@gmail.com>
Date2012-05-14 05:34 +0000
Subjectunexpected behaviour of Sum
Message-ID<joq5h8$r20$1@smc.vnet.net>
I do not want to say that this is a bug, however I did
not find, in the Sum documentation, an explanation of this
behaviour (v8.0.4)

I defined an innocent function like
sod[n_]:=Plus@@IntegerDigits[n]
that compute the sum of the digits of a number.
(I tried with other functions, so the culprit is not IntegerDigits)

Then I compute two sums:
Sum[sod[k],{k,10^6}] which gives 27000001 (ok)
then 
Sum[sod[k],{k,1+10^6}] which gives 500001500001 (nonsense).
then 
Sum[sod[k],{k,2,1+10^6}] which gives 27000002 (ok)

so, it seems to me that Sum has a problem when the iterator
works in a range greater than 10^6.

Indeed, I made an experiment:
I set L={}; and defined
sod[n_]:=(AppendTo[L,n];Plus@@IntegerDigits[n])
Then Sum[sod[k],{k,1+10^6}] still gives 500001500001 
and at the end L is equal to {k}, so it seems that
Sum tried to do something symbolic (??).

Is this a bug or a feature whose documentation I was not
able to find? Say, is there an option to fix things ?

Btw, using ParallelSum instead of Sum works fine (and faster).
thanks

[toc] | [next] | [standalone]


#10088

FromA Retey <awnl@gmx-topmail.de>
Date2012-05-15 08:53 +0000
Message-ID<jot5hm$am0$1@smc.vnet.net>
In reply to#10075
Hi,

> I do not want to say that this is a bug, however I did
> not find, in the Sum documentation, an explanation of this
> behaviour (v8.0.4)
>
> I defined an innocent function like
> sod[n_]:=Plus@@IntegerDigits[n]
> that compute the sum of the digits of a number.
> (I tried with other functions, so the culprit is not IntegerDigits)
>
> Then I compute two sums:
> Sum[sod[k],{k,10^6}] which gives 27000001 (ok)
> then
> Sum[sod[k],{k,1+10^6}] which gives 500001500001 (nonsense).
> then
> Sum[sod[k],{k,2,1+10^6}] which gives 27000002 (ok)
>
> so, it seems to me that Sum has a problem when the iterator
> works in a range greater than 10^6.
>
> Indeed, I made an experiment:
> I set L={}; and defined
> sod[n_]:=(AppendTo[L,n];Plus@@IntegerDigits[n])
> Then Sum[sod[k],{k,1+10^6}] still gives 500001500001
> and at the end L is equal to {k}, so it seems that
> Sum tried to do something symbolic (??).

yes, Sum will try to something symbolic, and the default threshold is 
indeed 1000000, as SystemOptions["SymbolicSumThreshold"] will show you.
> Is this a bug or a feature whose documentation I was not
> able to find? Say, is there an option to fix things ?

You could in fact increase SymbolicSumThreshold, but I think there are 
much better ways to achieve what you want. First you should understand 
what happens: when switching to a symbolic algorithm, Sum will evaluate 
the summand symbolically, if you do that you will find the following:

Clear[k];sod[k]  will return k

What happend? IntegerDigits[k] will not evaluate, applying Plus will 
replace the Head with Plus and the end result is k. Sum[k,{1,n}] will 
return the well known Gauss formula and insert 10^6+1 and that's the 
wrong result you see.

One way to solve your problem would be to define sod so it only is 
evaluated for input that it actually does handle, e.g.:

ClearAll[sod]
sod[n_Integer] := Plus @@ IntegerDigits[n]

Another, probably even better approach is to use functions that will not 
even try to do anything symbolic. Actually Sum to some extend can be 
seen as a function made to return symbolic sums and it will do explicit 
summations just as an additional feature. A simple approach like this:

Total[Table[sod[k], {k, 10^6 + 1}]]

will immediately yield the correct result, independent on how you define 
sod. Presumably because the table will create a large list which will 
consume a lot of memory the last is slower than Sum in this case, but if 
you are after performance, you could change the definition of sod to this:

ClearAll[sod]
sod = Plus @@ IntegerDigits[#] &

Total[Table[sod[k], {k, 10^6 + 1}]] // Timing

which is now very fast since it now sees what sod actually is and will 
compile it. If you also want to be more memory efficient you can compile 
yourself:

Timing[Compile[{},
    Module[{sum = 0}, Do[sum += sod[k], {k, 10^6 + 1}]; sum],
    CompilationOptions -> "InlineExternalDefinitions" -> True][]
  ]

> Btw, using ParallelSum instead of Sum works fine (and faster).

which probably is because it does not try to do the sum symbolically 
(but probably not nearly as fast as the compiled versions)...

hth,

albert

[toc] | [prev] | [next] | [standalone]


#10120

Fromperplexed <yudumbo@gmail.com>
Date2012-05-18 09:23 +0000
Message-ID<jp54e5$gl5$1@smc.vnet.net>
In reply to#10088
Thanks to everybody.

It is surely true I could write a better definition
for my functions (sod was just an example),
but still I do think that this is an imperfection in
the documentation of Sum.

First of all, this SymbolicSumThreshold option
is never cited in the documentation of Sum.

In general, there is never a hint to the fact that
Sum will try to sum symbolically in the case of
a definite sum. If I did know, I would have considered
writing a better function.

On the contrary, in the documentation of Sum I read :

"If the range of a sum is finite, i is typically assigned a sequence
of values,
with f being evaluated for each one."

and

"If a sum cannot be carried out explicitly by adding up a finite
number of terms,
Sum will attempt to find a symbolic result. In this case, f is first
evaluated symbolically."

With due respect,
I think that maybe a couple of lines should be added to the
documentation at least in the "Possible issues" section.



[toc] | [prev] | [next] | [standalone]


#10156

FromMurray Eisenberg <murray@math.umass.edu>
Date2012-05-19 09:53 +0000
Message-ID<jp7qi9$qk4$1@smc.vnet.net>
In reply to#10088
Send to: suggestions@wolfram.com

On 5/18/12 5:22 AM, perplexed wrote:
> Thanks to everybody.
>
> It is surely true I could write a better definition
> for my functions (sod was just an example),
> but still I do think that this is an imperfection in
> the documentation of Sum.
>
> First of all, this SymbolicSumThreshold option
> is never cited in the documentation of Sum.
>
> In general, there is never a hint to the fact that
> Sum will try to sum symbolically in the case of
> a definite sum. If I did know, I would have considered
> writing a better function.
>
> On the contrary, in the documentation of Sum I read :
>
> "If the range of a sum is finite, i is typically assigned a sequence
> of values,
> with f being evaluated for each one."
>
> and
>
> "If a sum cannot be carried out explicitly by adding up a finite
> number of terms,
> Sum will attempt to find a symbolic result. In this case, f is first
> evaluated symbolically."
>
> With due respect,
> I think that maybe a couple of lines should be added to the
> documentation at least in the "Possible issues" section.
>
>
>
>

-- 
Murray Eisenberg                     murray@math.umass.edu
Mathematics & Statistics Dept.
Lederle Graduate Research Tower      phone 413 549-1020 (H)
University of Massachusetts                413 545-2859 (W)
710 North Pleasant Street            fax   413 545-1801
Amherst, MA 01003-9305

[toc] | [prev] | [next] | [standalone]


#10091

FromMurray Eisenberg <murray@math.umass.edu>
Date2012-05-16 08:25 +0000
Message-ID<jovoag$mj0$1@smc.vnet.net>
In reply to#10075
All this indicates that the behavior that surprised the O.P. is indeed a 
bit subtle.

When defining sod, is there any good reason to be using Plus with Apply
(Plus @@ IntegerDigits) instead of the more direct composite with Total 
(Total @ IntegerDigits)? I ask because for the example at hand, the 
ratio of Timing values for the two is roughly 3/2.


On 5/15/12 4:52 AM, A Retey wrote:
> Hi,
>
>> I do not want to say that this is a bug, however I did
>> not find, in the Sum documentation, an explanation of this
>> behaviour (v8.0.4)
>>
>> I defined an innocent function like
>> sod[n_]:=Plus@@IntegerDigits[n]
>> that compute the sum of the digits of a number.
>> (I tried with other functions, so the culprit is not IntegerDigits)
>>
>> Then I compute two sums:
>> Sum[sod[k],{k,10^6}] which gives 27000001 (ok)
>> then
>> Sum[sod[k],{k,1+10^6}] which gives 500001500001 (nonsense).
>> then
>> Sum[sod[k],{k,2,1+10^6}] which gives 27000002 (ok)
>>
>> so, it seems to me that Sum has a problem when the iterator
>> works in a range greater than 10^6.
>>
>> Indeed, I made an experiment:
>> I set L={}; and defined
>> sod[n_]:=(AppendTo[L,n];Plus@@IntegerDigits[n])
>> Then Sum[sod[k],{k,1+10^6}] still gives 500001500001
>> and at the end L is equal to {k}, so it seems that
>> Sum tried to do something symbolic (??).
>
> yes, Sum will try to something symbolic, and the default threshold is
> indeed 1000000, as SystemOptions["SymbolicSumThreshold"] will show you.
>> Is this a bug or a feature whose documentation I was not
>> able to find? Say, is there an option to fix things ?
>
> You could in fact increase SymbolicSumThreshold, but I think there are
> much better ways to achieve what you want. First you should understand
> what happens: when switching to a symbolic algorithm, Sum will evaluate
> the summand symbolically, if you do that you will find the following:
>
> Clear[k];sod[k]  will return k
>
> What happend? IntegerDigits[k] will not evaluate, applying Plus will
> replace the Head with Plus and the end result is k. Sum[k,{1,n}] will
> return the well known Gauss formula and insert 10^6+1 and that's the
> wrong result you see.
>
> One way to solve your problem would be to define sod so it only is
> evaluated for input that it actually does handle, e.g.:
>
> ClearAll[sod]
> sod[n_Integer] := Plus @@ IntegerDigits[n]
>
> Another, probably even better approach is to use functions that will not
> even try to do anything symbolic. Actually Sum to some extend can be
> seen as a function made to return symbolic sums and it will do explicit
> summations just as an additional feature. A simple approach like this:
>
> Total[Table[sod[k], {k, 10^6 + 1}]]
>
> will immediately yield the correct result, independent on how you define
> sod. Presumably because the table will create a large list which will
> consume a lot of memory the last is slower than Sum in this case, but if
> you are after performance, you could change the definition of sod to this:
>
> ClearAll[sod]
> sod = Plus @@ IntegerDigits[#]&
>
> Total[Table[sod[k], {k, 10^6 + 1}]] // Timing
>
> which is now very fast since it now sees what sod actually is and will
> compile it. If you also want to be more memory efficient you can compile
> yourself:
>
> Timing[Compile[{},
>      Module[{sum = 0}, Do[sum += sod[k], {k, 10^6 + 1}]; sum],
>      CompilationOptions ->  "InlineExternalDefinitions" ->  True][]
>    ]
>
>> Btw, using ParallelSum instead of Sum works fine (and faster).
>
> which probably is because it does not try to do the sum symbolically
> (but probably not nearly as fast as the compiled versions)...
>
> hth,
>
> albert
>

-- 
Murray Eisenberg                     murray@math.umass.edu
Mathematics & Statistics Dept.
Lederle Graduate Research Tower      phone 413 549-1020 (H)
University of Massachusetts                413 545-2859 (W)
710 North Pleasant Street            fax   413 545-1801
Amherst, MA 01003-9305

[toc] | [prev] | [standalone]


Back to top | Article view | comp.soft-sys.math.mathematica


csiph-web