axiom-developer
[Top][All Lists]

## [Axiom-developer] [#227 'random()$Integer' is a strange function] Using  From: wyscc Subject: [Axiom-developer] [#227 'random()$Integer' is a strange function] Using Grep here are all the lines involving random() Date: Mon, 14 Nov 2005 19:54:11 -0600

Changes http://wiki.axiom-developer.org/227RandomIntegerIsAStrangeFunction/diff
--
You are right, 'random()' is not implementd or specified in 'Float' (it
should!) and the above three categories are the only ones Hyperdoc shows. But
'random()' for 'Float' is available in almost any computation software and the
lack of it in Axiom is simply because Axiom developers were hardly interested
in floating point computations at the time. It surely does not imply that
'random()\$Float' has no applications (how about probability theory and statistics?) The neglect of numerical computation tools may be a fatal flaw in the development of Axiom, especially when it claims to be "the Scientific Computation System". So much so that even after hooking up with NAG's Fortran library and adding graphics, it was not able to attract the real scientific community and only the computer algebra community. With the convergence of symbolic-numerical computation as a dominating theme at ISSAC, it is crucial for the survival of Axiom to strength its numerical applications, and random ! number generation for floating point numbers is definitely a basic tool. You seem to insist to interpret 'random()\$INT' to mean a random integer chosen
out of all integers, and in this sense, then you are correct, but only because
the implementation of 'random()\$INT' uses the Lisp version, not because it is inherently impossible to generate such a random integer (see Third point below). I think you cannot give a better documentation for this function for a category, and you cannot specify a function 'random(n)' without knowing the domain where 'n' lives or an explicit bijection between the set and some segment of integers. The function 'random()' has meaning for any set, finite or not, and in the case the set is finite, it can be used without having to worry about the size of the set. Of course, in implementing such a function for a finite set, like the first line shown below (the result of grep), there is a tacit assumption that the size of the finite set is less than$2^{26}$. We may consider that$2^{26}$is a system constant due to hardware! or efficiency consideration (in fact, due to Lisp implementation) and should be documented. I would agree that in certain places, using random(n) is technically more correct since it would not subject the set to a system limit, but I don't follow your reasoning to remove it altogether. Of course, it is possible to remove any code, and rewrite it in some other form, but that would be both unnecessary and counter-productive. Here're my reasons. Firstly, you cannot really start 'random(n)\$INT' without a seed (here 'n' is
NOT the seed but an upper bound for the range). Axiom uses 'random()\$INT' to provide the seed for its algebra codes (see line in 'd01agents.spad'). Of course, 'random()$Lisp' must have its own seed, possibly taken from some
hardware clock. But 'random()\$INT' provides a higher level of conceptual abstraction for the seed and that is a valid design for algebra code. Secondly, to remove 'random()' means removing all the lines grepped below and hoping it will not break anything. Are you willing to spend the time to track this? Are you going to replace this with 'random(n)' by forcing the usage to require knowing the size of a set a priori (consider the set of compositions of a positive integer 'k', for example) and knowing some hardware clock address? The version 'random()\$S' hides these technicalities from the user. Which
version would be more user friendly? Unless you want to do away with random
elements altogether, you will also have to set up explicit bijections, which is
not possible for the generality Axiom is designed for.

Thirdly, it is not inconceivable to select random elements out of an infinite
set. For example, take Streams over a finite set (say 'GF(2)'). We can
conceptually generate a random stream of binary digits and implement this as
'random()\$Stream(GF(2))'. We simply need to generate each digit randomly one at a time. (I will not argue with you whether such an stream of binary digits is truely random or not, since this is moot because we never finish doing so; and I know that if a pseudo-random generator is used to generate the coordinates of an n-dimension point, then these points lie on certain hyperplanes in n-dimensional space. These are simply properties of these pseudo-random generators, and do not invalidate the mathematical concept of a random element from an infinite set.) Now it is just a simple leap to consider these streams as integers expressed in binary, where the k-th bit is the bit for 2<SUP>k</SUP>. Since Axiom can compute (or at least simulate computing) with s! treams, Axiom can compute with random elements from the ring of integers. Fourthly, which do you think is more efficient: to generate a random integer one bit at a time, and having to stop somewhere eventually, or to generate a random integer within a bound of 2<SUP>26</SUP>? In conclusion, I agree that one may use 'random(n)\$INT' almost everywhere
'random()\$INT' is used in the implementation of 'random()\$S' for a finite set
'S'. I say "almost" because in defining the seed in algebra code, it is
convenient to use 'random()\$INT' ; I say "may" rather than "should" because in many cases where usage is 'random()\$INT' modulo a small integer, the system
bound is of no concerns.  However, I don't think you can or should replace
'random()\$S' by 'random(n)\$S' since the latter need not make sense for some
sets 'S' (for example, where the concept of 'next' or the bijection with '1..n'
is not given).

