### 4 releases

0.4.1 | May 12, 2024 |
---|---|

0.0.4 | Sep 20, 2023 |

0.0.3 | Apr 10, 2023 |

#**203** in Math

**61** downloads per month

**MIT OR Apache-2.0 OR Zlib**

34KB

693 lines

# aberth

An implementation of the Aberth-Ehrlich method for finding the zeros of a polynomial.

Aberth's method uses an electrostatics analogy to model the approximations as negative charges and the true zeros as positive charges. This enables finding all complex roots simultaneously, converging cubically (worst-case it converges linearly for zeros of multiplicity).

This crate is

and tries to have minimal dependencies. It uses
arrayvec
to avoid allocations, which will be removed when rust stabilises support for
const-generics.`#!``[``no_std``]`

## Usage

Add it to your project:

`cargo`` add aberth`

Specify the coefficients of your polynomial in an array in ascending order and
then call the

method on your polynomial.`aberth`

`use` `aberth``::`aberth`;`
`const` `EPSILON``:` `f32` `=` `0.``001``;`
`const` `MAX_ITERATIONS``:` `u32` `=` `10``;`
`//` 0 = -1 + 2x + 4x^4 + 11x^9
`let` polynomial `=` `[``-``1.``,` `2.``,` `0.``,` `0.``,` `4.``,` `0.``,` `0.``,` `0.``,` `0.``,` `11.``]``;`
`let` roots `=` `aberth``(``&`polynomial`,` `MAX_ITERATIONS``,` `EPSILON``)``;`
`//` [
`//` Complex { re: 0.4293261, im: 1.084202e-19 },
`//` Complex { re: 0.7263235, im: 0.4555030 },
`//` Complex { re: 0.2067199, im: 0.6750696 },
`//` Complex { re: -0.3448952, im: 0.8425941 },
`//` Complex { re: -0.8028113, im: 0.2296336 },
`//` Complex { re: -0.8028113, im: -0.2296334 },
`//` Complex { re: -0.3448952, im: -0.8425941 },
`//` Complex { re: 0.2067200, im: -0.6750695 },
`//` Complex { re: 0.7263235, im: -0.4555030 },
`//` ]

The above method does not require any allocation, instead doing all the computation on the stack. It is generic over any size of polynomial, but the size of the polynomial must be known at compile time.

The coefficients of the polynomial may be

, `f32`

, or even complex numbers
`f64`

, `Complex <f32>`

`Complex``<``f64``>`

:`#` `use` `aberth``::``{`aberth`,` Complex`}``;`
`#`
`#` `let` p1 `=` `[``1_``f32``,` `2_``f32``]``;`
`#` `let` r1 `=` `aberth``(``&`p1`,` `10``,` `0.``001``)``;`
`#`
`#` `let` p2 `=` `[``1_``f64``,` `2_``f64``]``;`
`#` `let` r2 `=` `aberth``(``&`p2`,` `10``,` `0.``001``)``;`
`#`
`#` `let` p3 `=` `[``Complex``::`new`(``1_``f32``,` `2_``f32``)``,` `Complex``::`new`(``3_``f32``,` `4_``f32``)``]``;`
`#` `let` r3 `=` `aberth``(``&`p3`,` `10``,` `0.``001``)``;`
`#`
`#` `const` `MAX_ITERATIONS``:` `u32` `=` `10``;`
`#` `const` `EPSILON``:` `f64` `=` `0.``001``;`
`let` polynomial `=` `[``Complex``::`new`(``1_``f64``,` `2_``f64``)``,` `Complex``::`new`(``3_``f64``,` `4_``f64``)``]``;`
`let` roots `=` `aberth``(``&`polynomial`,` `MAX_ITERATIONS``,` `EPSILON``)``;`

If

is available then there is also an `std`

struct which
allocates some memory to support dynamically sized polynomials at run time.
This may also be good to use when you are dealing with polynomials with many
terms, as it uses the heap instead of blowing up the stack.`AberthSolver`

`use` `aberth``::`AberthSolver`;`
`let` `mut` solver `=` `AberthSolver``::`new`(``)``;`
solver`.`epsilon `=` `0.``001``;`
solver`.`max_iterations `=` `10``;`
`//` 0 = -1 + 2x + 4x^3 + 11x^4
`let` a `=` `[``-``1.``,` `2.``,` `0.``,` `4.``,` `11.``]``;`
`//` 0 = -28 + 39x^2 - 12x^3 + x^4
`let` b `=` `[``-``28.``,` `0.``,` `39.``,` `-``12.``,` `1.``]``;`
`for` polynomial `in` `[`a`,` b`]` `{`
`let` roots `=` solver`.``find_roots``(``&`polynomial`)``;`
`//` ...
`}`

Note that the returned values are not sorted in any particular order.

The coefficient of the highest degree term should not be zero.

`#!``[``no_std``]`

`#!``[``no_std``]`To use in a

environment you must disable `no_std`

and enable
the `default-features`

feature:`libm`

`[``dependencies``]`
`aberth = { version = "0.4.1", default-features = false, features ``=` `[``"`libm`"``]` }

## Stability Guarantees

:

`may experience breaking changes even in minor and patch releases`

`mod``internal`We expose the

module, for those interested in supplying their own
initial guesses to `internal`

. However this `internal ::`aberth_raw

`internal`

module is
considered an implementation detail and does not follow the semantic versioning
scheme of the rest of the project.## License

This crate is licensed under any of the Apache license, Version 2.0, or the MIT license, or the Zlib license at your option.

#### Dependencies

~265–395KB