There are two tricks I can see that are required to make this faster. Firstly notice that L(n,q)*Psi(n,q) is relatively small once q gets beyond a certain point. Thus L(n,q)*Psi(n,q) can be computed using ordinary double precision for q greater than some very small limit (depending on n). If one knew how fast this series converges (which must have been worked out somewhere), one could even progressively reduce the precision as the computation went, for even greater speed. For example the following Pari script should compute all but the last 150 or so digits of P(10^9) quite quickly:
Psi(n, q) = local(a, b, c); a=sqrt(2/3)*Pi/q; b=n-1/24; c=sqrt(b); (sqrt(q)/(2*sqrt(2)*b*Pi))*(a*cosh(a*c)-(sinh(a*c)/c)) L(n, q) = if(q==1,1,sum(h=1,q-1,if(gcd(h,q)>1,0,cos((g(h,q)-2*h*n)*Pi/ q)))) g(h, q) = if(q<3,0,sum(k=1,q-1,k*(frac(h*k/q)-1/2))) n=1000000004 \p36000 a1 = L(n,1)*Psi(n,1); \p18000 a2 = L(n,2)*Psi(n,2); \p12000 a3 = L(n,3)*Psi(n,3); \p9000 a4 = L(n,4)*Psi(n,4); \p8000 a5 = L(n,5)*Psi(n,5); \p6000 a6 = L(n,6)*Psi(n,6); \p6000 a7 = L(n,7)*Psi(n,7); \p5000 a8 = L(n,8)*Psi(n,8); \p4000 a9 = sum(y=9,14,L(n,y)*Psi(n,y)); \p3000 a10 = sum(y=15,17,L(n,y)*Psi(n,y)); \p2000 a11 = sum(y=18,34,L(n,y)*Psi(n,y)); \p1000 a12 = sum(y=35,300,L(n,y)*Psi(n,y)); round(a1+a2+a3+a4+a5+a6+a7+a8+a9+a10+a11+a12) The second trick is that computing gcd(h,q) is costly. One should factor q and then sieve for all h not coprime to q in short cache friendly segments, especially for very large n. But I don't believe Mathematica uses this Rademacher series thing anyway. If you look at the inner most loop, that computation involving frac must take at least 80 cycles in double precision. But for n = 10^9, that expression must get evaluated about 2*10^11 times. That's about 1.6*10^13 cycles, which on sage.math has go to take about 10000s. Even if I'm out by a factor of 10 with the cycles, mathematica clearly doesn't do this. Perhaps if one had a fast way of evaluating the Dedekind sum, one might have a chance. Bill. --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~----------~----~----~----~------~----~------~--~---
