[Axiom-developer] [#227 'random()$Integer' is a strange function] Using Grep here are all the lines involving random()

[wyscc]

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}
--
forwarded from http://wiki.axiom-developer.org/address@hidden