random polynomial generation
Steffen
I need to create a random multivariate polynomial. I do it as follows:
F = GF(10007)['x,y'].random_element(4,9)
Now, sage creates a polynomial in x and y of degree 2 in every
variable, since 4 = 2+2. Furthermore 9 restricts the polynomial to 9
coefficients. I could not find any documentation for
"random_element(..,..)" but thats my guess after tinkering around with
the values. So far everything is perfect.
The problem is now, that most of the time the created polynomial has
only 6 or 7 coefficients. Since the probability to choose 0 in the
field GF(bigPrime) is quite low, I would expect the polynomial to have
9 coefficients in most cases. If I increase this second parameter of
the random_element function, the average number of coefficients
increases up to the maximum possible number of coefficients, which is
9. Unfortunately, the computation time for creating the polynomial
increases nearly linearly with the second parameter of the
"random_element" function.
So I am wondering if my understanding of the parameters of
"random_elment" is wrong or if this function really produces such
results, which I do not regard as random behaviour.
Cheers, Steffen
Justin C. Walker
On Oct 15, 2007, at 4:47 PM, Steffen wrote:
>
> Hi,
>
> I need to create a random multivariate polynomial. I do it as follows:
>
> F = GF(10007)['x,y'].random_element(4,9)
>
> Now, sage creates a polynomial in x and y of degree 2 in every
> variable, since 4 = 2+2. Furthermore 9 restricts the polynomial to 9
> coefficients. I could not find any documentation for
> "random_element(..,..)" but thats my guess after tinkering around with
> the values. So far everything is perfect.
For the record, you can find out about this kind of thing in SAGE
using the "?" and "??" operators:
sage: PF9.<a,b>=GF(9,'z')['a,b']
sage: PF9.random_element?
Return a random polynomial in this polynomial ring.
INPUT:
degree -- maximum total degree of resulting polynomial
terms -- maximum number of terms to generate
OUTPUT: a random polynomial of total degree degree
and with term terms in it.
...
"??" will give you this together with the corresponding code.
There are some glitches in the system, but it works pretty well.
> The problem is now, that most of the time the created polynomial has
> only 6 or 7 coefficients. Since the probability to choose 0 in the
> field GF(bigPrime) is quite low, I would expect the polynomial to have
> 9 coefficients in most cases. If I increase this second parameter of
> the random_element function, the average number of coefficients
> increases up to the maximum possible number of coefficients, which is
> 9. Unfortunately, the computation time for creating the polynomial
> increases nearly linearly with the second parameter of the
> "random_element" function.
> So I am wondering if my understanding of the parameters of
> "random_elment" is wrong or if this function really produces such
> results, which I do not regard as random behaviour.
Check out the code, and ask if this doesn't answer your questions.
HTH
Justin
--
Justin C. Walker, Curmudgeon-At-Large
Institute for the Absorption of Federal Funds
--------
Men are from Earth.
Women are from Earth.
Deal with it.
--------
didier deshommes
>
> Hi,
>
> I need to create a random multivariate polynomial. I do it as follows:
>
> F = GF(10007)['x,y'].random_element(4,9)
Hi Stephen,
This is not an "exact" function. The only guarantee we have is that we
will get a polynomial with total degree of *at most* 4 and total
number of terms is *at most* 9.
You're right, in such a big field the coefficient is almost always
nonzero. The problem is in the degrees: we don't check for repetitions
when generating them (we don't care). As you know, we often view
multivariate polynomials as dictionaries with the degrees as keys and
the coefficients as values. The functions works simply (with
parameters 4 and 9):
1) generate 9 random tuples of for the degrees. The only requirement
we have is that the sum of the element in these tuples must not exceed
4. Repetitions are allowed.
2) Generate 9 coefficients.
3) Create a dictionary where the keys are the degree tuples and the
values are the coefficients. Repetitions are discarded and that is how
we end up with a polynomial with less than 9 terms.
4) Create a polynomial from this dictionary and return it.
Hope that helps.
didier
Nick Alexander
>
> There are some glitches in the system, but it works pretty well.
Glitches that I would love to hear about, and hopefully fix.
Nick
Steffen
> Hi Stephen,
> This is not an "exact" function. The only guarantee we have is that we
> will get a polynomial with total degree of *at most* 4 and total
> number of terms is *at most* 9.
>
> You're right, in such a big field the coefficient is almost always
> nonzero. The problem is in the degrees: we don't check for repetitions
> when generating them (we don't care). As you know, we often view
> multivariate polynomials as dictionaries with the degrees as keys and
> the coefficients as values. The functions works simply (with
> parameters 4 and 9):
> 1) generate 9 random tuples of for the degrees. The only requirement
> we have is that the sum of the element in these tuples must not exceed
> 4. Repetitions are allowed.
> 2) Generate 9 coefficients.
> 3) Create a dictionary where the keys are the degree tuples and the
> values are the coefficients. Repetitions are discarded and that is how
> we end up with a polynomial with less than 9 terms.
> 4) Create a polynomial from this dictionary and return it.
Hi didier,
the implementation does not return a polynomial of a total degree of
at most 4, but a polynomial of total degree of at most 4/2 = 2 in x
and in y. If I change the total degree to 5, nothing happens, since
5/2 = 2. This might be a bug in the implementation. However I am happy
with this behaviour and maybe there should be the option for choosing
the total degree or the degree in every variable.
Furthermore I am not happy with this implementation in general. In
step 1.) you do not care about repetitions. This sounds reasonible
since repetitions are part of randomness. Later in step 3) you do care
about repetetions and summarise them under the value 0. If the value 0
gains the same importance as all other values in the corresponding set
of values, than the multiple occurance of 0 is a repetition, too.
I am quite new in SAGE and have no idea how sage code looks like, but
I will have a look and see if I can do some changes :-)
Cheers, Steffen
didier deshommes
> Hi didier,
>
> the implementation does not return a polynomial of a total degree of
> at most 4, but a polynomial of total degree of at most 4/2 = 2 in x
> and in y. If I change the total degree to 5, nothing happens, since
> 5/2 = 2. This might be a bug in the implementation. However I am happy
> with this behaviour and maybe there should be the option for choosing
> the total degree or the degree in every variable.
For total degree, I'm using the definition here:
http://planetmath.org/encyclopedia/OrderAndDegreeOfPolynomial.html
So I am not concerned about individual degrees at all.
> Furthermore I am not happy with this implementation in general. In
> step 1.) you do not care about repetitions. This sounds reasonible
> since repetitions are part of randomness. Later in step 3) you do care
> about repetetions and summarise them under the value 0. If the value 0
I don't explicitly discard repetitions in 3), the dictionary object
takes care of that by discarding repeated keys (in this case, the keys
are the degree tuples).
didier
cwitty
> 2007/10/16, Steffen <sre...@gmx.de>:
>
> > Hi didier,
>
> > the implementation does not return a polynomial of a total degree of
> > at most 4, but a polynomial of total degree of at most 4/2 = 2 in x
> > and in y. If I change the total degree to 5, nothing happens, since
> > 5/2 = 2. This might be a bug in the implementation. However I am happy
> > with this behaviour and maybe there should be the option for choosing
> > the total degree or the degree in every variable.
>
> For total degree, I'm using the definition here:http://planetmath.org/encyclopedia/OrderAndDegreeOfPolynomial.html
>
> So I am not concerned about individual degrees at all.
Given this definition (which I agree is correct), I would expect that
if I ask for a total degree of 4, I would sometimes see monomials like
x^4 or x*y^3. I think the lack of these monomials is what surprises
(and, coincidentally, pleases) Steffen.
Carl
Steffen
Exactly, thats one of two points. The maximum degree in every variable
is (maximum total degree of resulting polynomial) / (number of
varialbes of the polynomial). Thus for example GF(10007)
['x,y,z'].random_element(5,9) will be limited in every variable to
degree 5/3 = 1 !!!. This is not what the upper definition says.
The second point is about the number of coefficients that are set to
0. This might a point to argue about, but if I create a random
polynomial with a (maximum number of terms to generate) then I expect
that the 0 occurs with the same probability and thus as often as every
other element. Thats why I am not happy if 20% or more of the
parameters are 0.
Steffen
William Stein
> > Given this definition (which I agree is correct), I would expect that
> > if I ask for a total degree of 4, I would sometimes see monomials like
> > x^4 or x*y^3. I think the lack of these monomials is what surprises
> > (and, coincidentally, pleases) Steffen.
> >
> > Carl
>
> Exactly, thats one of two points. The maximum degree in every variable
> is (maximum total degree of resulting polynomial) / (number of
> varialbes of the polynomial). Thus for example GF(10007)
> ['x,y,z'].random_element(5,9) will be limited in every variable to
> degree 5/3 = 1 !!!. This is not what the upper definition says.
> The second point is about the number of coefficients that are set to
> 0. This might a point to argue about, but if I create a random
> polynomial with a (maximum number of terms to generate) then I expect
> that the 0 occurs with the same probability and thus as often as every
> other element. Thats why I am not happy if 20% or more of the
> parameters are 0.
>
It sounds to me like you should implement a variant of random_element
for polynomial rings that you like, and post a patch. You could:
(1) fix the docstring to be correct,
(2) make your variant available via an option, e.g.,
random_element(something='blah')
-- William
didier deshommes
> Exactly, thats one of two points. The maximum degree in every variable
> is (maximum total degree of resulting polynomial) / (number of
> varialbes of the polynomial). Thus for example GF(10007)
> ['x,y,z'].random_element(5,9) will be limited in every variable to
> degree 5/3 = 1 !!!. This is not what the upper definition says.
> The second point is about the number of coefficients that are set to
> 0. This might a point to argue about, but if I create a random
> polynomial with a (maximum number of terms to generate) then I expect
> that the 0 occurs with the same probability and thus as often as every
> other element. Thats why I am not happy if 20% or more of the
> parameters are 0.
I filed out a bug report about those 2 issues:
1) Degrees can severely restricted.
2) The polynomials returned can be too sparse
I plan to post a patch addressing your concerns (I can especially see
how 1) can be annoying). Random poly generation will most likely be
slower, so for now I'm planning to keep the current behavior around,
even if it is not the default.
didier
Steffen
Thanks, I will wait for didiers patch. If I then have any additional
requirements I will implement them via an optional flag or smth
similar.
Steffen
didier deshommes
http://sagetrac.org/sage_trac/ticket/980 . The individual degree
distribution is a little better:
{{{
sage: GF(10007)['x,y,q'].random_element(6,10)
-2005*x^6 + 2400*x^4*y^2 - 3609*x^3*y^3 + 488*x*y^5 - 3093*x^4*y*q +
3482*x*y*q^3 - 989*x^2*y*q - 3529*x*q^3 - 3957*x
}}}
But note that most of the time for the example at the beginning of the
thread, we still get 6,7 out of 9 terms most of the time. I still
don't think this is a bug: we are not creating a polynomial with 9
terms in it, but picking one with at most 9 terms.
{{{
sage: GF(10007)['x,y'].random_element(4,9)
797*x^4 - 439*x^2*y^2 - 1457*x*y^3 - 2348*y^4 - 1721*x^3 - 1885*x^2*y
- 1760*x*y^2 + 310*y
}}}
didier
2007/10/24, Steffen <sre...@gmx.de>:
Martin Albrecht
after realizing that Steffen and I share an office at RHUL I discussed this
thing with him today for some time.
The improved implementation (#980) still doesn't produce random polynomials
for two reasons: The code does not seem to produce monomials of degree up to
$d$ uniformly at random.
deg = degree
for i in range(n):
exp = ZZ.random_element(0,deg+1)
if exp <= deg:
exps.append(exp)
deg -= exp
else:
exps.append(0)
E.g. in this implementation the probability that a (0,0,0....,0,0,0,0)
exponent tuple is produced is (1/(d+1))^n because we have to hit 0 out of d+1
possibilities n times.
However, if we write down a list M of all possible monomials of degree <= d
this L has length
#M = \sum_{i=0}^d ( binomial(n + i -1, i ) )
and the probability to hit the constant monomial is (1/#M). Plugging in some
numbers: n = 10, d = 2
implemented: (1 / 3)^10
uniformly at random: 1 / ( 1 + 10 + 55)
To fix this we need to consider choosing monomials of a degree D at random
which can be done by finding a bijection between the integers up to some N =
binomial( n + d -1 , d ) and the set of compositions. Mike (mhansen)
provided this code to do it:
def random_monomial(n, degree):
total = binomial(n+degree-1,degree)
random_index = randint(0, total)
comb = choose_nk.from_rank(random_index, n+degree-1, n-1)
monomial = [ comb[0] ]
monomial += map(lambda i: comb[i+1]-comb[i]-1, range(n-2))
monomial.append( n+degree-1-comb[-1]-1 )
and this explanation:
http://www.cse.ucsd.edu/classes/sp07/cse21/Ron_Notes/starbin.pdf
Side note: This code does not correctly for me as it can run into an infinite
loop which probably can be tracked down to _comb_largest with a parameter 'w'
< 0.
This construction is random if the random number generator ("randint") is
random. Btw. how random is randint?
Now we need to choose a degree d at random. We cannot do this uniformly at
random because the classes (associated to the degree) are not of the same
size (e.g., 1, 10, 55 above) We don't want to choose classes uniformly but
elements and again mhansen beat me to an implementation:
def random_monomial_less_than_degree(n, degree):
#Get the counts of the total number of monomials
#of degree d
counts = [1] #degree 0
for d in range(1, degree):
counts.append(binomial(n+d-1, d))
total = sum(counts)
#Select a random one
random_index = randint(0, total-1)
#Figure out which degree it corresponds to
d = 0
while random_index >= counts[d]:
random_index -= counts[d]
d += 1
#Generate the corresponding monomial
comb = choose_nk.from_rank(random_index, n+d-1, n-1)
monomial = [ comb[0] ]
monomial += map(lambda i: comb[i+1]-comb[i]-1, range(n-2))
monomial.append( n+d-1-comb[-1]-1 )
return monomial
However, an implementation without the need to explicitly construct the counts
array would be good.
With this in place one can start thinking about constructing random
polynomials from random monomials. For this we don't have an elegant solution
yet. We (=Steffen and me) distinguish two cases:
Let #T be the number of terms requested.
If $MM is the number of all possible monomials of all allowed degree <= d and
#T < $MM/2 then we generate #T _distinct_ monomials as above and assign
random coefficients (possibly zero). The overhead of requesting distinct
monomials should be at most 2 because if we are looking for 1/2 of the search
space, every second choice should be a double.
If #T > $MM/2 we generate all possible monomials, pick #T and assign
coefficients. This should be more effective for this case because we don't
generate any doubles (but memory is more precious than cpu cycles, so we
might have to move that barrier up a bit).
Does this sound like a sensible approach?
Martin
--
name: Martin Albrecht
_pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99
_www: http://www.informatik.uni-bremen.de/~malb
_jab: martinr...@jabber.ccc.de
Robert Bradshaw
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).
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.
- Robert
Martin Albrecht
> 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.
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.
> 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.
didier deshommes
> This construction is random if the random number generator ("randint") is
> random. Btw. how random is randint?
The core generator for all random functions in Python uses the
mersenne twister which is pretty strong.
I have another suggestion for this problem, that looks somewhat like
yours. Maple has 2 functions in its combinatorics package that :
inttovec(number,nvars) which turns a number into vector of length
nvars, and vectotint(vec) that does the opposite. Here's the
documentation for them:
"""
These two functions provide a one-to-one correspondence between the
non-negative integers and all vectors composed of n non-negative
integers.
The one-to-one correspondence is defined as follows. View all vectors
of n non-negative integers as exponent vectors on n variables.
Therefore, for each vector, there is a corresponding monomial.
Collect all such monomials and order them by increasing total
degree. Resolve ties by ordering monomials of the same degree in
lexicographic order. This gives a canonical ordering.
"""
Ex:
> inttovec(9,2);
[0, 3]
> vectoint([0,3]);
9
Now the idea is simple: for random_elements(deg,terms) , generate the
a number randomly in (0, nchoosek(n+d-1,d)) and compute the
corresponding monomial:
for t in terms:
num = randint(0, nchoosek(n+d-1,d))
term = inttovec(num,nvars)
Since integers are chosen uniformly, this would guarantee (?) that the
polynomial is generated uniformly. Only hitch is that I don't know if
there is such inttovec is in in SAGE yet. mhansen, any idea?
didier
Mike Hansen
> polynomial is generated uniformly. Only hitch is that I don't know if
> there is such inttovec is in in SAGE yet. mhansen, any idea?
Yes, this is pretty much what I'm doing. While I don't have those
exact functions, they would be easy to implement.
How fast do these need to be? Here's a rough function that uniformly
selects monomials without replacement from all possible monomials with
degree less than d.
def random_monomials(n, degree, terms):
#Get the counts of the total number of monomials
#of degree d
counts = [1] #degree 0
for d in range(1, degree):
counts.append(binomial(n+d-1, d))
total = sum(counts)
#Select a random indices
indices = sample(xrange(total), terms)
monomials = []
for random_index in indices:
#Figure out which degree it corresponds to
d = 0
while random_index >= counts[d]:
random_index -= counts[d]
d += 1
#Generate the corresponding monomial
comb = choose_nk.from_rank(random_index, n+d-1, n-1)
monomial = [ comb[0] ]
monomial += map(lambda i: comb[i+1]-comb[i]-1, range(n-2))
monomial.append( n+d-1-comb[-1]-1 )
monomials.append(monomial)
return monomials
Here's an example:
sage: time random_monomials(20, 40, 20)
CPU times: user 0.09 s, sys: 0.00 s, total: 0.09 s
Wall time: 0.09
[[8, 1, 5, 0, 0, 1, 2, 0, 1, 1, 2, 0, 0, 2, 4, 2, 1, 4, 3, 1],
[0, 0, 9, 2, 0, 7, 2, 0, 3, 2, 1, 0, 3, 1, 0, 1, 4, 0, 4, 0],
[0, 0, 3, 0, 1, 4, 3, 1, 0, 2, 1, 3, 4, 1, 1, 0, 6, 7, 0, 0],
[0, 2, 3, 0, 0, 2, 1, 2, 5, 3, 0, 0, 1, 5, 2, 0, 1, 1, 9, 0],
[0, 1, 1, 7, 0, 1, 6, 0, 1, 0, 1, 0, 1, 6, 2, 0, 7, 0, 2, 1],
[7, 0, 3, 1, 0, 6, 1, 4, 0, 8, 0, 0, 0, 0, 0, 1, 3, 3, 0, 0],
[0, 0, 0, 4, 1, 5, 3, 1, 1, 0, 0, 2, 3, 3, 3, 1, 4, 0, 1, 6],
[1, 2, 5, 0, 5, 1, 1, 0, 0, 7, 0, 1, 1, 1, 1, 2, 3, 4, 1, 0],
[1, 7, 0, 0, 4, 3, 0, 2, 0, 0, 1, 8, 1, 1, 0, 0, 2, 5, 0, 0],
[0, 4, 0, 3, 5, 0, 0, 0, 1, 0, 1, 3, 2, 1, 8, 4, 0, 0, 1, 0],
[1, 0, 9, 0, 1, 7, 3, 1, 2, 0, 0, 1, 0, 0, 5, 1, 0, 6, 0, 0],
[1, 3, 0, 3, 5, 0, 1, 2, 0, 2, 4, 1, 0, 4, 1, 2, 3, 1, 4, 0],
[0, 2, 3, 8, 1, 0, 3, 1, 0, 1, 1, 1, 0, 1, 5, 5, 1, 5, 0, 0],
[3, 0, 4, 0, 8, 0, 3, 1, 0, 2, 0, 1, 0, 3, 1, 6, 2, 2, 0, 1],
[2, 5, 1, 0, 1, 0, 2, 5, 1, 2, 3, 3, 0, 0, 0, 4, 4, 0, 0, 0],
[1, 0, 6, 2, 5, 0, 0, 0, 1, 4, 2, 0, 5, 0, 1, 1, 0, 0, 3, 4],
[1, 1, 0, 2, 0, 1, 1, 1, 3, 3, 2, 2, 1, 0, 0, 1, 1, 1, 11, 7],
[7, 0, 3, 0, 4, 1, 2, 1, 6, 0, 0, 1, 3, 1, 0, 0, 7, 3, 0, 0],
[1, 2, 3, 1, 0, 1, 0, 0, 3, 3, 2, 0, 5, 0, 0, 0, 3, 1, 2, 7],
[0, 5, 0, 3, 1, 1, 2, 0, 1, 1, 0, 1, 4, 2, 8, 2, 2, 1, 0, 2]]
--Mike
Robert Bradshaw
> 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.
- Robert
didier deshommes
>
> > Since integers are chosen uniformly, this would guarantee (?) that the
> > polynomial is generated uniformly. Only hitch is that I don't know if
> > there is such inttovec is in in SAGE yet. mhansen, any idea?
>
> Yes, this is pretty much what I'm doing. While I don't have those
> exact functions, they would be easy to implement.
>
> How fast do these need to be? Here's a rough function that uniformly
> selects monomials without replacement from all possible monomials with
> degree less than d.
Is this function in sage? Where is it located?
didier
Mike Hansen
Which function?
--Mike
didier deshommes
>
> > Is this function in sage? Where is it located?
>
> Which function?
Sorry, the random_monomials() function.
>
> --Mike
>
> >
>
Mike Hansen
--Mike
Steffen
On 26 Okt., 00:48, Robert Bradshaw <rober...@math.washington.edu>
wrote:
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
didier deshommes
> 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
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
Mike Hansen
> random_monomials(n,degree,terms) failed each time for degree =1 (but
> was fine for degree=0).
Yeah, I knew that when I wrote it -- it was just something quick that
I wrote up. The degree 1 case is trivial to handle though.
--Mike
Steffen
On 26 Okt., 18:30, "didier deshommes" <dfdes...@gmail.com> wrote:
> 2007/10/26, Steffen <sre...@gmx.de>:
>
>
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.
Martin Albrecht
I've attached a 'random_monomial.py' to
http://trac.sagemath.org/sage_trac/ticket/980
which implements Steffen's and my proposal.
Thoughts?
didier deshommes
>
> Hi everybody,
>
> I've attached a 'random_monomial.py' to
>
> http://trac.sagemath.org/sage_trac/ticket/980
>
> which implements Steffen's and my proposal.
Hey guys,
I've attached a patch for this at
http://trac.sagemath.org/sage_trac/ticket/980 . Let me know if it
works for you.
didier