# How to evaluate sum with one million summands?

For a research project I am working on currently, I need to do a very simple and straightforward calculation. Unfortunately, I do not know how to include Mathematica code here, but it is very short anyway:

b[x_] := x^2 - x + 1/2

bp[x_] := b[Mod[x, 1]]

d[n_, q_] := Sum[bp[k/n]* bp[q*k/n], {k, 0, n - 1}]


Now I need to compare two values of d[n,q], in particular, I need to calculate d[1346269,514229] and d[1346269,1137064] to see which one is larger. It works perfectly fine for smaller numbers, e.g. I tried d[75025, 28657] and got the correct result in a reasonable amount of time. However, when I tried evaluating d[1346269,514229] after some time I got the result

(1/9760128332100732436)(4744910246749618660646829 -
4880064166050366218 Hold[$$ConditionHold[$$ConditionHold[
SystemDumpAutoLoad[Hold[SumInfiniteSum],
Hold[SumInfiniteSum, SumSumInfiniteRationalSeries,
SumSumInfiniteRationalExponentialSeries,
SumSumInfiniteLogarithmicSeries,
SumSumInfiniteBernoulliSeries,
SumSumInfiniteFibonacciSeries, SumSumInfiniteLucasLSeries,
SumSumInfiniteArcTangentSeries,
SumSumInfiniteArcCotangentSeries,
SumSumInfiniteqArcTangentSeries,
SumSumInfiniteqArcCotangentSeries,
SumSumInfiniteStirlingNumberSeries,
SumSumInfiniteqRationalSeries], "SumInfiniteSum"]]]][(1 -
Ceiling[(1 - SumFiniteSumDumpl)/1346269] +
Floor[(1346268 - SumFiniteSumDumpl)/1346269]) Mod[(
514229 SumFiniteSumDumpl)/1346269, 1], {SumFiniteSumDumpl,
0, 1346268}, True])


Now, I am not too familiar with Mathematica, so I am not sure where the problem is exactly. However, I would need the two results of d[1346269,1137064] and d[1346269,514229] exactly (i.e. not numerically) as they are super close together, so any rounding could already change the results sufficiently much to alter the order of the two. Is there any way of computing those sums symbolically?

I find that this evaluates much faster. Mathematica is much faster at evaluating functions with a list of 1 million data points than it is at evaluate a function 1 million times with a single point each.

b[x] := x^2 - x + 1/2
bp[x_] := b[Mod[x, 1]]
d[n_, q_] := Total[bp[Range[0, n - 1]/n] bp[q Range[0, n - 1]/n]]
d[1346269, 1137064]


This takes about 17 seconds to evaluate on my machine and gives me:

$$\frac{1459973134402153452576673}{9760128332100732436}$$

Evaluating d[1346269, 514229] gives me:

$$\frac{1459973134399471446859617}{9760128332100732436}$$

The difference is:

$$\frac{670501429264}{2440032083025183109}$$

Evaluated to 100 digits with N[difference, 100], I get

2.74792054550653169316510562953899839764312057350982296551104800194 089580643554604005134744886010933307817655482572397565420836194 $$\cdot 10^{-7}$$

• Your point about the way lists are interacted with via functions during evaluation is going to be quite impactful for me! Thank you :) do you have a good example or explanation as to how the list is evaluated differently than running the evaluation some N number of times? I understand the difference in how much code you’d have to write, but it seemed to me that would only affect the memory taken up, and not change the speed of evaluation. Is the difference in having to access it some N amount of times, reloading the function each time? – CA Trevillian May 10 at 3:28
• I have tried it your way now and indeed it is much faster. Which is really useful, since in fact not only do I need to compute some d[n,q], but for fixed n I need to compute Table[d[n, q], {q, 0, Ceiling[n/2]}] and then find the smallest element. Is there another way of speeding up the computation of the entire table as well? I thought of first computing Table[bp[k/n],{k,0,n-1}] and then just reading the function values from that table. But since bp is not a very complicated function, I was not sure whether this is significantly faster. But is there some way of speeding this up? – Analysis801 May 10 at 6:09
• @CATrevillian mathematica.stackexchange.com/questions/18393/… provides a little background and links to a good question/answer by Mr. Wizard. I don't understand all the details behind why it's faster, but have often found using this feature speeds up code for large amounts of data. Sin[Range[0, 100, 0.001]] is faster than Table[Sin[i], {i, 0, 100, 0.001}] which is faster than For[i = 0, i <= 100, i = i + 0.001, Sin[i]]. – MassDefect May 10 at 18:03
• @Analysis801 Hmmm... I'm not sure. I think that's probably worthy of its own question, if you haven't already asked one. Each one is a pretty major calculation and will take quite some time, so to do half a million of them would be tough. – MassDefect May 10 at 18:10
• @MassDefect wow! I unfortunately didn’t even know you could do that! Now I fortunately do. The link is awesome and your examples are perfect in illustrating the differences. I’m excited to do some new timing tests :) – CA Trevillian May 11 at 1:49