formula guesser

[Ralf Stephan]

Hello,
I'm thinking about implementing a formula guesser for C-finite integer sequences. The algorithm, which is not as complicated as the one for D-finite sequences, needs SymPy's rsolve on one hand, and on the other an implementation of the LLL algorithm.

My questions:
- is there interest to have that in SymPy? I have a working patch for Sage but I've been waiting for a year now for review and it uses Pari for the LLL.
- if there is interest, I understand the SymPy package does not depend on external specialized numerics libraries except for mpmath?
- if so, the only Python LLL implementation AFAIK is in pymatgen which has an MIT license. Could this be used, assuming it would be technically useful?

I'm only sticking my toe in the water for the moment and would be glad if you could give me orientation.

Regards,

[Mateusz Paprocki]

Hi,

mpmath implements PSLQ algorithm, thought it might be insufficient for
the problem your're solving. Implementation of LLL is welcome, as any
other contributions extending SymPy's functionality. Reusing MIT or
BSD (or equivalent permissive license) code is perfectly possible, as
long as you attribute the original work properly.

Mateusz

> Regards,
>
> --
> You received this message because you are subscribed to the Google Groups "sympy" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sympy+un...@googlegroups.com.
> To post to this group, send email to sy...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sympy.
> To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/fc8c58e9-1ec8-4c2b-8e57-89017dc01100%40googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

[Ralf Stephan]

On Thursday, January 1, 2015 10:38:06 PM UTC+1, Mateusz Paprocki wrote:

mpmath implements PSLQ algorithm, thought it might be insufficient for
the problem your're solving.

No, it's fine. Many thanks. 

[Ralf Stephan]

Actually, it's not sufficient, so I'm trying my hands on LLL. 

[Ralf Stephan]

I'm thinking about implementing a formula guesser for C-finite integer sequences.

There is now a working implementation at https://github.com/sympy/sympy/pull/8811

and I want to resolve here two questions posed by Sergey.

Initially, I used the name "guess" to do 1. finding of linear recurrence and 2. putting

into rsolve() for the closed form. Sergey thinks the user can figure out 2) herself, and

so needs a command just for 1). All in all there are three possibilities:

A. leave it as is with the name "guess" or a better one;

B. instead have "find_linear_recurrence" or just "find_recurrence";

C. have both A) and B)

As this is of general interest and should be done right at the start, please weigh

in with your choice of A/B/C and the name(s) to use.

Regards,

PS: I figured out I didn't need the LLL after all  8)

[Joachim Durchholz]

Am 12.01.2015 um 15:18 schrieb Ralf Stephan:
>
> Initially, I used the name "guess" to do 1. finding of linear recurrence
> and 2. putting
> into rsolve() for the closed form. Sergey thinks the user can figure out 2)
> herself, and
> so needs a command just for 1). All in all there are three possibilities:
>
> A. leave it as is with the name "guess" or a better one;
> B. instead have "find_linear_recurrence" or just "find_recurrence";
> C. have both A) and B)

If the result of (1) could conceivably every be useful to anybody else
without having it put (2), then (1) should go into a separate function.

You can still offer a second function that does the guess+rsolve combo.

Don't worry too much about getting it right from the start.
It's too easy to fine-tune some minor detail, but only after the code
hits the road will people find the glaring omission, easy to see in
20/20 hindsight.
IOW it's more important to make the code flexible and easy to change
rather than to make it perfect - perfection requires multiple iterations
and, more often than not, a full rewrite or two (or three or four...
been there, done that, got all the t-shirts...)

Just my 2c.