On 26 Okt., 18:30, "didier deshommes" <[EMAIL PROTECTED]> wrote:
> 2007/10/26, Steffen <[EMAIL PROTECTED]>:
>
>
Ok, here an example. Lets take a polynomial over
F:=GF(nextprime(2**42)) in two variables x and y and a maximum total
degree of 3.
>
> > 1) Polynomial with max number of monomial. We dont need to worry about
> > that case, since here all the monomial are chosen, that means actually
> > there is nothing to choose. So this will be efficient anyway.
In the first case we iterate over all monomials and assign them
independently a random value \in F. Due to the size of F all
coefficients ai (by coefficient I mean the element in front of an
monomial, Martin doesn't like it ;-)) will be !=0 and we get a
polynomial such as:
a0 + a1x + a2y + a3xx + a4xy + a5yy + a6xxx + a7xxy + a8xyy + a9yyy
> > 2) A user wants an exact < totalmax number of monomials. In this case
> > its difficult to reach real randomness in an efficient way. Martins
> > and my proposal in this case was to except collisions during the
> > implementation, that is choose a random monomial and throw it away if
> > already chosen. This is not most efficient, the expectation
> > calculation period has 2 * the optimal time as upper bound.
In this case the user may choose the maximum number of monomials to be
5. In this case the polynomial will look like:
a) a0 + a3xx + a6xxx + a7xxy + a8xyy or
b) a3xx + a4xy + a6xxx + a8xyy + a9yyy
That means, that EXACTLY 5 of the coefficients get a random value \in
F and the rest is set to 0. Note, that every of these 5 coefficients
can also get the value 0 with probability 1/(size(F)), yielding a
polynomial with less then 5 monomial with very small probability.
The according exact 5 monomials that receive a random coefficient \in
F can be chosen by Martin's scheme above. This scheme produces up to
50% collisions during the choice of the monomials, but we had no
better idea so far :-) The idea of the scheme is as follows:
If you want to have less or equal than half of the maximum number of
monomials then do:
As long as you dont have enough monomials choose a next one. If you
chose a monomial, that you have chosen before, ignore it and proceed.
else if you want to have more than the half of maximum possible
monomials:
Choose all.
As long as you have too much:
Choose a random monomial. If this is still in the list, remove
it.
> > 3) A user wants a real random polynom with a certain number of
> > monomials, but there is no need to fix a maximum number of monomials.
> > An efficient implementation here would be:
> > #m = maxNumberOfMonomials = "calculate it"
> > #d = desiredNumberOfMonomials = "choose it"
> > Iterate over the list of all monomials, with probability #d/#m choose
> > this monomial.
> > This would be faster than 2) and would return a polynomial with an
> > expectation value of monomials of #d
Now in the third case the user want a polynomial with approximately 5
monomials:
a) a0 + a3xx + a6xxx + a7xxy + a8xyy or
b) a3xx + a4xy + a5yy + a6xxx + a8xyy + a9yyy or
c) a0 + a3xx + a6xxx + a7xxy
An easy and efficient way to determine a polynomial with approximately
5 out of 10 monomials is to iterate over the number of all monomial
and asign the corresponding coefficient a random value with
probability 5/10 and no value or 0 with probability 1 - 5/10. Indeed
the number of chosen monomials will be distributed according to the
"binomial distribution", which looks a bit like the normal
distribution. Thus in the upper example the polynomial would have 5
monomials with the highest probabiltity, 4 or 6 with the same but
smaller probability and so on.
However, this might a sufficient behaviour for the user in many cases
and is fast and easy to implement :-)
>
> Could you give an example for each of these cases? I'm having trouble
> distinguishing the difference between 2) and 3)
>
> Mike, your code had a subtle bug, where
> random_monomials(n,degree,terms) failed each time for degree =1 (but
> was fine for degree=0).
>
> didier
Although we are making a big thing out of this stupid random
generation, I think its important to
1) receive a random foo if the function name is random_foo
2) avoid collisions during the implementation, since this increases in
most cases unnecessarily the calculation period and might cause
unexpected cases in which the collisions dominate the calculation cost.
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/
-~----------~----~----~----~------~----~------~--~---
