|
From: David B. <bo...@wa...> - 2007-12-12 15:59:16
|
Hi Alberto, Gustavo, ... and all the list !
I continue to work on my new branch. I want to tell you my changes and
have your feedback.
There are 4 points, the last is surely the more important.
1. The tree.
The NxpElementTree is no more a binary tree, now. Its structure looks
like the function's one. So, the sum 2+x+y+2z is not a big tree of
trees but just one tree. All the arguments are stored in a list.
We can now do three things with trees :
* simplify them : the simplification is not total. The goal is to
simplify trivial things like a+0, a^1, x+3x, etc... Don't expect the
simplify function to expand an expression. This way, NumExp works
faster. The simplification works now like the derivation, we have a
hash table, keys are operators and values are the correspondant
functions. In fact, it works with +, -, /, * and ^...
The code needs cleaning, but works.
* expand them : if you want to expand (a+b)^2, you just have to enter
expand[(a+b)^2], the function transforms the tree (a+b)^2 in a sparse
multivariate polynomial, then this last one is converted back to a tree
which is the result. The interest to work with the polynomial is that
computations are really faster than if we work directly with
NxpElements. You can expect to expand (a+b+c+2)^200.
* factorize them : At the moment, only univariate polynomials can be
factorized. This will change when all that I expose here will work. The
tree entered in the function is transformed to an univariate
polynomial. We factorize it and then we transform it back to a tree.
2. New directory algebra.
Polynomials are now in the kernel/algebra directory. They are not
NxpElement. They work more like mpfr/gmp numbers. At the beginning
their coefficients were just integers, but that didn't really work. So
I changed that for multivariate polynomials. But I didn't want to work
with NxpElement for numbers. So I created a wrapper to gmp/mpfr numbers.
So we have a NxpNb structure that works correctly even if it needs some
work again.
Univariate polynomials work always only with integers just because I
didn't need them with other coefficients. But this could change later.
3. Numbers.
Now that I have NxpNb structure, I changed all the different types
NxpElementInt, NxpElementFrac, NxpElementReal into one.
struct _NxpElementR {
NxpElementNumber parent;
NxpNb *value;
};
We always have nxp_element_int_new, nxp_element_frac_new, etc..., but
they creates a new nxp_element_r element.
It's possible that I change NxpElementComplex into
struct _NxpElementComplex {
NxpElementNumber parent;
NxpNb *re;
NxpNb *im;
}
Then calculus in the complex.c file would be easier to read. But I'm
not sure.
4. Functions.
Maybe this is the biggest change.
I wanted to have the possibility to define a function like this in
NumExp :
gcd(a:POLYNOMIAL, b:POLYNOMIAL, x:VARIABLE):=[
BLABLA
]
But I needed to be able to test the type of each argument.
So, I decided to change the prototype management.
This is what we entered before to define a builtin function:
nxp_bifunc_define_global("igcd", &nxp_prototype__INT_INT, &eval,
&derive, &simp);
This needed that nxp_prototype__INT_INT already exists.
So now, we enter :
nxp_bifunc_define_global("igcd[INT,INT]", &eval, &derive, &simp);
A new function nxp_proto_get_proto_full(name, &new_name); is called in
nxp_bifunc_define_global that returns what I call a NxpProto :
struct _NxpProto {
int arity;
GSList *eval_proto;
GSList *derive_proto;
GSList *simp_proto;
};
If the proto doesn't exist, it is created and otherwise, the already
existing proto is returned.
When we evaluate igcd(4, 6)
All the function with the name igcd are taken.
Then, for each, we compare the arguments' types needed
with the ones given.
This comparison is done like this :
The function gives a NxpProto.
The list of eval_proto in this NxpProto is a list of functions, the
first one tests the type of the first argument, the second one tests
the type of the second argument...
With igcd, the first function tests if 4 is an integer, then if 6 is
an integer too.
A test function does something like this :
if the given element x is of type INT, return REF(x)
else y= eval(x) and if x is of type INT return y
else unref(y)
return NULL
So a NULL returned value tells that the argument is bad, else we have a
pointer to the good value.
If we create a new module which contains new
elements, we can add a test function for those new elements easily :
nxp_proto_add_tester("PERMUTATION", eval, simp);
eval tests the argument if we evaluate the function, and simp tests the
argument if we simplify the function.
When, we have found the good function to execute, the arguments are
also in the good form in a list {4, 6}.
Then, the eval function asks for the C function corresponding to igcd.
The arguments cannot be given like before, so we cannot execute the
following function :
nxp_bifunc_igcd(NxpElement *a, NxpElement *b, ETC);
but we can execute this one :
nxp_bifunc_igcd(NxpElementList *args, ETC);
where args is the list {4, 6} in our example.
So, what do we win ?
PRO
- The structure is dynamical, even with user-functions, we will be able
to test types of arguments.
- The code is smaller, before we had a function to test INT_INT
that was two times the same test, and we also had INT_INT_INT, etc...
Each prototypes had to be know in advance.
- We can ask for type that are not NxpElement types. For example, if we
want to create functions that work only with prime numbers, we can
imagine a test function for PRIME and then we can create a new function
with primes.
CONS
- When we have nxp_bifunc_igcd(NxpElementInt *a, NxpElementInt *b, ETC),
we know that this function needs two arguments that are integers. With
nxp_bifunc_igcd(NxpElementList *args, ETC); it's not in the name of the
function, but we can tell this in the commentary introducing the
function.
- I don't see others.
All this is in my branch. Things about factorization of expressions
don't work for now because of those so many changes.
I also know my code must be reorganised and cleaned a little, but ideas
are there...
So now, you can criticize all this, don't be too angry !! ;-)
Cheers.
David.
|