-
Notifications
You must be signed in to change notification settings - Fork 1
/
TODO
282 lines (206 loc) · 8.9 KB
/
TODO
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
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
TODO :
------
+++++++++++++++++++++++++
++++ Primay Functions ***
+++++++++++++++++++++++++
+ Linear Algebra over the Matrix.
==> WIP (See t-matrix.c)
+ Factorisation over Z (Distinc Degree Factorisation + Cantor-Zassenhaus) / Modular Factorisation (?)
==> Factorisation over R or C
+ Limits (Gruntz)
==> Need linear algebra and factorization.
+ Undefined sum:
sum(x^k, k=1..N)= ?
+ Integration:
==> Poor Man Integrator (See http://www-sop.inria.fr/cafe/Manuel.Bronstein/pmint/ )
++++++++++++++++++++
++++ Extensions +++
++++++++++++++++++++
+ MODULO(P,A)
A : integer or polynom
+ MATRIX
+ Rewite how the extensions are handled.
Create a Jump Table Matrix
with types as column,
with function as line.
Each function becomes a direct call to this matrix:
typedef may_t (*func_t)(may_t);
func_t diff_tab[256];
may_t diff_recur_c(may_t x)
{
if (MAY_UNLIKELY (MAY_NUM_P (x)))
return MAY_ZERO;
return diff_tab[MAY_TYPE(x)](x);
}
Registering an extension will fill in theses tables.
Registering a function will need a default function to use.
void may_func_register(diff_table, default_diff);
==> Faster extension (as fast as native types)
==> Fast indirect call (memory is not pollutated with other data)
==> As the tables uses 256 entries, no mask nor comparaison is needed.
==> Behavior can be regrouped by function (behavior of exp for diff, eval, ...)
Most of the switch cases already use an implicit indirect table.
How the init code shall be handled ?
+++++++++++++++++++++++++++++++++
++++ Basic Operations +++
+++++++++++++++++++++++++++++++++
may_t may_optimize_indets (may_t list_var).
Optimize the list of dependencies by looking for algebric dependencies.
==> How to do?
may_t may_reduce (may_t x)
Compute the list of variables, and use it to reduce / simplify the expression.
may_t may_normal (may_t x);
"Normal" form of an expression.
Two equal expressions should have the same normal representation
or at least the difference between them should be zero.
(sqrtsimp, rectform, normalsign, reduce, rationalize)
How to handle (sqrt(2)-x)/(2-x^2) ?
int may_equal_p (may_t a, may_tb)
Return may_zero_p (may_normal (a-b))
may_t may_expsimp (may_t x);
Simplify expression using exp / log
==> Difference with may_reduce?
may_t may_trigsimp (may_t x);
Simplify expression using cos / sin / tan
==> Difference with may_reduce?
==> Replace with half andle? sin(x)=2*t/(1+t^2) avec t=tan(x/2)
int may_upoly_p (may_t x, may_domain_e domain, may_t var)
Test if 'x' is an univariated polynom of the variable 'var' with the coefficients in the domain 'domain'.
Return 0 if failure, 1 if success, 2 if success AND all the coefficients are pure numbers.
may_t may_upoly_coeff (may_t x, may_t var, mpz_srcptr deg)
may_t may_mod (may_t p1, may_t p2, may_t vars)
may_t may_invmod (may_t p1, may_t p2, may_t vars)
Need may_gcdex
may_t may_unmod (a)
Remove any reference to a modulo extension.
may_t may_expand_mod (may_t a, may_t modulus, may_t vars)
Return a developped modulo modulus
may_t may_resultant (may_t a, may_t b, may_t x)
Return the resultant
may_t may_compose(may_t f, may_t g, may_t x)
Assuming f and g are univariate polynomial of x, return f(g(x))
Efficient Algorithm ?
++++++++++++++++++++++++++++++
++++ Amelioration +++
++++++++++++++++++++++++++++++
+ RANGE : Move it as an extension.
==> TBC if good idea.
+ Add support of MAY_OUT_UNIT_CIRCLE and MAY_IN_UNIT_CIRCLE in the predicate.
+ may_ratfactor --> may_unifactor ? --> may_ufactor ?
+ Improve "evalr" to support more function (trigo ?)
+ may_rewrite:
Better algorithm to implement.
+ tests:
Use separate data file to store inputs / expected values .
+ may_match the pattern '$1*x+$2' over 'x' won't work.
==> TBC if needed.
+ "sign(x)^2" can be simplified in 1 except if x is 0.
+ "sign(x)^3" can be simplified in sign(x)
+ 4^(1/2) % 3 = 1 (maple) or 2 (mupad/xcas) ?
Problem of the choice of the root : 4^(1/2) can be 1 or 2 depending on the sign.
+ Define degree(x^-1)
+ ./t-pika "(x+2)*INFINITY" ==> INFINITY+INFINITY*x
Not very useful answer.
+ ./t-pika "tan(5*PI/18)*tan(7*PI/18)*sqrt(3)" -otcollect
==> (cosh(1/2*log(3)-2/3*I*PI)+sinh(1/2*log(3)-2/3*I*PI)-sinh(1/2*log(3)-1/9*I*PI)-cosh(1/2*log(3)-1/9*I*PI)+cosh(1/2*log(3)+2/3*I*PI)+sinh(1/2*log(3)+2/3*I*PI)-sinh(1/2*log(3)+1/9*I*PI)-cosh(1/2*log(3)+1/9*I*PI))/(1-2*cos(1/9*PI))
./t-pika "tan(5*PI/18)*tan(7*PI/18)" -otcollect
==> -(1+2*cos(1/9*PI))/(1-2*cos(1/9*PI))
The sqrt(3) prevents to recollect everything.
+ Finish may_sqrtsimp For:
==> sqrt(30)*sqrt(105) == 15*sqrt(14)
==> (7+5*sqrt(2))^(1/3) --> (1+sqrt(2))
==> 1/(2^(1/2)+3^(1/2)+6^(1/2)) --> 5/23*sqrt(3)-1/23*sqrt(2)*sqrt(3)+7/23*sqrt(2)-12/23 ??
==> 2^(1/4)*(2^(1/2)+2)/(8+6*2^(1/2))^(1/2) --> 1 (Ca a l'air compliquée!!!!)
==> (5-2*3^(1/2)*x-2*2^(1/2)*3^(1/2)+2*2^(1/2)*x+x^2)/(1-2*3^(1/2)*x+x^2)
--> (-sqrt(3)+sqrt(2)+x)/(-sqrt(3)-sqrt(2)+x)
==> (19+15*2^(1/3)+12*2^(2/3))^(1/3) --> 1+2^(1/3)+2^(2/3)
+ polvar shall use a dict and not a list.
+ Rethink the polynomial
Evolve independent, extract, Degree, division and gcd
+ shall not scan an expression to get the degre (Cache the degree in the expression ?)
+ Optional argument: MAY_SINGLE_DEPEND, MAY_FULL_DEPEND for extraction to not check for recursive independency.
+ Change canonical representation of X^(r) with r=RAT into (X^(1/q))^(p) and p/q=r
+++++++++++++++++++++++++
++++ Fix BUGS +++
+++++++++++++++++++++++++
+ may_get_domain is totaly broken.
+ (real(x)+abs(real(x)))/(real(x)+abs(real(x))) ==> 1
But it is not true nearly everywhere.
==> To document ?
+ ./t-eval "(1+x^2+y^3+z^4)^17*(1-x^2+y-z)^15" -oexpand -ogcd "(1+x^2+y^3+z^4)^12*(1-x^2+y-z)^11"
Wrong result
Result shall be the expanded version of (1+x^2+y^3+z^4)^12*(1-x^2+y-z)^11
It is not.
++++++++++++++++++++++++++++
++++ Performance +++
++++++++++++++++++++++++++++
+ ./t-pika "tan(x)/cos(x)^1034" -otcollect
==> Very, very long computation. GCD too big.
+ ./t-pika "tan(2+x)" -oseries x 100
==> 2s whereas it is instantenous with taylor
./t-pika "sin(cos(1+x)" -oseries x 100
More generaraly series is not efficient at all
+ may_expand can be improved on some sparse input like
==> (1+3*x+2*x^2)^1000
+ may_eval_sum / may_eval_product:
==> partial sums can be merged.
+ may_replace (P(x), x, NUM)
If P is a polynomial and NUM a numerical,
we can optimize by caching some values of NUM^d in the evaluation of the expression for d <= deg(P)
Use dedicative function?
+ may_div_qr univarie:
See how to do an integer evaluation followed by by a heuristic lift.
Or a newton evaluation?
+ may_expand_var/may_collect: shall not develop the expression if possible.
If not dependend on x, return x.
If it is a sum, collect each element of the sum then regroup the same degrees.
If it is a product, collect each element and extract the element indepedent of x. Then?
+ may_gcd:
* Handle case gcd(P^N,Q) without expanding P^N
gcd (P^n, Q^m) =
. g = 1
. g' = gcd(P,Q)
. while g' != 1
if n < m :
g = g * g' ^n
P = P/g'
Q = g'
m = m - n
else if n > m
g = g * g' ^ m
Q = Q/g'
P = g'
n = n - m
else
g = g * g' ^ n
break loop
g' = gcd (P, Q)
. return g
* Hack: substitute a local variabl if it exists an integer N such as y only exists as a power of N in the expression.
* Hack: perform all multiplication and power hack before doing the expand.
* Subresultant PRS :
- Sort the list from the lower degree to the higher one?
* Heuristic GCD:
- Put a limit from which we no longer calculate the heuristic GD.
- Take into account all the arguments to avoid having to convert / deconvert everytime.
- Allows to take into account the minimum of the maximum of all the entries.
- A pass to convert / deconvert all variables?
- The deconvertion must not make the double division whole to recover the mod and the quotient.
- See if we can not evaluate lower quits to fail more often, and continue if successful (who will have the advantage
to reduce the degrees).
+++++++++++++++++++++++
++++ Errors +++
+++++++++++++++++++++++
+++++++++++++++++++++++
++++ Others +++
+++++++++++++++++++++++
+ Add a cache (Hash-Table) : how to handle the coherency problems?
+ Visibility attribute (http://gcc.gnu.org/wiki/Visibility)
+ Port to M*LIB
==> Better performance,
==> Less bugs.
++++++++++++++++++++
++++ Doc +++
++++++++++++++++++++
Alignement restriction?
Rewrite documentation for may_hold.