Ralf Hemmecke wrote:
>
> On 10/04/2015 02:21 PM, Waldek Hebisch wrote:
> > I think we should have a new category, like:
>
> > )abbrev category RCHOICE RandomChoice
>
> Well, yes, why not.
>
> > RandomChoice : Category == with
> > random_element : Integer -> Union(%, "failed")
>
> I would also prefer randomElement as the name.
>
> > ++ random_element(n) generates random element
> > ++ with values in some set having of order \spad{n}
> ^^^^^^^^^^^^^^^^^^^^^^^^
> That is something I don't understand.
>
> If I had to implement that category for SparseUnivariatePolynomial(R)
> what exactly should I implement then? "order n" is not a well defined
> concept. I would understand randomElement(n) chooses from a pool of n
> elements. The question then only is: what is the pool?
>
> > ++ elements and with probability distribution that is
> > ++ roughly uniform on this set. Returns failed if
> > ++ \spad{%} has less than \spad{n} elements.
>
> Also that is somewhat too vague. I suppose n means the number of
> elements in a set from the underlying domain %. Suppose % is Integer and
> n = 100 and I implement the set as S=[2^1, 2^2, 2^3, ..., 2^100].
> I can uniformly choose from S (just as I can uniformly choose an
> exponent e in the range 1..100 and return 2^e), but I wouldn't call this
> a good implementation, because if favours powers of 2 which are not
> really random choises of integers.
>
> > The idea is that unlike say simulations we do not need perfectly
> > uniform distribution (and given that support of distribution
> > is unspecified claim of exact uniformity would have little
> > meaning), which may simplify implementation. Also, we can
> > not magically enlarge finite domains, so if users requent
> > choice from more elements than available the only possibility
> > is to fail.
>
> > AFAICS this condition will propagate resonably well trough
> > type towers. In particular we can give generic definition for
> > all finite domains and easily propagate it from infinite
> > domains to bigger infinite domains.
> >
> > Natural name for operation would be 'random', but it may
> > conflict with existing 'random(n)' in some domains. ATM
> > I do not see if such conflict leads to troubles or is just
> > harmless, so I opted for different name.
> >
> > Comments?
>
> We have random(n) to return a random integer in the range 0..(n-1).
>
> Maybe it is not the best idea, because not all domains can be ordered
> linearly, but what about "randomElement: (%, %) -> Union(%, failed)" in
> the sense that randomElement(a, b) returns a random element in the range
> from a to b. For example, if % is SparseUnivariatePolynomial(Integer)
> and we ask for
>
> randomElement(x^2+4*x+10, x^3+5*x^2+13*x+20)
>
> it would return a polynomial like this
>
> randomElement(0,1)*x^3+
> randomElement(1,5)*x^2+
> randomElement(4,13)*x+
> randomElement(10,20)
>
> That's just an ad hoc idea, because it is still vague, what is meant by
> a "range" in a general domain without linear order, but perhaps it opens
> some discussion about a little more control on what randomElement returns.
Actually, the case when there is no order is most intersting.
Namely, ordered ring contains copy of integers, so
random(n)::R
gives a generic implementation in such case. We need
extra effort to handle other cases. The first nontrivial
case is polynomials over finite field.
Main motivation for this category came from factorization
and gcd. There we need to know that probability of hitting
any specified element is low enough. For this one could
specify something like p(a) <= 1/n. However, in practice
we do not know n. More preciely, typically very small n
works. But theoretical estimate is quite large. So we
start from small n and keep doubling n till it is large
enough. Of course, for finite domains we need to handle
"failed" case, but this is separate concern.
For efficiency we want random elements to be "small", however
for correctness it is enough that we have enough distinct
values.
So the specification I wrote is quite weak, to allow easy
implementation. OTOH it is strong enough for typical
use in randomized algorithms.
--
Waldek Hebisch
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/fricas-devel.
For more options, visit https://groups.google.com/d/optout.
