mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Blogorrhea > carpetpool

Reply
 
Thread Tools
Old 2020-12-30, 09:50   #1
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

23·41 Posts
Post Computation of P-Recursive Sequences in Polynomial Time

Is it possible for centered trinomial coefficients to be computed in O(log n) time, analogous to how the time complexity of modular exponentiation is O(log n)?

I am well aware that factorials cannot be computed in logarithmic time, making Wilson's theorem impractical for large numbers.

On the other hand, raising an integer to a power can easily be done in logarithmic time, making Fermat's test practical for large numbers.

Where does computing centered trinomial coefficient (and similar sequences), fall into?

To be clear, central trinomial coefficients are the coefficient of x^n in (x^2 + x + 1)^n for n ≥ 0.

Meanwhile, centered binomial coefficients binomial(2*n, n) are the coefficient of x^n in (x^2 + 2x + 1)^n for n ≥ 0.

Catalan numbers have the form binomial(2*n, n)/(n + 1) for n ≥ 0. I can't name a single algorithm for computing either central binomial coefficients or Catalan numbers in O(log n) time.

Is the same true for centered trinomial coefficients, and if so, why is it impossible to compute any particular term in O(log n) time?
carpetpool is offline   Reply With Quote
Old 2021-01-03, 22:16   #2
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

23×41 Posts
Post

The examples involving Trinomial Coefficients and Catalan numbers (also see here) are examples of P-recursive sequences, which is what I am generally after.

After doing a bit of research, I was able to find this article, which explicitly states that the N-th term of a P-recursive sequence can be computed in no more than O(N^(1/2)) operations. This paper also seems to agree.

Unfortunately, that's not practical for (primality) testing large numbers. That being said, it's not impossible to design an algorithm that can reduce the complexity from almost linear to polynomial time, as is the case of C-recursive sequences (Fibonacci, Lucas, Mersenne,..).

My idea is to reduce the baby-step giant step techniques with something analogous to square-multiply for P-recursive sequences, which I'm sure exists.

If anyone know of a paper that proves otherwise, or some better ideas, please let me know.

Last fiddled with by carpetpool on 2021-01-03 at 22:20
carpetpool is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
recursive relation enzocreti enzocreti 0 2019-04-02 13:39
Can discrete logarithms / factoring be done in P (i.e., deterministic polynomial time)? Raman Factoring 1 2016-05-23 13:44
Having a hard time finding a polynomial for a C138 YuL Msieve 3 2013-11-30 03:16
Recursive Primes? jinydu Lounge 18 2004-06-23 02:36
AKS - A polynomial-time algorithm for testing primality. Maybeso Math 11 2002-11-20 23:39

All times are UTC. The time now is 08:56.


Sun Dec 5 08:56:35 UTC 2021 up 135 days, 3:25, 0 users, load averages: 1.59, 1.63, 1.52

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.