Re: unexpected behaviour of Sum
- To: mathgroup at smc.vnet.net
- Subject: [mg126496] Re: unexpected behaviour of Sum
- From: A Retey <awnl at gmx-topmail.de>
- Date: Tue, 15 May 2012 04:52:34 -0400 (EDT)
- Delivered-to: l-mathgroup@mail-archive0.wolfram.com
- References: <joq5h8$r20$1@smc.vnet.net>
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
- Follow-Ups:
- Re: unexpected behaviour of Sum
- From: Murray Eisenberg <murray@math.umass.edu>
- Re: unexpected behaviour of Sum