1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
|
#ifndef _KPOINT1D_H
#define _KPOINT1D_H
#include <cassert>
#include <cstdlib>
#include <iostream>
#include <bigrational.h>
#include <root1.h>
#include <kratpoly.h>
using namespace std;
class K_POINT1D
{
friend class K_POINT2D;
mutable unsigned int type; // type == 1 if ROOT1
// 2 if bigrational
mutable ROOT1* PtR; // the interval for *this, 0 if type == 2
mutable bigrational PtB; // the point for *this, undefined if type == 1
K_RATPOLY* poly; // a polynomial that vanished at *this
unsigned long ref_count; // reference counter
// stream
ostream& output(ostream&) const;
// primitive
// int cut(const bigrational& b) const
// cut *this at the point b, i.e.,
// refine the interval for *this
// by setting get_low() or get_high() to be b.
int cut(const bigrational&) const;
// int halve() const
// cut *this at the point half that halves the interval for *this, i.e.,
// refine the interval for *this
// by setting get_low() or get_high() to be half.
int halve() const;
// int reduce(const unsigned long num_bits) const
// reduce *this s.t.
// [get_low(), get_high()] will contain all the numbers
// approximated by float_est to num_bits precision.
// return 1 if some reduction occurs and
// 0 otherwise.
int reduce(const unsigned long) const;
// int contract(const bigrational& tol) const
// contract *this s.t. [get_low(), get_high()] will be no larger than tol.
int contract(const bigrational&) const;
// int shrink(const bigrational& fac) const
// shrink *this s.t. [get_low(), get_high()] will become smaller by fac.
// e.g. fac == 1/10 => [get_low(), get_high()] becomes 1/10.
int shrink(const bigrational&) const;
// int K_POINT1D :: separate(const K_POINT1D& x) const
// separate *this and x s.t. they will not overlap.
// POSSIBLY DOES NOT TERMINATE.
int separate(const K_POINT1D&) const;
// arithmetic
// K_POINT1D add(const K_POINT1D& x) const
// return *this + x
K_POINT1D add(const K_POINT1D&) const;
// K_POINT1D sub(const K_POINT1D& x) const
// return *this - x
K_POINT1D sub(const K_POINT1D&) const;
// K_POINT1D mul(const K_POINT1D& x) const
// return *this * x
K_POINT1D mul(const K_POINT1D&) const;
// K_POINT1D div(const K_POINT1D& x) const
// return *this / x
K_POINT1D div(const K_POINT1D&) const;
public:
// constructors, assignment and destructor
// K_POINT1D()
// constructs a type 0 instance.
K_POINT1D();
// K_POINT1D(const ROOT1& r)
// construct a type1 instance from ROOT1 r.
// r.num_root must have been 1.
K_POINT1D(const ROOT1&);
// K_POINT1D(const ROOT1& r)
// construct a type1 instance from ROOT1 r of a root of K_RATPOLY P.
// r.num_roots must have been 1.
K_POINT1D(const ROOT1&, const K_RATPOLY&);
// K_POINT1D(const bigrational& b)
// construct a type2 instance from bigrational b.
K_POINT1D(const bigrational&);
// K_POINT1D(const bigrational& b, const K_RATPOLY& P)
// construct a type2 instance from bigrational b and K_RATPOLY P.
// P must vanish at b.
K_POINT1D(const bigrational&, const K_RATPOLY&);
K_POINT1D(const K_POINT1D&);
K_POINT1D& operator =(const K_POINT1D&);
~K_POINT1D();
// stream
friend ostream& operator <<(ostream&, const K_POINT1D&);
// primitive
bigrational get_low() const;
bigrational get_high() const;
// arithmetic
friend K_POINT1D operator +(const K_POINT1D&, const K_POINT1D&);
friend K_POINT1D operator -(const K_POINT1D&, const K_POINT1D&);
friend K_POINT1D operator *(const K_POINT1D&, const K_POINT1D&);
friend K_POINT1D operator /(const K_POINT1D&, const K_POINT1D&);
// comparison
// int compare(const K_POINT1D& x) const
// return 1 if *this > x,
// 0 if *this == x, and
// - 1 if *this < x.
int compare(const K_POINT1D&) const;
// int compare(const bigrational& b) const
// return 1 if *this > b,
// 0 if *this == b, and
// - 1 if *this < b.
int compare(const bigrational&) const;
// int sort(K_POINT1D** const X, const unsigned long n)
// perform insertion sort on the array X of length n.
// return 1 if elements are distinct and
// 0 otherwise.
friend int sort(K_POINT1D** const, const unsigned long);
// int overlap(const K_POINT1D& x) const
// return 1 if *this and x overlap, and
// 0 otherwise.
int overlap(const K_POINT1D&) const;
// get_pts(): get algebraic points
// unsigned long get_pts(const bigrational& l, const bigrational& h,
// const K_RATPOLY& P,
// K_POINT1D**& pts,
// const bigrational& tol, const int count_endpts)
// computes the roots "pts" of a univariate polynomial P
// on/in the interval [l, h].
// returns the number of roots.
// if tol > 0 then an interval for each root is no larger than tol.
// if tol = 0 then there is no limit on the size of intervals for roots.
// if count_endpts = 1 then
// the roots at the endpoints of the interval [l, h] are counted.
// if count_endpts = 0 then
// the roots on the endpoints of the interval [l, h] are ignored.
friend unsigned long get_pts(const bigrational&, const bigrational&,
const K_RATPOLY&,
K_POINT1D**&,
const bigrational&, const int);
// unsigned long get_all_pts(const K_RATPOLY& P,
// K_POINT1D**& pts,
// const bigrational& tol)
// computes all the intersections "pts" of a univariate polynomials P.
// returns the number of roots.
// if tol > 0 then an interval for each root is no larger than tol.
// if tol = 0 then there is no limit on the size of intervals for roots.
friend unsigned long get_all_pts(const K_RATPOLY&,
K_POINT1D**&,
const bigrational);
// other
friend unsigned long match_intervals(const bigrational* const,
const bigrational* const,
const unsigned long,
K_POINT1D** const,
long*&,
const unsigned long);
friend unsigned long get_pts_interior(const bigrational&, const bigrational&,
const bigrational&, const bigrational&,
const K_RATPOLY&, const K_RATPOLY&,
K_POINT2D**&,
const bigrational&);
friend int refine_interior(K_POINT1D* const, K_POINT1D* const,
const K_RATPOLY&, const K_RATPOLY&,
K_POINT2D*&,
const bigrational&);
};
#endif
|