William

\begin{verbatim}
aggcat~1.spa:     random()     == index((random()$Integer rem (size()$% +
1))::PositiveInteger)
algcat~1.spa:     random() == represents [random()$R for i in 1..rank()]$Vector(R)
algext~1.spa:         random == represents([random()$R for i in 0..d1]) boolea~1.spa: random() == boolea~1.spa: even?(random()$Integer) => false
catdef~1.spa:        ++ random() returns a random element from the set.
d01age~1.spa:      seed:INT := random()$INT d01age~1.spa: r:LDF := [(((random(seed)$INT) :: DF)*s/dseed + l) for i in
1..n]
ddfact~1.spa:           for j in 1..k1 repeat u:=u+monomial(random()$F,j) ddfact~1.spa: for j in 0..k1-1 repeat u:=u+monomial(random()$F,j)
diviso~1.spa:        +/[random()$F * qelt(v, j) for j in minIndex v .. maxIndex v] diviso~1.spa: +/[(random()$Integer rem m::Integer) * qelt(v, j)
diviso~1.spa:          j := i + 1 + (random()$Z rem (n - i)) facuti~1.spa: ran(k:Z):R == random()$R
facuti~1.spa:        ran(k:Z):R == (random(2*k+1)$Z -k)::R ffcg~1.spa: random() == ffcg~1.spa: positiveRemainder(random()$Rep,sizeFF pretend Rep)$Rep -$Rep
1$Rep ffnb~1.spa: ++ random(n) creates a vector over the ground field with random entries. ffnb~1.spa: random(n) == ffnb~1.spa: for i in 1..n repeat v.i:=random()$GF
ffnb~1.spa:    random() == random(extdeg)$INBFF ffpoly~1.spa:-- ++ random()$FFPOLY(GF) generates a random monic polynomial
ffpoly~1.spa:      ++ random(n)$FFPOLY(GF) generates a random monic polynomial ffpoly~1.spa: ++ random(m,n)$FFPOLY(GF) generates a random monic polynomial
ffpoly~1.spa:--    random == qAdicExpansion(random()$I) ffpoly~1.spa:-- if (c := random()$GF) ^= 0 then
ffpoly~1.spa:        if (c := random()$GF) ^= 0 then ffpoly~1.spa: random(m,n) == ffpoly~1.spa: if d > 1 then n := ((random()$I rem (d::PI)) + m) :: PI
ffpoly~1.spa:      random(n)
ffp~1.spa:    random() == random()$Rep files~1.spa: ix := random()$Integer rem #ks
fmod~1.spa:    random()             == random(q)$Rep fmod~1.spa: random() == random(p)$Rep
fracti~1.spa:        ++ random() returns a random fraction.
fracti~1.spa:      random():% ==
fracti~1.spa:        while zero?(d:=random()$S) repeat d fracti~1.spa: random()$S / d
gpgcd~1.spa:--JHD          lval:=[(random()$I rem (2*range) - range)::R for i in 1..nvr] gpgcd~1.spa:--JHD lval:=[(random()$I rem (2*range) -range)::R  for i
in 1..nvr]
groebs~1.spa:             ranvals:L I:=[1+(random()$I rem (count*(# lvar))) for vv in rlvar] idecom~1.spa: val:=random()$Z rem 23
idecom~1.spa:       ranvals:List(Z):=[(random()$Z rem 23) for vv in lv1] intege~1.spa: ++ random(n) returns a random integer from 0 to \spad{n-1}. intege~1.spa: random() == random()$Lisp
intege~1.spa:      random(x) == RANDOM(x)$Lisp intege~1.spa: ++ random(n) returns a random integer from 0 to \spad{n-1}. \end{verbatim} \begin{verbatim} intfac~1.spa: x0 := random()$I
lingro~1.spa:        while c=0 repeat c:=random()$Z rem 11 lingro~1.spa: ll: List Z :=[random()$Z rem 11 for i in 1..nvar1]
lodof~1.spa:    random()               == index((1 + (random()$Integer rem size()))::PI) mfinfa~1.spa: --if R case Integer then random()$R rem (2*k1)-k1
mfinfa~1.spa:      +/[monomial(random()$F,i)$R for i in 0..k1]
modmon~1.spa:         random == UnVectorise([random()$R for i in 0..d1]) mring~1.spa: random() == index( (1+(random()$Integer rem size()$%) )_ naalgc~1.spa: -- [random()$Character :: String :: Symbol for i in
1..rank()$%], _ oderf~1.spa: retract eval(f, t, [random()$Q :: F for k in t])
permgr~1.spa:      ++ random(gp,i) returns a random product of maximal i
generators
permgr~1.spa:      ++ random(gp) returns a random product of maximal 20
generators
permgr~1.spa:      ++ Note: {\em random(gp)=random(gp,20)}.
permgr~1.spa:      randomInteger : I     := 1 + (random()$Integer rem numberOfGenerators) permgr~1.spa: numberOfLoops : I := 1 + (random()$Integer rem maxLoops)
permgr~1.spa:        randomInteger : I := 1 + (random()$Integer rem numberOfGenerators) permgr~1.spa: randomInteger : I := 1 + (random()$Integer rem
numberOfGenerators)
permgr~1.spa:      numberOfLoops : I  := 1 + (random()$Integer rem maximalNumberOfFactors) permgr~1.spa: randomInteger : I := 1 + (random()$Integer rem
numberOfGenerators)
pfbr~1.spa:      randomR() == random()
pfbr~1.spa:   else randomR() == (random()$Integer rem 100)::R pfbr~1.spa: randomR() == random() pfbr~1.spa: else randomR() == (random()$Integer)::R
pfo~1.spa:                                      setelt(redmap, k, random()$Z)::F plot~1.spa:-- jitter := (random()$I) :: F
primel~1.spa:    randomInts(n, m)       ==
[symmetricRemainder(random()$Integer, m) for i in 1..n] primel~1.spa: c := symmetricRemainder(random()$Integer, i)
random~1.spa:        -- random()  generates numbers in 0..rnmax
rep2~1.spa:      randomIndex := 1+(random()$Integer rem numberOfGenerators) rep2~1.spa: randomIndex := 1+(random()$Integer rem numberOfGenerators)
rep2~1.spa:             randomIndex := 1+(random()$Integer rem numberOfGenerators) rep2~1.spa: randomIndex := 1+(random()$Integer rem
numberOfGenerators)
rep2~1.spa:               randomIndex := 1+(random()$Integer rem numberOfGenerators) rep2~1.spa: randomIndex := 1+(random()$Integer rem numberOfGenerators)
rep2~1.spa:          randomIndex := 1+(random()$Integer rem numberOfGenerators) rep2~1.spa: randomIndex := 1+(random()$Integer rem numberOfGenerators)
rep2~1.spa:             randomIndex := 1+(random()$Integer rem numberOfGenerators) rep2~1.spa: randomIndex := 1+(random()$Integer rem
numberOfGenerators)
rep2~1.spa:               randomIndex := 1+(random()$Integer rem numberOfGenerators) sia369~1.spa: ++ random() creates a random element. sia369~1.spa: ++ random(a) creates a random element from 0 to \spad{n-1}. sia369~1.spa: seed : % := 1$Lisp               -- for random()
sia369~1.spa:   random() ==
sia369~1.spa:   random(n) == RANDOM(n)$Lisp string~1.spa: random() == char(random()$Integer rem size())
twofac~1.spa:          vval := random()$F \end{enumerate} \begin{enumerate} twofac~1.spa: val:=random()$extField
\end{verbatim}
--