Thread Rating:
  • 1 Vote(s) - 5 Average
  • 1
  • 2
  • 3
  • 4
  • 5
My favorite integer sequence
#48
(08/20/2014, 02:11 PM)sheldonison Wrote: I downloaded your memory efficient code, jdf_seq_v2.gp, and it works great I figured out how to initialize the SeqParts array for a power of 2, and then it is fast for numbers not to much bigger than that exact power of 2. What is the algorithm for initialization halfway to the next power of 2? For example (2^24+2^23)? I don't understand the polynomials well enough to write my own SeqPowers2 initialization starting with 3,6,12,24....

Okay, here's the latest version:

.gp   jdf_seq_v3.gp (Size: 8.45 KB / Downloads: 450)

Note that for SeqPowers2 and SeqPowers2m, it converts large numbers to floating point for display purposes. To turn this off, set jPrec=0

You may have noticed that the graphs I've been posting in this discussion use matplotlib. I prefer graphing in SAGE/python with matplotlib. But my sequence code is in PARI/gp. I would actually prefer to write all my code in SAGE/python, but I'm trying to keep my code accessible to the group here, which means PARI/gp.

My workaround is to export the data from gp to a text file. I do this in my code by setting jWrite=1 when I'm ready to export data. I then import the data into SAGE, then save it to a SAGE native format for reuse later. From there, I can make all my graphs. (Sheldon, if you know of a better way to write stuff to disk from gp, please let me know.)

Anyway, updates in this code:
1. I created a slightly modified version of the NextSeq() function, aptly named NextSeq2(). It accomplishes the same effect as the previous version, but the bit checking is faster.

2. InitPolys will reuse previously calculated polynomials. It will only add what it needs to. If you run InitPolys(20), then InitPolys(25), it will only calculate 21..25 in the second call. Because of this, you can safely call InitPolys from other functions, to ensure that all required polynomials are available. See SeqPowers2, for example.

3. The new function SeqPowers2m, which takes two main arguments: n and m. The n parameter is the max exponent; the m parameter is also an exponent, but controls a sequential counter. The function calculates k*2^j, where [2^(m-1)+1 <= k <= 2^m], and [1 <= j <= n]. There is an optional parameter start, which limits j to the range [start <= j <= n].
Effectively, this calculates a grid of values, from about 2^(start+m-1) to 2^(n+m).

4. I made a bug fix and a couple performance enhancements to InitPolys:
4.1: The previous version scaled the polynomials incorrectly (they were reduced by one too many powers of 2). For example, the following code should always return 1, for any value of k:

Code:
subst(SeqPol[k+1], x, 2^(k-1))

The defect wasn't noticeable, because the code had a compensating "bug". In this case, two wrongs made a right. Anyway, both bugs are fixed now.

4.2: I realized that when calculating the points for polynomial interpolation, I had a running sum of terms, only to take the differences as the first step of interpolation. This seemed inefficient. Therefore, I don't calculate the values directly, but the first differences, and the interpolation code skips the first differences and starts on the second differences.

4.3: This is the big performance boost. I realized that I could reuse almost half the points from the previous polynomial grid. This saves some of the very expensive computations (high-degree polynomials with large rational coefficients). Speedup is roughly 40%. (Begin Edit) I.e., it takes 40% less time. Depending on your point of view, that means the speedup is roughly 70% ~= 1/(1-.4) (End Edit)

(Begin Edit)
5. I forgot to mentioned another big change in SeqNum: while I was writing SeqPowers2m, I found a pattern for calculating A(2^n) for integer n, which requires only one polynomial evaluation (as opposed to n evaluations). I haven't done a comparison between the old and new version, but I assume the speedup is significant, especially when n is very large.
(End Edit)

There are probably still a few bugs in the code, so if you run into any, please let me know.

I'm still getting around to writing the code that calculates arbitrary terms of the sequence. It's actually a bit complicated, which is why I've been putting it off.
~ Jay Daniel Fox
Reply


