Roots.h File Reference

Root-finders for polynomial of arbitrary degree. More...

#include "pbat/warning/Push.h"
#include "pbat/warning/OldStyleCast.h"
#include "pbat/warning/SignConversion.h"
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdlib>
#include <cstring>
#include <limits>
#include <type_traits>
#include <immintrin.h>
#include "pbat/warning/Pop.h"
#include "pbat/Aliases.h"
#include <array>
#include <utility>

Go to the source code of this file.

Namespaces
namespace	pbat
	The main namespace of the library.
namespace	pbat::math
	Math related functionality.
namespace	pbat::math::polynomial
	The namespace for the Polynomial module.

Macros
#define	_CY_CORE_H_INCLUDED_
#define	_CY_CORE_MEMCPY_LIMIT   256
#define	_CY_COMPILER_UNKNOWN
#define	_CY_COMPILER_VER_MEETS(msc, gcc, clang, intel)
#define	_CY_COMPILER_VER_BELOW(msc, gcc, clang, intel)
#define	constexpr
#define	_CY_TEMPLATE_ALIAS_UNPACK(...)
#define	_CY_TEMPLATE_ALIAS(template_name, template_equivalent)
#define	restrict
#define	CY_NODISCARD
#define	CY_CLASS_FUNCTION_DEFAULT
#define	CY_CLASS_FUNCTION_DELETE
#define	nodefault   default:
#define	_CY_IVDEP
#define	_CY_IVDEP_FOR   _CY_IVDEP for
#define	_CY_CRT_SECURE_NO_WARNINGS
#define	_CY_CRT_SECURE_RESUME_WARNINGS
#define	_CY_POLYNOMIAL_H_INCLUDED_
#define	_CY_POLY_TEMPLATE_B
#define	_CY_POLY_TEMPLATE_BC   template <bool boundError = false, typename RootCallback>
Polynomial Root Finding Functions
These functions find polynomial roots. They can be limited to a finite bounds between xMin and xMax. Functions for degree 3 and higher polynomials use numerical root finding. By default, they use Newton iterations defined in RootFinderNewton as their numerical root finding method, but they can also be used with a custom class that provides the same interface. The given xError parameter is passed on to the numerical root finder. The default value is 0, which aims to find the root up to numerical precision. This might be too slow. Therefore, for a high-performance implementation, it is recommended to use a non-zero error threshold for xError. If boundError is false (the default value), RootFinderNewton does not guarantee satisfying the error bound xError, but it almost always does. Keeping boundError false is recommended for improved performance.
#define	_CY_POLY_TEMPLATE_N
#define	_CY_POLY_TEMPLATE_R
#define	_CY_POLY_TEMPLATE_A
#define	_CY_POLY_TEMPLATE_D
#define	_CY_POLY_TEMPLATE_NC
#define	_CY_POLY_TEMPLATE_RC
#define	_CY_POLY_TEMPLATE_AC

Typedefs
template<class T, auto N>
using	pbat::math::polynomial::detail::CArray = T[N]
	C-style array alias.

Functions
template<auto N, class TScalar = Scalar>
bool	pbat::math::polynomial::HasRoot (std::array< TScalar, N+1 > const &coeffs, TScalar min=std::numeric_limits< TScalar >::lowest(), TScalar max=std::numeric_limits< TScalar >::max())
	Check if a polynomial has a root in the range [min,max].
template<auto N, class TScalar = Scalar>
std::array< TScalar, N >	pbat::math::polynomial::Roots (std::array< TScalar, N+1 > const &coeffs, TScalar min=std::numeric_limits< TScalar >::lowest(), TScalar max=std::numeric_limits< TScalar >::max())
	Computes all real roots of a degree N polynomial in the range [min,max].
template<auto N, class FOnRoot, class TScalar = Scalar>
bool	pbat::math::polynomial::ForEachRoot (FOnRoot &&fOnRoot, std::array< TScalar, N+1 > const &coeffs, TScalar min=std::numeric_limits< TScalar >::lowest(), TScalar max=std::numeric_limits< TScalar >::max())
	Computes the each real root of a degree N polynomial in the range [min,max] in increasing order.

Detailed Description

Root-finders for polynomial of arbitrary degree.

Author

Quoc-Minh Ton-That (tonth.nosp@m.at.q.nosp@m.uocmi.nosp@m.nh@g.nosp@m.mail..nosp@m.com)

We lightly wrap Cem Yuksel's cyCodeBase polynomial root-finding functions to work in our codebase.

See [16]

Date

2025-02-27

Copyright

Copyright (c) 2025

Macro Definition Documentation

_CY_COMPILER_VER_BELOW

#define _CY_COMPILER_VER_BELOW	(		msc,
			gcc,
			clang,
			intel )

Value:

false

_CY_COMPILER_VER_MEETS

#define _CY_COMPILER_VER_MEETS	(		msc,
			gcc,
			clang,
			intel )

Value:

false

_CY_POLY_TEMPLATE_A

#define _CY_POLY_TEMPLATE_A

Value:

    template <typename ftype> \
    CY_NODISCARD inline

_CY_POLY_TEMPLATE_AC

#define _CY_POLY_TEMPLATE_AC

Value:

    template <typename ftype, typename RootCallback> \
    inline

_CY_POLY_TEMPLATE_B

#define _CY_POLY_TEMPLATE_B

Value:

    template <bool boundError = false> \
    CY_NODISCARD

_CY_POLY_TEMPLATE_D

#define _CY_POLY_TEMPLATE_D

Value:

    template <typename ftype> \
    inline

_CY_POLY_TEMPLATE_N

#define _CY_POLY_TEMPLATE_N

Value:

    template <                                  \
        int N,                                  \
        typename ftype,                         \
        bool boundError     = false,            \
        typename RootFinder = RootFinderNewton> \
    CY_NODISCARD inline

_CY_POLY_TEMPLATE_NC

#define _CY_POLY_TEMPLATE_NC

Value:

    template <                                  \
        int N,                                  \
        typename ftype,                         \
        bool boundError     = false,            \
        typename RootFinder = RootFinderNewton, \
        typename RootCallback>                  \
    inline

_CY_POLY_TEMPLATE_R

#define _CY_POLY_TEMPLATE_R

Value:

    template <typename ftype, bool boundError = false, typename RootFinder = RootFinderNewton> \
    CY_NODISCARD inline

_CY_POLY_TEMPLATE_RC

#define _CY_POLY_TEMPLATE_RC

Value:

    template <                                  \
        typename ftype,                         \
        bool boundError     = false,            \
        typename RootFinder = RootFinderNewton, \
        typename RootCallback>                  \
    inline

_CY_TEMPLATE_ALIAS

#define _CY_TEMPLATE_ALIAS	(		template_name,
			template_equivalent )

Value:

        using template_name = _CY_TEMPLATE_ALIAS_UNPACK template_equivalent

_CY_TEMPLATE_ALIAS_UNPACK

#define _CY_TEMPLATE_ALIAS_UNPACK

(

...

)

Value:

__VA_ARGS__

CY_CLASS_FUNCTION_DEFAULT

#define CY_CLASS_FUNCTION_DEFAULT

Value:

        {                             \
        }

CY_CLASS_FUNCTION_DELETE

#define CY_CLASS_FUNCTION_DELETE

Value:

        {                                                    \
            static_assert(false, "Calling deleted method."); \
        }