On 26 Okt., 00:48, Robert Bradshaw <[EMAIL PROTECTED]>
wrote:
> On Oct 25, 2007, at 4:23 PM, Martin Albrecht wrote:
>
> > On Friday 26 October 2007, Robert Bradshaw wrote:
> >> This is an interesting construction, but I am wondering if a uniform
> >> distribution for all polynomials of specified degree < d, with a
> >> specified number of terms, is the most natural one to give, and how
> >> grave the impact is on efficiency. (Depending on the coefficient
> >> ring, this goal may not even be achievable).
>
> > Yes, a random boolean multivariate polynomial will have $MM/2
> > monomials i.e.
> > 1/2 of all possible monomials. That is okay, we are not enforcing
> > #T to be
> > achieved but we are enforcing that the coefficients determine if we
> > get to #T
> > or not rather than the implementation.
>
> For boolean multivariate polynomials, it makes sense to talk about
> the number of terms of a random polynomial of a given degree, because
> you are working with a finite space, but this has a very different
> feel than a random polynomial over an infinite ring, say, Z.
>
> > Actually, Steffen jokingly proposed earlier to have .some_element()
> > besides .random_element() which gives you a somewhat random element
> > whereas .random_element() actually gives you something very random.
>
> The random_element() function should probably take arguments
> specifying the distribution--some_element makes it sound like it's
> always going to give the same thing.
>
> >> Also, rather than specifying maximum degree/number of terms, it might
> >> make more sense (and be much after to implement) to use a
> >> distribution with an expected degree and/or number of terms.
>
> > can you elaborate on this, I don't really understand that point.
>
> My point is that just because one isn't using a uniform distribution
> doesn't mean that the polynomials produced are any less random. For
> instance, fix a degree d and a (real) distribution X with support
> [0,infinity) and expected value 1. Now let r_1, ..., r_n be chosen
> out of X and let
>
> f = sum x_i ^ round(d/n * r_i)
>
> Now f is a monomial with expected (i.e. average) degree d (I think--
> not sure how bad the discontinuous rounding would mess things up),
> though it may have degree more or less than d, and though it is not
> uniformly chosen from any set is not any less "random." It can also
> be computed very quickly.
Yes, I totally agree with Robert in this point and had the discussion
with Martin before. The user might be interested in the following 3
things:
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.
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.
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
Steffen
>
> - Robert
--~--~---------~--~----~------------~-------~--~----~
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/
-~----------~----~----~----~------~----~------~--~---
