1 /*
2
3 Copyright (C) 2001,2002,2003,2004 Michael Rubinstein
4
5 This file is part of the L-function package L.
6
7 This program is free software; you can redistribute it and/or
8 modify it under the terms of the GNU General Public License
9 as published by the Free Software Foundation; either version 2
10 of the License, or (at your option) any later version.
11
12 This program is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
16
17 Check the License for details. You should have received a copy of it, along
18 with the package; see the file 'COPYING'. If not, write to the Free Software
19 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
20
21 */
22
23 #include "Lglobals.h"
24
25
26 //-----Global variables---------------------------------------
27
28
29 int my_verbose=0; // verbosity level: 0 means no verbose
30
31 int DIGITS, DIGITS2; // precision and sacrifice
32 int DIGITS3; // how many digits to output
33 Double tolerance;
34 Double tolerance_sqrd;
35 Double tolerance2;
36 Double tolerance3;
37
38 int global_derivative; //which derivative to compute
39 int max_n; // largest n used in a dirichlet series while computing an L-value.
40
41 Double A; //controls the 'support' of g(w) in the Riemann sum method
42 Double incr; //the increment in the Riemann sum method
43 Double tweak; //used in value_via_Riemann_sum to play with the angle
44
45 Double *LG; // lookup table for log(n)
46 Double *two_inverse_SQUARE_ROOT; // lookup table for sqrt(n)
47 int number_sqrts=0; // how many sqrt(n)'s to store
48 int number_logs=0; // how many log(n)'s to store
49
50 int *prime_table;
51 int number_primes=0;
52
53 Double *bernoulli; // lookup table for bernoulli numbers
54
55 bool print_warning=true;
56
57 Long my_LLONG_MAX; //equals LLONG_MAX defined in limits.h. For
58 //reasons doing with compilation bugs, I determine it myself
59
60 Double Pi;
61 Double log_2Pi;
62 Complex I;
63
64 bool only_use_dirichlet_series=false; //whether to compute just using the Dirichlet series
65 int N_use_dirichlet_series; //if so, how many terms in the Dirichlet series to use.
66
67 //------Incomplete gamma function global variables--------------
68
69 Complex last_z; // the last z to be considered in inc_GAMMA
70 Complex last_w; // the last w to be considered in inc_GAMMA
71 Complex last_comp_inc_GAMMA; // g(last_z,last_w)
72
73 Complex last_z_GAMMA; //the last z to be considered in GAMMA
74 Complex last_log_G; //the last log(GAMMA(z));
75
76 Double temme_a[1002],temme_g[501];
77 //used in Temme's asymptotic expansion of the
78 //incomplete gamma function
79 //XXXX might need more terms if I go to higher precision
80
81 // Riemann siegel band limited interpolation arrays and variables ----------
82
83 const Double sin_cof[]={1,-(Double)1/6,1/120,-(Double)1/5040,(Double)1/362880,-(Double)1/39916800};
84 const Double sinh_mult_fac=(Double)1/2;
85 const Double sin_tol=1.e-5;
86 const int sin_terms=2;
87
88 const Double blfi_block_growth=2; // how fast blfi blocks grow as we traverse the main sum, keep as is for now
89 const Double beta_fac_mult=6; // controls the density of blfi sampling and the number of blfi terms needed
90 const Double blfi_fac=.085; // efficiency of the blfi interpolation sum relative to an RS sum of same length
91 const Double pts_array_fac=10000;
92
93 const int rs_blfi_N=3;
94
95 Double *klog0; //log(k) at the beginning
96 Double *klog2; //log(k) at the end if needed
97 Double *ksqrt0; // 1/sqrt(k) at the beginning
98 Double *ksqrt2;// 1/sqrt(k) at the end if needed
99 int *num_blocks; // number of blocks
100 int *size_blocks;// size of blocks
101 Double *trig; // stores correction terms
102 Double *zz; // store powers of fractional part
103
104 Double **klog1; //log(k) in the middle if needed
105 Double **ksqrt1; // 1/sqrt(k) in the middle if needed
106 Double **klog_blfi; //initial term
107 Double **qlog_blfi; //band-width
108 Double **piv_org; //original pivot
109 Double **bbeta; //beta
110 Double **blambda; //lambda
111 Double **bepsilon; //epsilon
112 Double **arg_blfi; //arg_blfi
113 Double **inv_arg_blfi; //inv_arg_blfi
114
115 Double ***qlog_blfi_dense; // log(1+k/v) terms
116 Double ***qsqrt_blfi_dense; // 1/sqrt(1+k/v)
117 int ***blfi_done_left; //block done or not
118 int ***blfi_done_right; //block done or not
119 Double ***blfi_val_re_left; //real value of block
120 Double ***blfi_val_re_right; //real value of block
121 Double ***blfi_val_im_left; //imag value of block
122 Double ***blfi_val_im_right; //imag value of block
123
124 int length_org=0; // length of the main sum
125 int length_split=0; // length of the portion of the main sum to be evaluated directly
126 int lgdiv=0; // number of divisions of the main sum into intervals of the form [N,2N)
127 int max_pts=0; // max number of interpolation points allowed
128 int range=0; // number of blfi interpolation points needed
129 int blfi_block_size_org=0; // starting length of the blfi block
130 int total_blocks=0;
131 int rs_flag=0;
132
133 Double bc=0;
134 Double bc2=0;
135 Double kernel_fac=0;
136 Double ler=0;
137 Double mult_fac=0;
138 Double approx_blfi_mean_spacing=0;
139 Double interval_length=0;
140 Double error_tolerance=0;
141 Double input_mean_spacing=0;
142 Double input_mean_spacing_given=.01; //rough anticipated sampling distance between t's for zeta(1/2+It).
143 //Should be set if known.
144
145 //------------------------------------------------------------------
146
147
148 //-----intializing and cleaning up routines----------------------
149
150 //n is the number of log(n)'s to precompute
151 //call this function after changing the DIGITS global variable
initialize_globals(int n)152 void initialize_globals(int n){
153
154
155 #ifdef USE_MPFR
156 if(!DIGITS) DIGITS=40;
157 if(!DIGITS2) DIGITS2=2;
158 if(!DIGITS3) DIGITS3=DIGITS-DIGITS2;
159 //__mpfr_default_fp_bit_precision=Int(DIGITS*log(10.)/log(2.));
160 //mpfr_set_default_prec(__mpfr_default_fp_bit_precision);
161 mpfr_set_default_prec(Int(DIGITS*log(10.)/log(2.)));
162 reset(Pi);
163 reset(log_2Pi);
164 reset(I);
165 reset(tolerance);
166 reset(last_z);
167 reset(last_w);
168 reset(last_comp_inc_GAMMA);
169 reset(last_z_GAMMA);
170 reset(last_log_G);
171 loop(i,0,1002) reset(temme_a[i]);
172 loop(i,0,501) reset(temme_g[i]);
173 mpfr_const_pi(Pi.get_mpfr_t(), __gmp_default_rounding_mode);
174 log_2Pi=log(2*Pi);
175 #else
176 if(!DIGITS){
177 typedef std::numeric_limits< Double > tmp_Double;
178 DIGITS=tmp_Double::digits10-1;
179 }
180 if(!DIGITS2) DIGITS2=2;
181 if(!DIGITS3) DIGITS3=DIGITS-DIGITS2;
182 Pi= 3.14159265358979323846264338328L;
183 log_2Pi= 1.837877066409345483560659472811L;
184 //Pi= 3.1415926535897932384626433832795028841971693993751L;
185 //log_2Pi= 1.8378770664093454835606594728112352797227949472756L;
186 #endif
187 I=Complex(0,1);
188 tolerance=pow(.1,DIGITS);
189 tolerance_sqrd=tolerance*tolerance;
190 tolerance2=pow(.1,(DIGITS-DIGITS2+1));
191 tolerance3=pow(.1,(DIGITS3+1));
192
193 A=1./(16*Pi*Pi*23*DIGITS/10);
194 incr=2*Pi*.5/(log(10.)*DIGITS); //.5 here is current v in Riemann sum method
195 tweak=1;
196
197 last_z=1;
198 last_w=0;
199 last_comp_inc_GAMMA=0;
200 last_z_GAMMA=1;
201 last_log_G=0;
202
203 global_derivative=0;
204 max_n=1;
205
206 numeric_limits<long long> ll;
207 my_LLONG_MAX = ll.max(); //used once, but in the elliptic curve module Lcommandline_ellipitic.cc
208 //pari defines max #define max(a,b) ((a)>(b)?(a):(b)) and this causes problems with ll.max
209 //so I put it here as a global.
210 //also look at: http://www.google.com/answers/threadview?id=334912
211 //Re: g++ problems with strtoll (LLONG_MIN, LLONG_MAX, ULLONG_MAX not defined)
212 //for an explanation of why we just don't call LLONG_MAX (compiler inconsistencies).
213
214 int j,k;
215 Double r,x,dsum;
216
217 number_logs=n;
218 if(LG) delete[] LG;
219 LG = new Double[n+1];
220 for(k=1;k<=n;k++) LG[k]=log((Double)k);
221
222 number_sqrts=n;
223 if(two_inverse_SQUARE_ROOT) delete[] two_inverse_SQUARE_ROOT;
224 two_inverse_SQUARE_ROOT = new Double[n+1];
225 for(k=1;k<=n;k++) two_inverse_SQUARE_ROOT[k]=2/sqrt((Double)k);
226
227 if(bernoulli) delete[] bernoulli;
228 bernoulli= new Double[DIGITS+1];
229
230 bernoulli[0]=1;
231 for(k=1;k<=DIGITS;k++){
232 r=k+1; x=0;
233 for(j=1;j<=k;j++){
234 r=r*(k+1-j)*1./(j+1);
235 x=x-bernoulli[k-j]*r;
236 }
237 bernoulli[k]=x/(k+1);
238 }
239
240 //XXXXX this should depend on DIGITS
241 temme_a[1]=1;
242
243 temme_a[2]=(Double) 3;
244 temme_a[2]=1/temme_a[2]; //doing temme_a[2]=1./3 causes problems with long doubles or multiprecision. 1.L/3
245 //could cause trouble for multiprecision.
246 temme_a[3]=(Double)36;
247 temme_a[3]=1/temme_a[3];
248
249 for (int i=4;i<=1001;i++) {
250 dsum=0;
251 for (int j=2;j<=(i-1);j++)
252 dsum+=j*temme_a[j]*temme_a[i-j+1];
253 temme_a[i]=(temme_a[i-1]-dsum)/((Double) (i+1));
254 }
255
256 for(int i=1;i<=500;i++)
257 temme_g[i]=(1-2*(i%2))*
258 dfac(2*i+1)*temme_a[2*i+1];
259 temme_g[0]=1;
260
261 extend_prime_table(100);
262
263 }
264
delete_globals()265 void delete_globals(){
266
267 if(LG) delete [] LG;
268 if(two_inverse_SQUARE_ROOT) delete [] two_inverse_SQUARE_ROOT;
269 if(bernoulli) delete [] bernoulli;
270
271 if (prime_table) delete [] prime_table;
272
273 }
274
extend_LG_table(int m)275 void extend_LG_table(int m){
276
277
278 int n;
279
280 Double *tmp_LG; //used to copy over the old values
281 tmp_LG = new Double[number_logs+1];
282 for(n=1;n<=number_logs;n++) tmp_LG[n]=LG[n];
283
284 delete [] LG;
285 int new_number_logs=(int)(1.5*m); // extend table by 50 percent
286
287 LG = new Double[new_number_logs+1];
288 for(n=1;n<=number_logs;n++) LG[n]=tmp_LG[n];
289 for(n=number_logs+1;n<=new_number_logs;n++) LG[n]=log((Double)n);
290 number_logs=new_number_logs;
291
292 if(my_verbose>0)
293 cout << endl << "extended log table to: " << number_logs << endl;
294
295 delete [] tmp_LG;
296
297 }
298
extend_sqrt_table(int m)299 void extend_sqrt_table(int m){
300
301
302 int n;
303
304 Double *tmp_sqrt; //used to copy over the old values
305 tmp_sqrt = new Double[number_sqrts+1];
306 for(n=1;n<=number_sqrts;n++) tmp_sqrt[n]=two_inverse_SQUARE_ROOT[n];
307
308 delete [] two_inverse_SQUARE_ROOT;
309 int new_number_sqrts=(int)(1.5*m); // extend table by 50 percent
310
311 two_inverse_SQUARE_ROOT = new Double[new_number_sqrts+1];
312 for(n=1;n<=number_sqrts;n++) two_inverse_SQUARE_ROOT[n]=tmp_sqrt[n];
313 for(n=number_sqrts+1;n<=new_number_sqrts;n++) two_inverse_SQUARE_ROOT[n]=2/sqrt((Double)n);
314 number_sqrts=new_number_sqrts;
315
316 if(my_verbose>0)
317 cout << endl << "extended sqrt table to: " << number_sqrts << endl;
318
319 delete [] tmp_sqrt;
320
321 }
322
323
324 // a lot of Q time is spend here. This can be precomputed XXXXX
dfac(int i)325 Double dfac(int i)
326 {
327 Double t=1;
328 int n=i;
329 if(i==1 || i==0) return 1;
330 while(n>0) {
331 t=t*n;
332 n-=2;
333 }
334 //return (Double)(double)t;
335 return t;
336 }
337
extend_prime_table(int x)338 void extend_prime_table(int x)
339 {
340 int *sieve;
341 int sqrtx;
342 int n, p;
343 int number_primes_guess;
344
345 sieve = new int[x+1];
346
347 if (prime_table) delete [] prime_table;
348 number_primes = 0;
349
350 // Use explicit prime number theorem to allocate enough memory for primes
351 number_primes_guess = max((int)ceil(x/(log(x)-4))+1, 100);
352
353 prime_table = new int[number_primes_guess];
354
355 if (my_verbose > 0)
356 {
357 cout << "extending prime table to: " << x << "; ";
358 cout << "guessed " << number_primes_guess << " primes; ";
359 }
360 for (n=0;n<=x;n++)
361 sieve[n] = 1;
362
363 p = 2;
364 sqrtx = (int) sqrt(x);
365 while (p <= sqrtx)
366 {
367 n = 2*p;
368 while (n <= x)
369 {
370 sieve[n] = 0;
371 n = n + p;
372 }
373 do
374 p++;
375 while (sieve[p] == 0);
376 }
377 for (n=2;n<=x;n++)
378 {
379 if (sieve[n] == 1)
380 {
381 prime_table[number_primes] = n;
382 number_primes++;
383 }
384 }
385 delete [] sieve;
386
387 if (my_verbose > 0)
388 cout << "found " << number_primes << " primes." << endl;
389
390 return;
391 }
392
get_prime(int j)393 int get_prime(int j)
394 {
395 while (j >= number_primes)
396 {
397 extend_prime_table(prime_table[number_primes-1]*2);
398 }
399
400 return prime_table[j];
401 }
402