From f51aee83708673ef9941174951bec9aee80cb03c Mon Sep 17 00:00:00 2001 From: Gabriel Dos Reis Date: Thu, 31 Dec 2015 14:56:12 -0800 Subject: Avoid modulus bias in 'random()' usage. --- src/algebra/aggcat.spad.pamphlet | 2 +- src/algebra/boolean.spad.pamphlet | 2 +- src/algebra/divisor.spad.pamphlet | 4 ++-- src/algebra/ffpoly.spad.pamphlet | 2 +- src/algebra/files.spad.pamphlet | 2 +- src/algebra/gpgcd.spad.pamphlet | 6 +++--- src/algebra/groebsol.spad.pamphlet | 2 +- src/algebra/idecomp.spad.pamphlet | 4 ++-- src/algebra/lingrob.spad.pamphlet | 4 ++-- src/algebra/lodof.spad.pamphlet | 2 +- src/algebra/mfinfact.spad.pamphlet | 2 +- src/algebra/mring.spad.pamphlet | 2 +- src/algebra/permgrps.spad.pamphlet | 12 ++++++------ src/algebra/pfbr.spad.pamphlet | 2 +- src/algebra/rep2.spad.pamphlet | 31 +++++++++++-------------------- 15 files changed, 35 insertions(+), 44 deletions(-) (limited to 'src') diff --git a/src/algebra/aggcat.spad.pamphlet b/src/algebra/aggcat.spad.pamphlet index 71db9681..f94297c8 100644 --- a/src/algebra/aggcat.spad.pamphlet +++ b/src/algebra/aggcat.spad.pamphlet @@ -753,7 +753,7 @@ FiniteSetAggregate(S:SetCategory): Category == complement s == difference(universe(), s ) size() == 2 ** size()$S index i == {index(j::PositiveInteger)$S for j in 1..size()$S | bit?(i-1,j-1)} - random() == index((random()$Integer rem (size()$% + 1))::PositiveInteger) + random() == index((1 + random(size()$%)$Integer)::PositiveInteger) lookup s == n:PositiveInteger := 1 diff --git a/src/algebra/boolean.spad.pamphlet b/src/algebra/boolean.spad.pamphlet index 14abe29e..810a9cbe 100644 --- a/src/algebra/boolean.spad.pamphlet +++ b/src/algebra/boolean.spad.pamphlet @@ -101,7 +101,7 @@ Boolean(): Join(OrderedFinite, PropositionalLogic, ConvertibleTo InputForm) with a => 1 2 random() == - even?(random()$Integer) => %false + zero? random(2)$Integer => %false %true convert(x:%):InputForm == diff --git a/src/algebra/divisor.spad.pamphlet b/src/algebra/divisor.spad.pamphlet index f8c15f86..162e67aa 100644 --- a/src/algebra/divisor.spad.pamphlet +++ b/src/algebra/divisor.spad.pamphlet @@ -164,7 +164,7 @@ FractionalIdeal(R, F, UP, A): Exports == Implementation where +/[random()$F * qelt(v, j) for j in minIndex v .. maxIndex v] else randomLC(m, v) == - +/[(random()$Integer rem m::Integer) * qelt(v, j) + +/[random(m)$Integer * qelt(v, j) for j in minIndex v .. maxIndex v] minimize i == @@ -313,7 +313,7 @@ ModularHermitianRowReduction(R): Exports == Implementation where lr := [i for i in minRowIndex x .. maxRowIndex x]$List(Integer) for i in 1..(n := binomial(nr, nc)) repeat (d := determinant x(enumerateBinomial(lr, nc, i), lc)) ~= 0 => - j := i + 1 + (random()$Z rem (n - i)) + j := i + 1 + random(n - i)$Z return gcd(d, determinant x(enumerateBinomial(lr, nc, j), lc)) 0 diff --git a/src/algebra/ffpoly.spad.pamphlet b/src/algebra/ffpoly.spad.pamphlet index cc219171..b2cea908 100644 --- a/src/algebra/ffpoly.spad.pamphlet +++ b/src/algebra/ffpoly.spad.pamphlet @@ -986,7 +986,7 @@ FiniteFieldPolynomialPackage GF : Exports == Implementation where random(m,n) == if m > n then (m,n) := (n,m) d : NNI := (n - m) :: NNI - if d > 1 then n := ((random()$I rem (d::PI)) + m) :: PI + if d > 1 then n := (random(d)$I + m) :: PI random(n) @ diff --git a/src/algebra/files.spad.pamphlet b/src/algebra/files.spad.pamphlet index f09fbae3..b1233e8a 100644 --- a/src/algebra/files.spad.pamphlet +++ b/src/algebra/files.spad.pamphlet @@ -359,7 +359,7 @@ KeyedAccessFile(Entry): KAFcategory == KAFcapsule where f.fileIOmode ~= "input" => error ["File not in read state",f] ks: List Symbol := RKEYIDS(f.fileName)$Lisp null ks => error ["Attempt to read empty file", f] - ix := random()$Integer rem #ks + ix := random(#ks)$Integer k: String := string(ks.ix) [k, SPADRREAD(k, f.fileState)$Lisp] write!(f, pr) == diff --git a/src/algebra/gpgcd.spad.pamphlet b/src/algebra/gpgcd.spad.pamphlet index c247b8cc..d6bd096d 100644 --- a/src/algebra/gpgcd.spad.pamphlet +++ b/src/algebra/gpgcd.spad.pamphlet @@ -153,7 +153,7 @@ GeneralPolynomialGcdPackage(E,OV,R,P):C == T where randomCount:=init() randomCount else - randomR() == (random()$Integer rem 100)::R + randomR() == (random(100)$Integer)::R ---- JHD's local functions --- gcdSameVariables(p1:SUPP,p2:SUPP,lv:List OV) == -- two non-trivial primitive (or, at least, we don't care @@ -299,7 +299,7 @@ GeneralPolynomialGcdPackage(E,OV,R,P):C == T where --JHD range:I:=8 --JHD for i in 1.. repeat --JHD range:=2*range ---JHD lval:=[(random()$I rem (2*range) - range)::R for i in 1..nvr] +--JHD lval:=[(random(2*range)$I - range)::R for i in 1..nvr] --JHD uf1:SUPR:=univariate eval(p1,lvr,lval) --JHD degree uf1 ~= d1 => "new point" --JHD uf2:SUPR:=univariate eval(p2,lvr,lval) @@ -337,7 +337,7 @@ GeneralPolynomialGcdPackage(E,OV,R,P):C == T where --JHD ltry:List List R:=[] --JHD while true repeat --JHD range:=2*range ---JHD lval:=[(random()$I rem (2*range) -range)::R for i in 1..nvr] +--JHD lval:=[(random(2*range)$I -range)::R for i in 1..nvr] --JHD member?(lval,ltry) => "new point" --JHD ltry:=cons(lval,ltry) --JHD uf:=univariate eval(f,lvr,lval) diff --git a/src/algebra/groebsol.spad.pamphlet b/src/algebra/groebsol.spad.pamphlet index eedaa3bb..c89f31d9 100644 --- a/src/algebra/groebsol.spad.pamphlet +++ b/src/algebra/groebsol.spad.pamphlet @@ -113,7 +113,7 @@ GroebnerSolve(lv,F,R) : C == T gbt: L DPoly gb1: Union(L DPoly,"failed") for count in 1.. while testfail repeat - ranvals := [1+(random()$I rem (count*(# lvar))) for vv in rlvar] + ranvals := [1 + random(count*(# lvar))$I for vv in rlvar] val:=+/[rv*(vv::HDPoly) for vv in rlvar for rv in ranvals] val:=val+x::HDPoly diff --git a/src/algebra/idecomp.spad.pamphlet b/src/algebra/idecomp.spad.pamphlet index d5c5d4e4..51ff3a62 100644 --- a/src/algebra/idecomp.spad.pamphlet +++ b/src/algebra/idecomp.spad.pamphlet @@ -146,7 +146,7 @@ IdealDecompositionPackage(vl,nv) : C == T -- take away nv, now doesn't pv:DPoly:=0 pw:DPoly:=0 while not one? degree(lf,y) repeat - val:=random()$Z rem 23 + val:=random(23)$Z pv:=px+val*py pw:=px-val*py Id:=groebner([(univariate(h,x)).pv for h in Id]) @@ -316,7 +316,7 @@ IdealDecompositionPackage(vl,nv) : C == T -- take away nv, now doesn't ---- put the ideal in general position ---- genPosLastVar(J:FIdeal,truelist:List OV):GenPos == x := last truelist ;lv1:List OV :=remove(x,truelist) - ranvals:List(Z):=[(random()$Z rem 23) for vv in lv1] + ranvals:List(Z):=[random(23)$Z for vv in lv1] val:=+/[rv*(vv::DPoly) for vv in lv1 for rv in ranvals] val:=val+(x::DPoly) [ranvals,groebnerIdeal(groebner([(univariate(p,x)).val diff --git a/src/algebra/lingrob.spad.pamphlet b/src/algebra/lingrob.spad.pamphlet index a3018052..25ab9976 100644 --- a/src/algebra/lingrob.spad.pamphlet +++ b/src/algebra/lingrob.spad.pamphlet @@ -265,7 +265,7 @@ LinGroebnerPackage(lv,F) : C == T rval:List Z :=[] for ii in 1..(#lvar-1) repeat c:Z:=0 - while c=0 repeat c:=random()$Z rem 11 + while c=0 repeat c:=random(11)$Z rval:=concat(c,rval) nval:DPoly := (last.lvar)::DPoly - (+/[r*(vv)::DPoly for r in rval for vv in lvar]) @@ -311,7 +311,7 @@ LinGroebnerPackage(lv,F) : C == T xn:=lvar.last val := xn::DPoly nvar1:NNI:=(#lvar-1):NNI - ll: List Z :=[random()$Z rem 11 for i in 1..nvar1] + ll: List Z :=[random(11)$Z for i in 1..nvar1] val:=val+ +/[ll.i*(lvar.i)::DPoly for i in 1..nvar1] LL:=[elt(univariate(f,xn),val) for f in L] LL:= groebner(LL) diff --git a/src/algebra/lodof.spad.pamphlet b/src/algebra/lodof.spad.pamphlet index dd3d6209..aabb5d7d 100644 --- a/src/algebra/lodof.spad.pamphlet +++ b/src/algebra/lodof.spad.pamphlet @@ -58,7 +58,7 @@ SetOfMIntegersInOneToN(m, n): Exports == Implementation where s1 = s2 == s1.bits =$Bits s2.bits coerce(s:%):OutputForm == brace [i::OutputForm for i in elements s] - random() == index((1 + (random()$Integer rem size()))::PI) + random() == index((1 + random(size())$Integer)::PI) reallyEnumerate() == [[b, i] for b in enum(m, n) for i in 1..] member?(p, s) == s.bits.p diff --git a/src/algebra/mfinfact.spad.pamphlet b/src/algebra/mfinfact.spad.pamphlet index bca79804..c7d9645e 100644 --- a/src/algebra/mfinfact.spad.pamphlet +++ b/src/algebra/mfinfact.spad.pamphlet @@ -331,7 +331,7 @@ MultFiniteFactorize(OV,E,F,PG) : C == T -- This function has to be added to Eucliden domain ran(k1:Z) : R == - --if R case Integer then random()$R rem (2*k1)-k1 + --if R case Integer then random(2*k1)$R-k1 --else +/[monomial(random()$F,i)$R for i in 0..k1] diff --git a/src/algebra/mring.spad.pamphlet b/src/algebra/mring.spad.pamphlet index 8eafac0a..85451910 100644 --- a/src/algebra/mring.spad.pamphlet +++ b/src/algebra/mring.spad.pamphlet @@ -132,7 +132,7 @@ MonoidRing(R: Ring, M: Monoid): MRcategory == MRdefinition where res := res + co * p ** ex res pretend PositiveInteger - random() == index( (1+(random()$Integer rem size()$%) )_ + random() == index( (1 + random(size()$%)$Integer )_ pretend PositiveInteger)$% 0 == empty() diff --git a/src/algebra/permgrps.spad.pamphlet b/src/algebra/permgrps.spad.pamphlet index 39a9db79..652d4dbd 100644 --- a/src/algebra/permgrps.spad.pamphlet +++ b/src/algebra/permgrps.spad.pamphlet @@ -272,16 +272,16 @@ PermutationGroup(S:SetCategory): public == private where ranelt ( group : L V NNI , word : L L NNI , maxLoops : I ) : REC3 == -- generate a "random" element numberOfGenerators := # group - randomInteger : I := 1 + (random()$Integer rem numberOfGenerators) + randomInteger : I := 1 + random(numberOfGenerators)$Integer randomElement : V NNI := group.randomInteger words := nil()$(L NNI) if wordProblem then words := word.(randomInteger::NNI) if positive? maxLoops then - numberOfLoops : I := 1 + (random()$Integer rem maxLoops) + numberOfLoops : I := 1 + random(maxLoops)$Integer else numberOfLoops : I := maxLoops while positive? numberOfLoops repeat - randomInteger : I := 1 + (random()$Integer rem numberOfGenerators) + randomInteger : I := 1 + random(numberOfGenerators)$Integer randomElement := times ( group.randomInteger , randomElement ) if wordProblem then words := append ( word.(randomInteger::NNI) , words) numberOfLoops := numberOfLoops - 1 @@ -651,11 +651,11 @@ PermutationGroup(S:SetCategory): public == private where maximalNumberOfFactors < 1 => 1$(PERM S) gp : L PERM S := group.gens numberOfGenerators := # gp - randomInteger : I := 1 + (random()$Integer rem numberOfGenerators) + randomInteger : I := 1 + random(numberOfGenerators)$Integer randomElement := gp.randomInteger - numberOfLoops : I := 1 + (random()$Integer rem maximalNumberOfFactors) + numberOfLoops : I := 1 + random(maximalNumberOfFactors)$Integer while positive? numberOfLoops repeat - randomInteger : I := 1 + (random()$Integer rem numberOfGenerators) + randomInteger : I := 1 + random(numberOfGenerators)$Integer randomElement := gp.randomInteger * randomElement numberOfLoops := numberOfLoops - 1 randomElement diff --git a/src/algebra/pfbr.spad.pamphlet b/src/algebra/pfbr.spad.pamphlet index 8ae314c3..748c5f6d 100644 --- a/src/algebra/pfbr.spad.pamphlet +++ b/src/algebra/pfbr.spad.pamphlet @@ -199,7 +199,7 @@ PolynomialFactorizationByRecursionUnivariate(R, S): public == private where randomCount else if R has random: -> R then randomR() == random() - else randomR() == (random()$Integer rem 100)::R + else randomR() == (random(100)$Integer)::R factorByRecursion pp == and/[zero? degree u for u in coefficients pp] => map(raise,factorPolynomial lower pp) diff --git a/src/algebra/rep2.spad.pamphlet b/src/algebra/rep2.spad.pamphlet index 4219ab67..5524c72d 100644 --- a/src/algebra/rep2.spad.pamphlet +++ b/src/algebra/rep2.spad.pamphlet @@ -312,10 +312,10 @@ RepresentationPackage2(R): public == private where createRandomElement(aG,algElt) == numberOfGenerators : NNI := #aG -- randomIndex := randnum numberOfGenerators - randomIndex := 1+(random()$Integer rem numberOfGenerators) + randomIndex := 1 + random(numberOfGenerators)$Integer algElt := algElt * aG.randomIndex -- randomIndxElement := randnum numberOfGenerators - randomIndex := 1+(random()$Integer rem numberOfGenerators) + randomIndex := 1 + random(numberOfGenerators)$Integer algElt + aG.randomIndex @@ -481,8 +481,7 @@ RepresentationPackage2(R): public == private where -- fingerprint. x0,x1: M R if randomelements then -- random should not be from I - --randomIndex : I := randnum numberOfGenerators - randomIndex := 1+(random()$Integer rem numberOfGenerators) + randomIndex := 1 + random(numberOfGenerators)$Integer x0 := aG0.randomIndex x1 := aG1.randomIndex n : NNI := #row(x0,1) -- degree of representation @@ -496,12 +495,10 @@ RepresentationPackage2(R): public == private where -- chosen elements form "aG". if i = 7 then randomelements := true if randomelements then - --randomIndex := randnum numberOfGenerators - randomIndex := 1+(random()$Integer rem numberOfGenerators) + randomIndex := 1 + random(numberOfGenerators)$Integer x0 := x0 * aG0.randomIndex x1 := x1 * aG1.randomIndex - --randomIndex := randnum numberOfGenerators - randomIndex := 1+(random()$Integer rem numberOfGenerators) + randomIndex := 1 + random(numberOfGenerators)$Integer x0 := x0 + aG0.randomIndex x1 := x1 + aG1.randomIndex else @@ -576,8 +573,7 @@ RepresentationPackage2(R): public == private where result : B := false numberOfGenerators : NNI := #aG -- need a start value for creating random matrices: - -- randomIndex : I := randnum numberOfGenerators - randomIndex := 1+(random()$Integer rem numberOfGenerators) + randomIndex := 1 + random(numberOfGenerators)$Integer x : M R := aG.randomIndex n : NNI := #row(x,1) -- degree of representation foundResult : B := false @@ -587,11 +583,9 @@ RepresentationPackage2(R): public == private where -- create random elements recursively: -- x_i+1 :=x_i * mr1 + mr2, where mr1 and mr2 are randomly -- chosen elements form "aG". - -- randomIndex := randnum numberOfGenerators - randomIndex := 1+(random()$Integer rem numberOfGenerators) + randomIndex := 1 + random(numberOfGenerators)$Integer x := x * aG.randomIndex - --randomIndex := randnum numberOfGenerators - randomIndex := 1+(random()$Integer rem numberOfGenerators) + randomIndex := 1 + random(numberOfGenerators)$Integer x := x + aG.randomIndex -- test whether rank of x is n-1 rk : NNI := rank x @@ -672,8 +666,7 @@ RepresentationPackage2(R): public == private where -- if we switch to randomelements later, we take the last -- fingerprint. if randomelements then -- random should not be from I - --randomIndex : I := randnum numberOfGenerators - randomIndex := 1+(random()$Integer rem numberOfGenerators) + randomIndex := 1 + random(numberOfGenerators)$Integer x : M R := algebraGenerators.randomIndex foundResult : B := false for i in 1..numberOfTries until foundResult repeat @@ -685,11 +678,9 @@ RepresentationPackage2(R): public == private where -- chosen elements form "algebraGenerators". if i = 7 then randomelements := true if randomelements then - --randomIndex := randnum numberOfGenerators - randomIndex := 1+(random()$Integer rem numberOfGenerators) + randomIndex := 1 + random(numberOfGenerators)$Integer x := x * algebraGenerators.randomIndex - --randomIndex := randnum numberOfGenerators - randomIndex := 1+(random()$Integer rem numberOfGenerators) + randomIndex := 1 + random(numberOfGenerators)$Integer x := x + algebraGenerators.randomIndex else x := fingerPrint (i, algebraGenerators.1,_ -- cgit v1.2.3