# Polynomial Real Zeros Counter (G Dataflow)

Version:

Calculates the number of zeros of a real polynomial in a real interval. This node does not determine the values of the zeros.

## p(x)

Real polynomial. The first element of the array relates to the constant coefficient of the polynomial.

## start

Leftmost point of the real interval. start must be less than or equal to end.

Default: 0

## end

Rightmost point of the real interval.

Default: 0

## error in

Error conditions that occur before this node runs.

The node responds to this input according to standard error behavior.

Standard Error Behavior

Many nodes provide an error in input and an error out output so that the node can respond to and communicate errors that occur while code is running. The value of error in specifies whether an error occurred before the node runs. Most nodes respond to values of error in in a standard, predictable way.

error in does not contain an error error in contains an error
If no error occurred before the node runs, the node begins execution normally.

If no error occurs while the node runs, it returns no error. If an error does occur while the node runs, it returns that error information as error out.

If an error occurred before the node runs, the node does not execute. Instead, it returns the error in value as error out.

Default: No error

## number of zeros

Number of zeros of the real polynomial in the interval.

## error out

Error information.

The node produces this output according to standard error behavior.

Standard Error Behavior

Many nodes provide an error in input and an error out output so that the node can respond to and communicate errors that occur while code is running. The value of error in specifies whether an error occurred before the node runs. Most nodes respond to values of error in in a standard, predictable way.

error in does not contain an error error in contains an error
If no error occurred before the node runs, the node begins execution normally.

If no error occurs while the node runs, it returns no error. If an error does occur while the node runs, it returns that error information as error out.

If an error occurred before the node runs, the node does not execute. Instead, it returns the error in value as error out.

## Algorithm for Calculating the Number of Zeros of a Real Polynomial

This node uses the Sturm algorithm to calculate the number of zeros. Let p(x) be a real polynomial in x and let p'(x) be the derivative of p(x). If d(x) denotes the greatest common divisor (GCD) of p(x) and p'(x), such that

d(x) = gcd(p(x), p'(x))

Then p(x) has multiple zeros, if d(x) is a nonconstant polynomial. In other words, the polynomial p(x)/d(x) has only single zeros.

Repeating this idea, you can combine p(x) as the product of simple polynomials, each of which has single real zeros. The number of zeros of p(x) is equal to the sum of all zeros of the defined simple polynomials that have only single zeros.

## How to Determine the Zeros of a Real Polynomial

To determine the number of zeros of a real polynomial p(x) with the single zero property, use the following Euclidean algorithm:

$p\left(x\right)={q}_{1}\left(x\right){p}_{1}\left(x\right)-{p}_{2}\left(x\right)\phantom{\rule{0ex}{0ex}}{p}_{1}\left(x\right)={q}_{2}\left(x\right){p}_{2}\left(x\right)-{p}_{3}\left(x\right)\phantom{\rule{0ex}{0ex}}⋮\phantom{\rule{0ex}{0ex}}{p}_{r-2}\left(x\right)={q}_{r-1}\left(x\right){p}_{r-1}\left(x\right)-{p}_{r}\left(x\right)$

The Sturm's chain (p(x), p1(x), ..., pr(x)) determines the two values W(start) and W(end), where W(x) is the number of sign changes of the Sturm's chain.

The number of all zeros of p(x) is exactly equal to W(end) - W(start).

## How to Determine All Real Zeros of a Real Polynomial

To determine all real zeroes of a real polynomial, choose start and end that satisfies the following conditions:

$\text{start}=-\mathrm{max}\left\{\frac{\left(|{a}_{0}|+\dots +|{a}_{n-1}|\right)}{|{a}_{n}|},1\right\}$
$end=\mathrm{max}\left\{\frac{\left(|{a}_{0}|+\dots +|{a}_{n-1}|\right)}{|{a}_{n}|},1\right\}$

where a0, a1, ..., an are the elements of the polynomial.

Where This Node Can Run:

Desktop OS: Windows

FPGA: This product does not support FPGA devices