Ralf Hemmecke wrote:
>
> Unfortunately, you did not in detail comment on what I wrote.
You were writing that 'random_element' is underspecified.
I wrote that conditions I wrote are actually enough
for use in randomized algorithms. Let me add that
one could tighten specification a bit, for example
saying that elements are taken from set which has
at least n elements (or even exactly n elements)
or reqesting that probablility of any single element
is at most 1/n. However, such stronger specification
may require more effort, for example it may be natural
to take set of 2^k element (or some different round number).
Also, gettimg tight inequality for probabilities
takes extra effort.
Concerning beeing more specific about set of valus: I do
not see how we could make useful _generic_ specification.
In principle one could request that when n goes to
infinity random element should fill the whole domain.
But in fact, in randomized algorithms this may be
undesirable. Namely, we want enough values, but
otherwise we want "small" elements to limit cost of
computations.
More generaly, there are thing which needs to be specified
to make algorithm correct. But there is also "quality of
implementation" factor: we want our routines to be resonably
efficient and random elements should help getting efficiency.
But such quality factors are hard to specify. If specific
choice leads to better efficiency, it make sense to docoment
this somewhere. But documentation strings are bad place to
put such information. Also, there is really not much difference
to other routines: documentation strings tells what routines
do but frequently there are alternative choices, equivalent
from correctness point of view, but leading to different
speed.
> On 10/05/2015 02:17 PM, Waldek Hebisch wrote:
> > 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.
>
> If you are satisfied with random integers, then that must be stated in
> the category documentation.
You mean that we should state explicitely that random
elements need not exhaust the domain?
> In fact, I more and more get the impression that you don't actually want
> "RandomChoice". What you want is a stream of elements of % that do not
> repeat. Am I wrong?
It would be nice if we could get non-repetition for free. But
it seems that user have more info how to handle possible
repetition. OTOH merely having non-repeating sequence is
not enough. In practice we enlagre n as geometric sequence,
so we need enough randomness.
> > Main motivation for this category came from factorization
> > and gcd.
>
> Well. That somehow sounds like you want to easily throw away "unlucky
> primes".
That separate topic.
--
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.
