Re: unexpected behaviour of Sum
- To: mathgroup at smc.vnet.net
- Subject: [mg126511] Re: unexpected behaviour of Sum
- From: Murray Eisenberg <murray at math.umass.edu>
- Date: Wed, 16 May 2012 04:22:14 -0400 (EDT)
- Delivered-to: l-mathgroup@mail-archive0.wolfram.com
- References: <joq5h8$r20$1@smc.vnet.net> <201205150852.EAA10924@smc.vnet.net>
- Reply-to: murray at math.umass.edu
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 at 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
- References:
- Re: unexpected behaviour of Sum
- From: A Retey <awnl@gmx-topmail.de>
- Re: unexpected behaviour of Sum