Messages In This Thread
My favorite integer sequence - by tommy1729 - 07/27/2014, 08:44 PM
RE: My favorite integer sequence - by jaydfox - 07/31/2014, 01:51 AM
RE: My favorite integer sequence - by jaydfox - 08/01/2014, 01:53 AM
RE: My favorite integer sequence - by Gottfried - 08/01/2014, 03:25 PM
RE: My favorite integer sequence - by jaydfox - 08/01/2014, 05:04 PM
RE: My favorite integer sequence - by sheldonison - 08/01/2014, 11:36 PM
RE: My favorite integer sequence - by jaydfox - 08/01/2014, 11:57 PM
RE: My favorite integer sequence - by jaydfox - 08/05/2014, 04:49 PM
RE: My favorite integer sequence - by jaydfox - 08/05/2014, 05:57 PM
RE: My favorite integer sequence - by Gottfried - 08/06/2014, 04:38 PM
RE: My favorite integer sequence - by jaydfox - 08/07/2014, 01:19 AM
RE: My favorite integer sequence - by jaydfox - 08/07/2014, 01:34 AM
RE: My favorite integer sequence - by jaydfox - 08/09/2014, 09:42 AM
RE: My favorite integer sequence - by Gottfried - 08/09/2014, 02:27 PM
RE: My favorite integer sequence - by tommy1729 - 09/09/2014, 12:55 AM
RE: My favorite integer sequence - by jaydfox - 08/08/2014, 12:55 AM
RE: My favorite integer sequence - by Gottfried - 08/08/2014, 02:27 AM
RE: My favorite integer sequence - by jaydfox - 09/09/2014, 07:43 PM
RE: My favorite integer sequence - by jaydfox - 09/09/2014, 09:45 PM
RE: My favorite integer sequence - by jaydfox - 08/02/2014, 12:08 AM
RE: My favorite integer sequence - by tommy1729 - 08/03/2014, 11:38 PM
RE: My favorite integer sequence - by sheldonison - 08/04/2014, 11:49 PM
RE: My favorite integer sequence - by jaydfox - 09/16/2014, 05:32 AM
RE: My favorite integer sequence - by Gottfried - 09/17/2014, 07:39 PM
RE: My favorite integer sequence - by jaydfox - 10/02/2014, 10:53 PM
RE: My favorite integer sequence - by Gottfried - 08/03/2014, 03:32 PM
RE: My favorite integer sequence - by tommy1729 - 08/03/2014, 11:44 PM
RE: My favorite integer sequence - by sheldonison - 08/02/2014, 05:48 AM
RE: My favorite integer sequence - by tommy1729 - 09/10/2014, 08:57 PM
RE: My favorite integer sequence - by Gottfried - 08/02/2014, 07:43 PM
RE: My favorite integer sequence - by Gottfried - 08/02/2014, 09:29 PM
RE: My favorite integer sequence - by Gottfried - 08/02/2014, 09:36 PM
RE: My favorite integer sequence - by tommy1729 - 08/05/2014, 11:16 PM
RE: My favorite integer sequence - by tommy1729 - 08/08/2014, 11:02 PM
RE: My favorite integer sequence - by jaydfox - 08/09/2014, 07:02 PM
RE: My favorite integer sequence - by jaydfox - 08/09/2014, 10:51 PM
RE: My favorite integer sequence - by sheldonison - 08/11/2014, 04:51 PM
RE: My favorite integer sequence - by jaydfox - 08/11/2014, 05:19 PM
RE: My favorite integer sequence - by jaydfox - 08/19/2014, 01:36 AM
RE: My favorite integer sequence - by jaydfox - 08/19/2014, 02:05 AM
RE: My favorite integer sequence - by jaydfox - 08/19/2014, 05:31 PM
RE: My favorite integer sequence - by sheldonison - 08/19/2014, 07:56 PM
RE: My favorite integer sequence - by jaydfox - 08/20/2014, 07:42 AM
RE: My favorite integer sequence - by sheldonison - 08/20/2014, 02:11 PM
RE: My favorite integer sequence - by jaydfox - 08/20/2014, 07:57 PM
RE: My favorite integer sequence - by jaydfox - 08/21/2014, 01:15 AM
RE: My favorite integer sequence - by jaydfox - 08/21/2014, 05:25 AM
RE: My favorite integer sequence - by jaydfox - 08/22/2014, 05:39 PM
RE: My favorite integer sequence - by jaydfox - 09/11/2014, 01:33 AM
RE: My favorite integer sequence - by tommy1729 - 08/09/2014, 09:16 PM
RE: My favorite integer sequence - by jaydfox - 08/09/2014, 10:19 PM
RE: My favorite integer sequence - by tommy1729 - 08/09/2014, 10:52 PM
RE: My favorite integer sequence - by jaydfox - 08/09/2014, 11:46 PM
RE: My favorite integer sequence - by tommy1729 - 08/09/2014, 11:10 PM
RE: My favorite integer sequence - by jaydfox - 08/10/2014, 12:30 AM
RE: My favorite integer sequence - by tommy1729 - 08/11/2014, 12:17 PM
RE: My favorite integer sequence - by Gottfried - 08/22/2014, 12:30 AM
Amazing variant - by tommy1729 - 08/26/2014, 08:57 PM
RE: My favorite integer sequence - by tommy1729 - 09/01/2014, 10:37 PM
RE: My favorite integer sequence - by tommy1729 - 10/02/2014, 11:24 PM
RE: My favorite integer sequence - by jaydfox - 10/02/2014, 11:29 PM
RE: My favorite integer sequence - by tommy1729 - 02/10/2015, 12:15 AM
RE: My favorite integer sequence - by tommy1729 - 02/15/2015, 05:19 PM
RE: My favorite integer sequence - by tommy1729 - 10/07/2015, 08:22 AM
RE: My favorite integer sequence - by tommy1729 - 10/07/2015, 09:10 PM
RE: My favorite integer sequence - by tommy1729 - 03/13/2016, 12:31 AM

Possibly Related Threads...
Thread Author Replies Views Last Post
  My favorite theorem tommy1729 0 4,154 08/15/2015, 09:58 PM
Last Post: tommy1729



Users browsing this thread: 1 Guest(s)