(08/07/2014, 01:34 AM)jaydfox Wrote: It took just 2.5 minutes to calculate the polynomials, about twice as fast as SAGE/python, if I recall correctly. Not sure why the difference, but I'm not complaining:

Here is the second draft of the pari/gp code to calculate the sequence:

jdf_seq_v2.gp (Size: 3.15 KB / Downloads: 625)

I tried my hand at Newton's method, using Stirling numbers of the first kind, and the increase in speed is incredible. It took 2.5 minutes to calculate the first 100 polynomials in the previous version. Now it takes about 10 seconds!!

I calculated 150 polynomials in about 1.5 minutes. And for reference, 60 polynomials took about 1 second (between 850 and 1100 ms in repeated tests). Based on initial tests, the time seems to scale as the 5th power of N (and there are probably some factors of log(n) as well, but I don't have enough data to tease them out). If this trend continues, then 200 polynomials should take about 5 minutes, and 300 should take about 45 minutes.

Just to confirm that I didn't break anything when I changed the interpolation routine, here's a screenshot showing "manual" calculation of the A(2^8 ) through A(2^13), as well as the fast polynomial calculation of the A(0), A(2^0)..A(2^13). These can be validated against a public list of the first 10000 terms (which I already posted a link to previously, but here it is again for reference):

http://oeis.org/A000123/b000123.txt

Quote:Also, please note that when the polynomials are being printed in the InitPolys function, they are rescaled to match my previously posted polynomials. However, "under the hood", the polynomials are scaled properly. Just check out the SeqNum list to see the unscaled polynomials.

By the way, now that the code is finally written in PARI/gp, I took the opportunity to calculate the 2^99th element. (Note that a degree 100 polynomial only gets us up to 2^99. A very small tweak to the code will get the 2^100th element, so I'll be sure to include that in the next version.)

I also fixed this last issue I mentioned. With the 10th degree polynomial, the previous version would only calculate up to A(2^9). This version will calculate up to A(2^10). (In either case, if you try to go further than the advertized limit, you'll get an array index error.)

~ Jay Daniel Fox