On Fri, May 2, 2008 at 12:10 PM, John Cremona <[EMAIL PROTECTED]> wrote: > > ok, so the docstring reaveals (1) that the pari version is "by far the > fastest" as I suspected, but also that for n>50000 that we use a gp > interface rather than the pari library " since the C-library interface > to PARI > is limited in memory for individual operations" -- whatever that > means!
That's out of date now that Gonzalo T. and I fixed the pari interface so that it automatically doubles the stack if needed. The code needs to be fixed to never use gp by default. If you explicitly use algorithm='pari' it will still switch to gp; changing this was one of my fixes to my code so I could try this. Tom is trying the whole calculation directly in GP. He also did a log fit to timings and estimates it should take about a week in Sage on his machine. We'll see. > > That might explain David's timing observations. > > I tihnk the pari implementation is actually quite simple (and there is > a huge amount about Berouilli nos in Henri Cohen's latest book too) > which suggests that doing a cython implementation would not be hard. > > Maybe this is time for a repeat performance of the partitions > competition with M**ca! The complexity mostly depends on the precision one uses in computing a certain Euler product approximation to zeta and also the number of factors in the product. If you look at the PARI source code the comments do *not* inspire confidence in its correctness. I had a student give a provable bound on precision and number of factors needed and wasn't able to get anything as good as what PARI uses. Here's the funny part of the PARI code (in trans3.c): /* 1.712086 = ??? */ t = log( gtodouble(d) ) + (n + 0.5) * log(n) - n*(1+log2PI) + 1.712086; -- William --~--~---------~--~----~------------~-------~--~----~ 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://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
