BRL-CAD
poly.h
Go to the documentation of this file.
1 /* P O L Y . H
2  * BRL-CAD
3  *
4  * Copyright (c) 2004-2014 United States Government as represented by
5  * the U.S. Army Research Laboratory.
6  *
7  * This library is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU Lesser General Public License
9  * version 2.1 as published by the Free Software Foundation.
10  *
11  * This library is distributed in the hope that it will be useful, but
12  * WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14  * Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public
17  * License along with this file; see the file named COPYING for more
18  * information.
19  */
20 
21 /*----------------------------------------------------------------------*/
22 /* @file poly.h */
23 /** @addtogroup poly */
24 /** @{ */
25 
26 /**
27  * @brief Library for dealing with polynomials.
28  */
29 
30 #ifndef BN_POLY_H
31 #define BN_POLY_H
32 
33 #include "common.h"
34 #include "bu/magic.h"
35 #include "bn/defines.h"
36 #include "bn/complex.h"
37 
39 
40 /* This could be larger, or even dynamic... */
41 #define BN_MAX_POLY_DEGREE 6 /* Maximum Poly Order */
42 
43 /**
44  * Polynomial data type
45  * bn_poly->cf[n] corresponds to X^n
46  */
47 typedef struct bn_poly {
48  uint32_t magic;
49  size_t dgr;
51 } bn_poly_t;
52 
53 #define BN_CK_POLY(_p) BU_CKMAG(_p, BN_POLY_MAGIC, "struct bn_poly")
54 #define BN_POLY_NULL ((struct bn_poly *)NULL)
55 #define BN_POLY_INIT_ZERO { BN_POLY_MAGIC, 0, {0.0} }
56 
57 
58 /**
59  * bn_poly_mul
60  *
61  * @brief
62  * multiply two polynomials
63  */
64 BN_EXPORT extern struct bn_poly *bn_poly_mul(struct bn_poly *product,
65  const struct bn_poly *m1,
66  const struct bn_poly *m2);
67 
68 /**
69  * bn_poly_scale
70  *
71  * @brief
72  * scale a polynomial
73  */
74 BN_EXPORT extern struct bn_poly *bn_poly_scale(struct bn_poly *eqn,
75  double factor);
76 
77 /**
78  * bn_poly_add
79  * @brief
80  * add two polynomials
81  */
82 BN_EXPORT extern struct bn_poly *bn_poly_add(struct bn_poly *sum,
83  const struct bn_poly *poly1,
84  const struct bn_poly *poly2);
85 
86 /**
87  * bn_poly_sub
88  * @brief
89  * subtract two polynomials
90  */
91 BN_EXPORT extern struct bn_poly *bn_poly_sub(struct bn_poly *diff,
92  const struct bn_poly *poly1,
93  const struct bn_poly *poly2);
94 
95 /**
96  * @brief
97  * Divides any polynomial into any other polynomial using synthetic
98  * division. Both polynomials must have real coefficients.
99  */
100 BN_EXPORT extern void bn_poly_synthetic_division(struct bn_poly *quo,
101  struct bn_poly *rem,
102  const struct bn_poly *dvdend,
103  const struct bn_poly *dvsor);
104 
105 /**
106  *@brief
107  * Uses the quadratic formula to find the roots (in `complex' form) of
108  * any quadratic equation with real coefficients.
109  *
110  * @return 1 for success
111  * @return 0 for fail.
112  */
113 BN_EXPORT extern int bn_poly_quadratic_roots(struct bn_complex roots[],
114  const struct bn_poly *quadrat);
115 
116 /**
117  *@brief
118  * Uses the cubic formula to find the roots (in `complex' form)
119  * of any cubic equation with real coefficients.
120  *
121  * to solve a polynomial of the form:
122  *
123  * X**3 + c1*X**2 + c2*X + c3 = 0,
124  *
125  * first reduce it to the form:
126  *
127  * Y**3 + a*Y + b = 0,
128  *
129  * where
130  * Y = X + c1/3,
131  * and
132  * a = c2 - c1**2/3,
133  * b = (2*c1**3 - 9*c1*c2 + 27*c3)/27.
134  *
135  * Then we define the value delta, D = b**2/4 + a**3/27.
136  *
137  * If D > 0, there will be one real root and two conjugate
138  * complex roots.
139  * If D = 0, there will be three real roots at least two of
140  * which are equal.
141  * If D < 0, there will be three unequal real roots.
142  *
143  * Returns 1 for success, 0 for fail.
144  */
145 BN_EXPORT extern int bn_poly_cubic_roots(struct bn_complex roots[],
146  const struct bn_poly *eqn);
147 
148 /**
149  *@brief
150  * Uses the quartic formula to find the roots (in `complex' form)
151  * of any quartic equation with real coefficients.
152  *
153  * @return 1 for success
154  * @return 0 for fail.
155  */
156 BN_EXPORT extern int bn_poly_quartic_roots(struct bn_complex roots[],
157  const struct bn_poly *eqn);
158 
159 BN_EXPORT extern int bn_poly_findroot(bn_poly_t *eqn,
160  bn_complex_t *nxZ,
161  const char *str);
162 
163 BN_EXPORT extern void bn_poly_eval_w_2derivatives(bn_complex_t *cZ,
164  bn_poly_t *eqn,
165  bn_complex_t *b,
166  bn_complex_t *c,
167  bn_complex_t *d);
168 
169 BN_EXPORT extern int bn_poly_checkroots(bn_poly_t *eqn,
170  bn_complex_t *roots,
171  int nroots);
172 
173 BN_EXPORT extern void bn_poly_deflate(bn_poly_t *oldP,
174  bn_complex_t *root);
175 
176 BN_EXPORT extern int bn_poly_roots(bn_poly_t *eqn,
177  bn_complex_t roots[],
178  const char *name);
179 
180 /**
181  * Print out the polynomial.
182  */
183 BN_EXPORT extern void bn_pr_poly(const char *title,
184  const struct bn_poly *eqn);
185 
186 /**
187  * Print out the roots of a given polynomial (complex numbers)
188  */
189 BN_EXPORT extern void bn_pr_roots(const char *title,
190  const struct bn_complex roots[],
191  int n);
192 
194 
195 #endif /* BN_POLY_H */
196 /** @} */
197 /*
198  * Local Variables:
199  * mode: C
200  * tab-width: 8
201  * indent-tabs-mode: t
202  * c-file-style: "stroustrup"
203  * End:
204  * ex: shiftwidth=4 tabstop=8
205  */
fastf_t cf[BN_MAX_POLY_DEGREE+1]
Definition: poly.h:50
struct bn_poly * bn_poly_sub(struct bn_poly *diff, const struct bn_poly *poly1, const struct bn_poly *poly2)
subtract two polynomials
int bn_poly_quartic_roots(struct bn_complex roots[], const struct bn_poly *eqn)
Uses the quartic formula to find the roots (in `complex' form) of any quartic equation with real coef...
#define BN_MAX_POLY_DEGREE
Library for dealing with polynomials.
Definition: poly.h:41
Definition: clone.c:90
void bn_pr_roots(const char *title, const struct bn_complex roots[], int n)
int bn_poly_quadratic_roots(struct bn_complex roots[], const struct bn_poly *quadrat)
Uses the quadratic formula to find the roots (in `complex' form) of any quadratic equation with real ...
Header file for the BRL-CAD common definitions.
Definition: poly.h:47
void bn_poly_synthetic_division(struct bn_poly *quo, struct bn_poly *rem, const struct bn_poly *dvdend, const struct bn_poly *dvsor)
Divides any polynomial into any other polynomial using synthetic division. Both polynomials must have...
struct bn_poly * bn_poly_mul(struct bn_poly *product, const struct bn_poly *m1, const struct bn_poly *m2)
multiply two polynomials
size_t dgr
Definition: poly.h:49
bn_poly_t quo[1]
struct bn_poly bn_poly_t
struct bn_poly * bn_poly_scale(struct bn_poly *eqn, double factor)
scale a polynomial
#define __BEGIN_DECLS
Definition: common.h:73
struct bn_poly * bn_poly_add(struct bn_poly *sum, const struct bn_poly *poly1, const struct bn_poly *poly2)
add two polynomials
void bn_poly_eval_w_2derivatives(bn_complex_t *cZ, bn_poly_t *eqn, bn_complex_t *b, bn_complex_t *c, bn_complex_t *d)
int bn_poly_findroot(bn_poly_t *eqn, bn_complex_t *nxZ, const char *str)
void bn_pr_poly(const char *title, const struct bn_poly *eqn)
int bn_poly_cubic_roots(struct bn_complex roots[], const struct bn_poly *eqn)
Uses the cubic formula to find the roots (in `complex' form) of any cubic equation with real coeffici...
uint32_t magic
Definition: poly.h:48
int bn_poly_checkroots(bn_poly_t *eqn, bn_complex_t *roots, int nroots)
#define __END_DECLS
Definition: common.h:74
Complex numbers.
Definition: complex.h:39
bn_poly_t rem[1]
void bn_poly_deflate(bn_poly_t *oldP, bn_complex_t *root)
double fastf_t
Definition: defines.h:300
int bn_poly_roots(bn_poly_t *eqn, bn_complex_t roots[], const char *name)