# Tagged Questions

43 views

### Real roots of a quintic polynomial with constraints

This is a question on the edge of math and programming. I pondered about the best way to state the problem: should I provide context, or get straight to the point of the question? Given various ...
35 views

### Question about Horners rule algorithm

I am studying Horner's rule I have a question about an algorithm I found here . I understand that the rule allows you to break down polynomials in to monomials to solve them more easily, so that for ...
30 views

### Fast Fourier Transformation: inverse transform of the product of polynomials

I have managed to implement and understand most of the Fast Fourier Transformation. However, I have one last question. If one has two polynomials, say $A(x)$ and $B(x)$, and one computes DFT of ...
54 views

### Solving polynomial to get all coefficients

Given an array of N integers where N can go upto 10^4 and each element can be upto 10^5. Now i need to find the coefficients of polynomial p that is given as : ...
88 views

### Most Efficient Method to Find Roots of Polynomial [duplicate]

I am designing a software that has to find the roots of polynomials. I have to write this software from scratch as opposed to using an already existing library due to company instructions. I currently ...
40 views

### Efficient Extended GCD Algorithm for Polynomials

For computing the GCD of two multivariate polynomials we have the Euclidian algorithm. However, it's well known that the Euclidian algorithm is not very efficient (because of intermediate expression ...
61 views

### Find an algorithm to evaluate unknown polynomial of degree $n$ given its values for $x=0,x=1, x=2,\ldots,x=n$

Given $n+1$ values ($P(0),P(1), P(2),\ldots,P(n)$) of unknown polynomial $P(x)$ of degree $n$ find an algorithm that works in $O(n^2)$ for evaluating $P(n+1), P(n+2),\ldots,P(2n)$. Given $n+1$ values ...
36 views

### find the polynomial if we know its output

$f$ is a polynomial of integral coefficient.Now suppose we have a computer program to find out its output taken in $\mathbb{Z}$.Is it possible for us to find out this polynomial in finitely many ...
22 views

### Factorisation algorithm for polynomials in several variables over $\mathbb{Z}$.

What algorithm is used by a CAS to decide how to factor a polynomial in several variables over $\mathbb Z$?
54 views

14 views

### Are these computational models equivalent?

Let $f : X \to Y$ be a problem that you want to compute. Say we have an $O(1)$-computable maps, $\phi, \psi$, such that $X \xrightarrow{\phi} (\Bbb{Z}_n)^k \xrightarrow{\psi} Y$. After all, ...
58 views

54 views

### Computational Complexity of Algorithms

I want to know if the following proposition is correct or not? For any integer k, there exists an problem P for which, the minimum possible time complexity of any solution algorithm is ...
88 views

### what if geometric sequence + geometric sequence

I wrote a program that basicly can find the formula of the sequence that created with any-degree equation. For example if you give my program that sequence: [1926, 2811, 833240, 28778265, 398155842, ...
143 views

61 views

### Positive Semidefiniteness of a polynomial.

I have a multivariate polynomial $p(x_1,\ldots,x_n)$ and I wish to check if it is positive semidefinite over $R^n$. I can always choose any direction $\vec{v}$ and check that the univariate polynomial ...
349 views

### Recursive FFT java implementation

Given below is my java program for FFT. For the input {0,2,3,-1} its returns a false output in complex point representation. ...
107 views

### Multiplying Polynomials with fewer coefficient multiplications

Not sure how this works! Apparently it can be done in 5-6 multiplications Show how to multiply two degree 2 polynomials using fewer multiplications of coefficients than the naive algorithm.
490 views

### Finding all roots of polynomial system (numerically)

I want to numerically find all the roots of a system of polynomials (n equations in n variables). Since I can compute the Jacobian for the system (analytically or otherwise), I can use the Newton ...
294 views

### Roots of rational equation with multiple variables?

Let's say we have a rational polynomial in $k$ variables. We are only interested in rational solutions. If $k = 1$, name the variables ${x}$, if $k = 2$, name them ${x,y}$. For $k = 1$, it can be ...
### Trying to sort the coefficients of the polynomial $(z-a)(z-b)(z-c)…(z-n)$ into a vector
So I have a factored polynomial of the form $(z-a)(z-b)(z-c)\ldots(z-n)$ for $n$ an even positive integer. Thus the coefficient of $z^k$ for $0 \le k < n$ will be the sum of all distinct $n-k$ ...