Martin Rubey wrote:
>
> Waldek Hebisch <[EMAIL PROTECTED]> writes:
>
> > Martin Rubey wrote:
>
> > > The hard part is to get the asymptotic at infinity :-) As far as I know,
> > > functions of the form
> > >
> > > (a+b*n)^n*q(n)
> > >
> > > (a,b are fractions, q a rational function) does not necessarily satisfy a
> > > difference equation.
> > >
> >
> > Hmm, if f(n) = (a+b*n)^nW_1(n)/W_2(n) and W_2(n+1) and W_2(n) are non-zero,
> > then we have
> >
> > W_2(n+1)*W_1(n)*f(n+1) = (a+n*n)*W_2(n)*W_1(n+1)*f(n) (**)
>
> No, I don't think so:
>
> (a+b*(n+1))^(n+1) / (a+b*n)^n is not rational.
>
You are right: we get rational function only when b = 0.
Still, I think we can get something: assume nonzero a and write
(a + b*n) = a*(1 + c*n) where c = b/a. Now
g(n) = (1 + c*n)^{-n}f(n) = a^nW_1(n)/W_2(n)
In your method you build system of equations for a and b such that
(a+b*n)^{-n} is rational. We probably can build equation in c
such that when c solves this eqation than (1 + c*n)^{-n}f(n) is
of form a^nW_1(n)/W_2(n). I expect equation for c to be of
higher degree than equations for a and b. But having only one
variable should give us a win.
Another obserwation:
(5) -> guessExpRat [myPol(i) for i in 1..8]
3 2 n
(5) [[function= (n + 3n + 2n + 1)1 ,order= 0]]
Type: List(Record(function: Expression(Integer),order: NonNegativeInteger))
Time: 0.004 (IN) + 5.23 (EV) + 0.004 (OT) = 5.24 sec
(6) -> guessExpRat [myPol(i) :: PrimeField(67108879) for i in 1..8]
3 2 n
(6) [[function= (n + 3n + 2n + 1)1 ,order= 0]]
Type: List(Record(function: Expression(Integer),order: NonNegativeInteger))
Time: 0.01 (IN) + 0.63 (EV) + 0.01 (OT) = 0.66 sec
(7) -> guessExpRat [myPol(i) :: PrimeField(67108879) for i in 0..8]
3 n
(7) [[function= (n + 67108878n + 1)1 ,order= 0]]
Type: List(Record(function: Expression(Integer),order: NonNegativeInteger))
Time: 0.004 (IN) + 7.29 (EV) + 0.02 (OT) = 7.32 sec
(8) -> guessExpRat [myPol(i) for i in 0..8]
3 n
(8) [[function= (n - n + 1)1 ,order= 0]]
Type: List(Record(function: Expression(Integer),order: NonNegativeInteger))
Time: 0.004 (IN) + 30.04 (EV) + 0.004 (OT) = 30.05 sec
So, modular version is significantly (5 - 10 times) faster than integer
version. I would expect that in many cases modular result will
immediatly give correct a and b, so the speedup would directly
transfer to rational case. Also, at least using sbcl rational
calculation spends a lot of time in bignum arithmetic, so to
make code faster one needs deeper changes. I feel that with
modular aritmetic there is more room for improvement.
--
Waldek Hebisch
[EMAIL PROTECTED]
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups.google.com/group/fricas-devel?hl=en
-~----------~----~----~----~------~----~------~--~---
