mmcdara

867 Reputation

13 Badges

3 years, 232 days

MaplePrimes Activity


These are Posts that have been published by mmcdara

Here is a little animation to wish all of you a Merry Christmas

FireWorks.mw


Hi, 

This is more of an open discussion than a real question. Maybe it would gain to be displaced in the post section?

Working with discrete random variables I found several inconsistencies or errors.
In no particular order: 

  • The support of a discrete RV is not defined correctly (a real range instead of a countable set)
  • The plot of the probability function (which, in my opinion, would gain to be renamed "Probability Mass Function, see https://en.wikipedia.org/wiki/Probability_mass_function) is not correct.
  • The  ProbabiliytFunction of a discrte rv of EmpiricalDistribution can be computed at any point, but its formal expression doesn't exist (or at least is not accessible).
  • Defining the discrete rv "toss of a fair dice"  with EmpiricalDistribution and DiscreteUniform gives different results.


The details are given in the attached file and I do hope that the companion text is clear enough to point the issues.
I believe there is no major issues here, but that Maple suffers of some lack of consistencies in the treatment of discrete (at least some) rvs. Nothing that could easily be fixed.


As I said above, if some think this question has no place here and ought to me moved to the post section, please feel free to do it.

Thanks for your attention.


 

restart:

with(Statistics):


Two alternate ways to define a discrete random variable on a finite set
of equally likely outcomes.

Universe    := [$1..6]:
toss_1_dice := RandomVariable(EmpiricalDistribution(Universe));
TOSS_1_DICE := RandomVariable(DiscreteUniform(1, 6));

_R

 

_R0

(1)


Let's look to the ProbabilityFunction of each RV

ProbabilityFunction(toss_1_dice, x);
ProbabilityFunction(TOSS_1_DICE, x);

"_ProbabilityFunction[Typesetting:-mi("x",italic = "true",mathvariant = "italic")]"

 

piecewise(x < 1, 0, x <= 6, 1/6, 6 < x, 0)

(2)


It looks like the procedure ProbabilityFunction is not an attribute of RV with EmpiticalDistribution.
Let's verify

law := [attributes(toss_1_dice)][3]:
lprint(exports(law))

Conditions, ParentName, Parameters, CDF, DiscreteValueMap, Mean, Median, Mode, ProbabilityFunction, Quantile, Specialize, Support, RandomSample, RandomVariate

 


Clearly ProbabilityFunction is an attribute of toss_1_dice.

In fact it appears the explanation of the difference of behaviours relies upon different definitions
of the set of outcomes of toss_1_dice and TOSS_1_DICE

LAW := [attributes(TOSS_1_DICE)][3]:
exports(LAW):

law:-Conditions;
LAW:-Conditions;

[(Vector(6, {(1) = 1, (2) = 2, (3) = 3, (4) = 4, (5) = 5, (6) = 6}))::rtable]

 

[1 < 6]

(3)


From :-Conditions one can see that toss_1_dice is realy a discrete RV defined on a countable set of outcomes,
but that nothing is said about the set over which TOSS_1_DICE is defined.

The truly discrete definition of toss_1_dice is confirmed here :
(the second result is correct

ProbabilityFinction(toss_1_dice, x) = {0 if x < 1, 0 if x > 6, 1/6 if x::integer, 0 otherwise

ProbabilityFunction~(toss_1_dice, Universe);
ProbabilityFunction~(toss_1_dice, [seq(0..7, 1/2)]);

[1/6, 1/6, 1/6, 1/6, 1/6, 1/6]

 

[0, 0, 1/6, 0, 1/6, 0, 1/6, 0, 1/6, 0, 1/6, 0, 1/6, 0, 0]

(4)


One can also see that the Support of both of these RVs are wrong

(see for instance https://en.wikipedia.org/wiki/Discrete_uniform_distribution)

There should be {1, 2, 3, 4, 5, 6}, not a RealRange.

Support(toss_1_dice);
Support(TOSS_1_DICE);

RealRange(1, 6)

 

RealRange(1, 6)

(5)

 

0

 

{1, 2, 3, 4, 5, 6}

 

 


Now this is the surprising ProbabilityFunction of TOSS_1_DICE.
This obviously wrong result probably linked to the weak definition of the conditions for this RB.

# plot(ProbabilityFunction(TOSS_1_DICE, x), x=0..7);
plot(ProbabilityFunction(TOSS_1_DICE, x), x=0..7, discont=true)

 


These differences of treatments raise a lot of questions :
    -  Why is a DiscreteUniform RV not defined on a countable set?
    -  Why does the ProbabilityFunction of an EmpiricalDistribution return no result
        if its second parameter is not set to one  its outcomes.

 All this without even mentioning the wrong plot shown above.
 

I believe something which would work like the module below would be much better than what is done

right now

 

EmpiricalRV := module()
export MassDensityFunction, PlotMassDensityFunction, Support:

MassDensityFunction := proc(rv, x)
  local u, v, N:
  u := [attributes(rv)][3]:
  if u:-ParentName = EmpiricalDistribution then
    v := op([1, 1], u:-Conditions);
    N := numelems(v):
    return piecewise(op(op~([seq([x=v[n], 1/N], n=1..N)])), 0)
  else
    error "The random variable does not have an EmpiricalDistribution"
  end if
end proc:

PlotMassDensityFunction := proc(rv, x1, x2)
  local u, v, a, b:
  u := [attributes(rv)][3]:
  if u:-ParentName = EmpiricalDistribution then
    v := op([1, 1], u:-Conditions);
    a := select[flatten](`>=`, v, x1);
    b := select[flatten](`<=`, a, x2);
    PLOT(seq(CURVES([[n, 0], [n, 1/numelems(v)]], COLOR(RGB, 0, 0, 1), THICKNESS(3)), n in b), VIEW(x1..x2, default))
  else
    error "The random variable does not have an EmpiricalDistribution"
  end if
end proc:

Support := proc(rv, x1, x2)
  local u, v, a, b:
  u := [attributes(rv)][3]:
  if u:-ParentName = EmpiricalDistribution then
    v := op([1, 1], u:-Conditions);
    return {entries(v, nolist)}
  else
    error "The random variable does not have an EmpiricalDistribution"
  end if
end proc:

end module:
 

EmpiricalRV:-MassDensityFunction(toss_1_dice, x);
 

piecewise(x = 1, 1/6, x = 2, 1/6, x = 3, 1/6, x = 4, 1/6, x = 5, 1/6, x = 6, 1/6, 0)

(6)

f := unapply(EmpiricalRV:-MassDensityFunction(toss_1_dice, x), x):
f(2);
f(5/2);
 

1/6

 

0

(7)

EmpiricalRV:-PlotMassDensityFunction(toss_1_dice, 0, 7);

 

 


 

Download Discrete_RV.mw

 

 

Hi, 

As an amusement,  I decided several months ago to develop some procedures to fill a simple polygon* by hatches or simple textures.

* A simple polygon is a polygon  whose sides either do not intersect or either have a common vertex.

This work started with the very simple observation that if I was capable to hatch or texture a triangle, I will be too to hatch or texture any simple polygon once triangulated.
I also did some work to extend this work to non-simple polygons but there remains some issues to fix (which explains while it is not deliverd here).

The main ideat I used for hatching and texturing is based upon the description of each triangles by a set of 3 inequalities that any interior point must verify.
A hatch of this triangle is thius a segment whose each point is interior.
The closely related idea is used for texturing. Given a simple polygon, periodically replicated to form the texture, the set of points of each replicate that are interior to a given triangle must verify a set of inequalities (the 3 that describe the triangle, plus N if the pattern of the texture is a simple polygon with N sides).

Unfortunately I never finalise this work.
Recently @Christian Wolinski asked a question about texturing that reminded me this "ancient" work of mine.
So I decided to post it as it is, programatically imperfect, lengthy to run, and most of all french-written for a large part.
I guess it is a quite unorthodox way to proceed but some here could be interested by this work to take it back and improve it.

The module named "trianguler" (= triangulate) is a translation into Maple of Frederic Legrand's Python code (full reference given in the worksheet).
I added my own procedure "hachurer" (= hatching) to this module.
The texturing part is not included in this module for it was still in development.

A lot of improvements can be done that I could list, but I prefer not to be too intrusive in your evaluation of this work. So make your own idea about it and do not hesitate to ask me any informations you might need (in particular translation questions).


PS: this work has been done with Maple 2015.2
 

restart:


Reference: http://www.f-legrand.fr/scidoc/docmml/graphie/geometrie/polygone/polygone.html
                    (in french)
                    reference herein : M. de Berg, O. Cheong, M. van Kreveld, M. Overmars,  
                                                 Computational geometry,  (Springer, 2010)

Direct translation of the Frederic Legrand's Python code


Meaning of the different french terms

voisin_sommet  (n, i, di)
        let L the list [1, ..., n] where n is the number of vertices
        This procedure returns the index of the neighbour (voisin) of the vertex (sommet) i when L is rotated by di

equation_droite  (P0, P1, M)
        Let P0 and P1 two vertices and M an arbitrary point.
        Let (P0, P1) the vector originated at P0 and ending at P1 (idem for (P0, M)) and u__Z the unitary vector in the Z direction.
        This procedure returns (P0, P1) o (P0, M) . u__Z

point_dans_triangle  (triangle, M) P1, P2]
        This procedure returns "true" if point M is within (strictly) the  triangle "triangle" and "false" if not.

sommet_distance_maximale  (polygone, P0, P1, P2, indices)    
        Given a polygon (polygone) threes vertices P0, P1 and P2 and a list of indices , this procedure returns
        the vertex of the polygon "polygone" which verifies: 1/ this vertex is strictly within
        the triangle [P0, P1, P2] and 2/ it is the farthest from side [P1, P2] amid all the vertices that verifies point 1/.
        If there is no such vertex the procedure returns NULL.

sommet_gauche (polygone)
        This procedure returns the index of the leftmost ("gauche" means "left") vertex in polygon "polygone".
        If more than one vertices have the same minimum abscissa value then only the first one is returned.

nouveau_polygone(polygone,i_debut,i_fin)
        This procedure creates a new polygon from index i_debut (could be translated by i_first) to i_end (i_last)

trianguler_polygone_recursif(polygone)
        This procedure recursively divides a polygon in two parts A and B from its leftmost vertex.
         If A (B) is a triangle the list "liste_triangles" (mening "list of triangles") is augmented by A (B);
         if not the procedure executes recursively on A and B.

trianguler_polygone(polygone)
         This procedure triangulates the polygon "polygon"

hachurer(shapes, hatch_angle, hatch_number, hatch_color)
         This procedure generates stes of hatches of different angles, colors and numbers


Limitations:
   1/ "polygone" is a simply connected polygon
   2/  two different sides S and S', either do not intersect or either have a common vertex

trianguler := module()
export voisin_sommet, equation_droite, interieur_forme, point_dans_triangle, sommet_distance_maximale,
       sommet_gauche, nouveau_polygone, trianguler_polygone_recursif, trianguler_polygone, hachurer:

#-------------------------------------------------------------------
voisin_sommet := (n, i, di) -> ListTools:-Rotate([$1..n], di)[i]:



#-------------------------------------------------------------------
equation_droite := proc(P0, P1, M) (P1[1]-P0[1])*(M[2]-P0[2]) - (P1[2]-P0[2])*(M[1]-P0[1]) end proc:


#-------------------------------------------------------------------
interieur_forme := proc(forme, M)
  local N:
  N := numelems(forme);
  { seq( equation_droite(forme[n], forme[piecewise(n=N, 1, n+1)], M) >= 0, n=1..N) }
end proc:


#-------------------------------------------------------------------
point_dans_triangle := proc(triangle, M)
  `and`(
          is( equation_droite(triangle[1], triangle[2], M) > 0 ),
          is( equation_droite(triangle[2], triangle[3], M) > 0 ),
          is( equation_droite(triangle[3], triangle[1], M) > 0 )
       )
end proc:



#-------------------------------------------------------------------
sommet_distance_maximale := proc(polygone, P0, P1, P2, indices)
  local n, distance, j, i, M, d;

  n        := numelems(polygone):
  distance := 0:
  j        := NULL:

  for i from 1 to n do
    if `not`(member(i, indices)) then
      M := polygone[i];
      if point_dans_triangle([P0, P1, P2], M) then
        d := abs(equation_droite(P1, P2, M)):
        if d > distance then
          distance := d:
          j := i
        end if:
      end if:
    end if:
  end do:
  return j:
end proc:


#-------------------------------------------------------------------
sommet_gauche := polygone -> sort(polygone, key=(x->x[1]), output=permutation)[1]:



#-------------------------------------------------------------------
nouveau_polygone := proc(polygone, i_debut, i_fin)
  local n, p, i:

  n := numelems(polygone):
  p := NULL:
  i := i_debut:

  while i <> i_fin do
    p := p, polygone[i]:
    i := voisin_sommet(n, i, 1)
  end do:
  p := [p, polygone[i_fin]]
end proc:



#-------------------------------------------------------------------
trianguler_polygone_recursif := proc(polygone)
  local n, j0, j1, j2, P0, P1, P2, j, polygone_1, polygone_2:
  global liste_triangles:
  n  := numelems(polygone):
  j0 := sommet_gauche(polygone):
  j1 := voisin_sommet(n, j0, +1):
  j2 := voisin_sommet(n, j0, -1):
  P0 := polygone[j0]:
  P1 := polygone[j1]:
  P2 := polygone[j2]:
  j  := sommet_distance_maximale(polygone, P0, P1, P2, [j0, j1, j2]):

  if `not`(j::posint) then
    liste_triangles := liste_triangles, [P0, P1, P2]:
    polygone_1      := nouveau_polygone(polygone,j1,j2):
    if numelems(polygone_1) = 3 then
      liste_triangles := liste_triangles, polygone_1:
    else
      thisproc(polygone_1)
    end if:

  else
    polygone_1 := nouveau_polygone(polygone, j0, j ):
    polygone_2 := nouveau_polygone(polygone, j , j0):
    if numelems(polygone_1) = 3 then
      liste_triangles := liste_triangles, polygone_1:
    else
      thisproc(polygone_1)
    end if:
    if numelems(polygone_2) = 3 then
      liste_triangles := liste_triangles, polygone_2:
    else
      thisproc(polygone_2)
    end if:
  end if:

  return [liste_triangles]:
end proc:


#-------------------------------------------------------------------
trianguler_polygone := proc(polygone)
  trianguler_polygone_recursif(polygone):
  return liste_triangles:
end proc:


#-------------------------------------------------------------------
hachurer := proc(shapes, hatch_angle::list, hatch_number::list, hatch_color::list)

local A, La, Lp;
local N, P, _sides, L_sides, Xshape, ch, rel, p_rel, n, sol, p_range:
local AllHatches, window, p, _segment:
local NT, ka, N_Hatches, p_range_t, nt, shape, p_hatches, WhatHatches:

#-----------------------------------------------------------------
# internal functions:
#
# La(x, y, alpha, p) is the implicit equation of a straight line of angle alpha relatively
#                    to the horizontal axis and intercept p
#
# Lp(x, y, P) is the implicit equation of a straight line passing through points P[1] and P[2]
#
# interieur_triangle(triangle, M)

La := (x, y, alpha, p) -> cos(alpha)*x - sin(alpha)*y + p;
Lp := proc(x, y, P::list) (x-P[1][1])*(P[2][2]-P[1][2]) - (y-P[1][2])*(P[2][1]-P[1][1] = 0) end proc;


p_range    := [+infinity, -infinity]:
NT         := numelems(shapes):

AllHatches := NULL:

for ka from 1 to numelems(hatch_angle) do
  A         := hatch_angle[ka]:
  N_Hatches := hatch_number[ka]:
  p_range_t := NULL:
  _sides    := []:
  L_sides   := []:
  rel       := []:
  for nt from 1 to NT do

    shape := shapes[nt]:
    # _sides  : two points description of the sides of the shape
    # L_sides : implicit equations of the straight lines that support the sides

    N        := [1, 2, 3];
    P        := [2, 3, 1];
    _sides   := [ _sides[] , [ seq([shape[n], shape[P[n]]], n in N) ] ];
    L_sides  := [ L_sides[], Lp~(x, y, _sides[-1]) ];

    # Inequalities that define the interior of the shape

    rel := [ rel[], trianguler:-interieur_forme(shape, [x, y]) ];
  
    # Given the orientation of the hatches we search here the extreme values of
    # the intercept p for wich a straight line of equation La(x, y, alpha, p)
    # cuts the shape.
    
    p_rel := NULL:
    
    for n from 1 to numelems(L_sides[-1]) do
      sol   := solve({La(x, y, A, q), lhs(L_sides[-1][n])} union rel[-1], [x, y]);
      p_rel := p_rel, `if`(sol <> [], [rhs(op(1, %)), rhs(op(3, %))], [+infinity, -infinity]);
    end do:
    p_range_t := p_range_t, evalf(min(op~(1, [p_rel]))..max(op~(2, [p_rel])));
    p_range   := evalf(min(op~(1, [p_rel]), op(1, p_range))..max(op~(2, [p_rel]), op(2, p_range)));

  end do: # end of the loop over triangles

  p_range_t := [p_range_t]:
  p_hatches := [seq(p_range, (op(2, p_range)-op(1, p_range))/N_Hatches)]:
  # Building of the hatches
  #
  # This construction is far from being optimal.
  # Here again the main goal was to obtain the hatches with a minimum effort
  # if algorithmic development.

  window      := min(op~(1..shape))..max(op~(1..shape)):
  WhatHatches := map(v -> map(u -> if verify(u, v, 'interval'('closed') ) then u end if, p_hatches), p_range_t):

  for nt from 1 to NT do
    for p in WhatHatches[nt] do
      _segment := []:
      for n from 1 to numelems(L_sides[nt]) do
         _segment := _segment, evalf( solve({La(x, y, A, p), lhs(L_sides[nt][n])} union rel[nt], [x, y]) );
      end do;
      map(u -> u[], [_segment]);
      AllHatches := AllHatches, plot(map(u -> rhs~(u), %), color=hatch_color[ka]):
    end do:
  end do;

end do: # end of loop over hatch angles

plots:-display(
  PLOT(POLYGONS(polygone, COLOR(RGB, 1$3))),
  AllHatches,
  scaling=constrained
)

end proc:

end module:

 

Legrand's example (see reference above)

 

 

global liste_triangles:
liste_triangles := NULL:

polygone := [[0,0],[0.5,-1],[1.5,-0.2],[2,-0.5],[2,0],[1.5,1],[0.3,0],[0.5,1]]:

trianguler:-trianguler_polygone(polygone):

PLOT(seq(POLYGONS(u, COLOR(RGB, rand()/10^12, rand()/10^12, rand()/10^12)), u in liste_triangles), VIEW(0..2, -2..2))

 

trianguler:-hachurer([liste_triangles], [-Pi/4, Pi/4], [40, 40], [red, blue])
 

 

F := (P, a, b) -> map(p -> [p[1]+a, p[2]+b], P):

MOTIF  := [[0, 0], [0.05, 0], [0.05, 0.05], [0, 0.05]];
motifs := [ seq(seq(F(MOTIF, 0+i*0.075, 0+j*0.075), i=0..26), j=-14..13) ]:

plots:-display(
  plot([polygone[], polygone[1]], color=red, filled),
  map(u -> plot([u[], u[1]], color=blue, filled, scaling=constrained), motifs)
):

texture    := NULL:
rel_motifs := map(u -> trianguler:-interieur_forme(u, [x, y]), motifs):
  
for ref in liste_triangles do
  ref;
  #
  # the three lines below are used to define REF counter clockwise
  #
  g           := trianguler:-sommet_gauche(ref):
  bas         := sort(op~(2, ref), output=permutation);
  REF         := ref[[g, op(map(u -> if u<>g then u end if, bas))]];
  rel_ref     := trianguler:-interieur_forme(REF, [x, y]): #print(ref, REF, rel_ref);
  texture_ref := map(u -> plots:-inequal(rel_ref union u, x=0..2, y=-1..1, color=blue, 'nolines'), rel_motifs):
  texture     := texture, texture_ref:
end do:

plots:-display(
  plot([polygone[], polygone[1]], color=red, scaling=constrained),
  texture
)

[[0, 0], [0.5e-1, 0], [0.5e-1, 0.5e-1], [0, 0.5e-1]]

 

 

MOTIF  := [[0, 0], [0.05, 0], [0.05, 0.05], [0, 0.05]];
motifs := [ seq(seq(F(MOTIF, piecewise(j::odd, 0.05, 0.1)+i*0.1, 0+j*0.05), i=-0.2..20), j=-20..20) ]:
plots:-display(
  plot([polygone[], polygone[1]], color=red, filled),
  map(u -> plot([u[], u[1]], color=blue, filled, scaling=constrained), motifs)
):

texture    := NULL:
rel_motifs := map(u -> trianguler:-interieur_forme(u, [x, y]), motifs):
  
for ref in liste_triangles do
  ref;
  g := trianguler:-sommet_gauche(ref):
  bas := sort(op~(2, ref), output=permutation);
  REF := ref[[g, op(map(u -> if u<>g then u end if, bas))]];
  rel_ref     := trianguler:-interieur_forme(REF, [x, y]): #print(ref, REF, rel_ref);
  texture_ref := map(u -> plots:-inequal(rel_ref union u, x=0..2, y=-1..1, color=blue, 'nolines'), rel_motifs):
  texture     := texture, texture_ref:
end do:

plots:-display(
  plot([polygone[], polygone[1]], color=red, scaling=constrained),
  texture
)

[[0, 0], [0.5e-1, 0], [0.5e-1, 0.5e-1], [0, 0.5e-1]]

 

 

MOTIF  := [[0, 0], [0.4, 0], [0.4, 0.14], [0, 0.14]]:
motifs := [ seq(seq(F(MOTIF, piecewise(j::odd, 0.4, 0.2)+i*0.4, 0+j*0.14), i=-1..4), j=-8..7) ]:


plots:-display(
  plot([polygone[], polygone[1]], color=red, filled),
  map(u -> plot([u[], u[1]], color=blue, filled, scaling=constrained), motifs)
):

palettes := ColorTools:-PaletteNames():
ColorTools:-GetPalette("HTML"):

couleurs := [SandyBrown, PeachPuff, Peru, Linen, Bisque, Burlywood, Tan, AntiqueWhite,      NavajoWhite, BlanchedAlmond, PapayaWhip, Moccasin, Wheat]:

nc   := numelems(couleurs):
roll := rand(1..nc):

motifs_nb      := numelems(motifs):
motifs_couleur := [ seq(cat("HTML ", couleurs[roll()]), n=1..motifs_nb) ]:

texture    := NULL:
rel_motifs := map(u -> trianguler:-interieur_forme(u, [x, y]), motifs):
  
for ref in liste_triangles do
  ref;
  g := trianguler:-sommet_gauche(ref):
  bas := sort(op~(2, ref), output=permutation);
  REF := ref[[g, op(map(u -> if u<>g then u end if, bas))]];
  rel_ref     := trianguler:-interieur_forme(REF, [x, y]): #print(ref, REF, rel_ref);
  texture_ref := map(n -> plots:-inequal(rel_ref union rel_motifs[n], x=0..2, y=-1..1, color=motifs_couleur[n], 'nolines'), [$1..motifs_nb]):
  texture     := texture, texture_ref:
end do:

plots:-display(
  plot([polygone[], polygone[1]], color=red, scaling=constrained),
  texture
)

 

MOTIF  := [ seq(0.1*~[cos(Pi/6+Pi/3*i), sin(Pi/6+Pi/3*i)], i=0..5) ]:
motifs := [ seq(seq(F(MOTIF, i*0.2*cos(Pi/6)+piecewise(j::odd, 0, 0.08), j*0.3*sin(Pi/6)), i=0..12), j=-6..6) ]:


plots:-display(
  plot([polygone[], polygone[1]], color=red, filled),
  map(u -> plot([u[], u[1]], color=blue, filled, scaling=constrained), motifs)
):


motifs_nb      := numelems(motifs):
motifs_couleur := [ seq(`if`(n::even, yellow, brown) , n=1..motifs_nb) ]:

texture    := NULL:
rel_motifs := map(u -> trianguler:-interieur_forme(u, [x, y]), motifs):
  
for ref in liste_triangles do
  ref;
  g := trianguler:-sommet_gauche(ref):
  bas := sort(op~(2, ref), output=permutation);
  REF := ref[[g, op(map(u -> if u<>g then u end if, bas))]];
  rel_ref     := trianguler:-interieur_forme(REF, [x, y]): #print(ref, REF, rel_ref);
  texture_ref := map(n -> plots:-inequal(rel_ref union rel_motifs[n], x=0..2, y=-1..1, color=motifs_couleur[n], 'nolines'), [$1..motifs_nb]):
  texture     := texture, texture_ref:
end do:

plots:-display(
  plot([polygone[], polygone[1]], color=red, scaling=constrained),
  texture
)

 

 


 

Download Triangulation_Hatching_Texturing.mw

I'm particularly interested in data analysis and more specifically in statistical analysis of computer code outputs.

One of the main activity of this very broad field is named Uncertainty Propagation. In a few words it consists in perturbing the inputs of a computational code in order to understand (and quantify) how these perturbations propagates through the outputs of this code.

At the core of uncertainty propagation is the ability to generate large numbers of "random" variations of the inputs. Knowing that these entries can be counted in tens, one sees that the first problem consists in generating "random" points in a space of potentially very large dimension.

Even among my mathematician colleagues an impressive number of them is completely ignorant of the way "random" numbers are generated. I guess that a lot of Mapleprimes' users are too. My purpose is not to give a course on this topic and the affording litterature is vast enough for everyone interested might find informations of any level of complexity.
Among those who have some knowledge about Pseudo Random Numbers Generators (PRNG), only a few of them know that a PRNG has to pass severe tests ("tests of randomness") before the streams of number it generates might  be qualified as "reasonably random" and therefore this PRNG might be released.

One of most famous example of a bad PRNG is given by "randu" (IBM 1966, and probably used in Fortran libraries during more than 30 years), this same PRNG that Knuth qualified himself as the "infamous generator".

These tests of randomness are generally gathered in dedicated libraries and Diehard is probably tone of the most known of them.
Diehard has originally been developed by George Marsaglia more than twenty years ago and it's still widely ued today.

I recently decided, not because I have doubts about the quality of the work done by Maplesoft, to test the Maple's PRNG named "Mersenne Twister". First, because it can do no harm to publish quantitative information that allows everyone to know that it is using a proven PRNG; second, because the (very simple) approach used here can fill the gaps I have mentioned above.

Mersenne Twister (often dubbed mt19937) is considered as a very good PRNG; it is used in a lot of applications (including finance where it is not so rare to sample input spaces of dimensions larger than 1000... ok I know, mt19937 is often considered as a poor candidate for cryptography applications, but it's not my concern here).

I have thus decided to spend some time to run the Diehard suite of tests on a sequence of integers numbers generated by RandomTools[MersenneTwister].


 

restart:


DIEHARD tests suite for Pseudo Random Numbers Generators (PRNG)

Reference: http://webhome.phy.duke.edu/~rgb/General/dieharder.php

The installation procedure (Mac OSX) can be found here
    https://gist.github.com/blixt/9abfafdd0ada0f4f6f26
or here
    http://macappstore.org/dieharder/

For other operating systems, please search on the web pages.


dieharder [-h]   # for inline help
dieharder -l      # to get the lists all the avaliable tests




A description of the many tests can be found here:
    https://en.wikipedia.org/wiki/Diehard_tests
    https://sites.google.com/site/astudyofentropy/background-information/the-tests/dieharder-test-descriptions
    https://www.stata.com/support/cert/diehard/randnumb_mt64.out

General theory about PRNG testing can be found here (a reference among many):
    http://liu.diva-portal.org/smash/get/diva2:740158/FULLTEXT01.pdf

or here (more oriented to the NIST test suite)
    https://www.random.org/analysis/Analysis2005.pdf
    https://nvlpubs.nist.gov/nistpubs/legacy/sp/nistspecialpublication800-22r1a.pdf



In a terminal window execute the following commands for an exhaustive testing ("-a" option).
The "-g 202" option means that the generator is replaced by a text format input file
(use dieharder -h for more details).

cd //..../Desktop/DIEHARD

dieharder -g 202 -f SomeAsciiFile -a > //..../Desktop/DIEHARD/TheResultFile.txt

Be carefull, the complete testing takes several hours (about 5 on my computer)



__________________________________________________________________________________
 


Maple's Mersenne Twister Generator

Maple help page : RandomTools[MersenneTwister][GenerateInteger]
(see rincluded references to the Mersenne Twister PRNG).

Note: in the sequel this generator will be dubbed mt19937


The Mersenne Twister is implemented in many softwares.
It is higly likely that this PRNG (and the others these softwares propose) have been intensively
tested with one of the existing PRNG testing libraries.
Unfortunately only a few editors have made public the results of these tests (probably because
the implementation in itself is rarely questioned... but a code typo is always a possibility).

One exception is ths software STATA.
A summary of the results can be found here
   https://www.stata.com/support/cert/diehard/.
A complete description of the results of the tests passed is given here
   https://www.stata.com/support/cert/diehard/randnumb_mt64.out

The classical pattern of the performances of mt19937 can be found here

   http://www2.ic.uff.br/~celso/artigos/pjo6.ps.

and the table below comes from it (P means "Passed", F means "Failed"):


____________________________________________________________________________


In the Maple code below, a sequence of N UnsignedInt32 numbers is generated from the
Maple's Mersenne Twister and the result is exported in an ASCII file.
The Seed is set to 1 (SetState(state=1)) to compare, with a small value of N (let's say N=10)
the sequence produced by Maple's mt19937 with the the sequence of the same length generated
by Diehard's mt19937.
To generate this later sequence and save it in file Diehard_mt19937, just run in a terminan window
the command (-S 1 means "seed = 1", -t 10 means "a sequence of length 10"):
   dieharder -S 1 -B -o -t 10 > Diehard_mt19937

About the value of N:

In http://webhome.phy.duke.edu/~rgb/General/dieharder.php it's recommend that N be at least
equal to 2.5 million; STATA used N=3 million.
Other web sources say this value is too small.
For N=10 million the Maple's mt19937 doesn't pass the tests successfully.
I used here N=50 million (the resulting ASCII file has size 537 Mo).



Name of the input file.

The file generated by Maple is named Maple_mt19937_N=5e7.txt



One important thing is the preamble of a licit input file.

This preamble must have 6 lines (the value 10 right to count must be set to the value of N).
A licit preamble is of the form.

#==================================================================

# some text indicating the generator used

#==================================================================

type: d

count: 10

numbit: 32

As Maple_mt19937_N=5e7.txt is generated from an ExportMatrix command, this preamble is added
by hand.
 


Running multiple Diehard tests

To run the same tests used to qualify STATA's Mersenne Twister, open a terminal window,
go to the directory that contains input file Maple_mt19937_N=5e7.txt and run this script:

 for i in {0,1,2,3,4,8,9,10,11,12,13,14,15,16}; do

    dieharder -g 202 -f Maple_mt19937_N=5e7.txt -d $i >> Diehard___Maple_mt19937_N=5e7

 done ;

The results are then forked in the ASCII file Diehard___Maple_mt19937_N=5e7

 

with(RandomTools[MersenneTwister]):

dir := cat("/", currentdir(), "Desktop/DIEHARD/"):
InputFile := cat(dir, "Maple_mt19937_N=5e7.txt"):

SetState(state=1);

N := 5*10^7:

st := time():
S := convert([seq(GenerateUnsignedInt32(), i=1..N)], Matrix)^+;
time()-st;

S := Vector(4, {(1) = ` 50000000 x 1 `*Matrix, (2) = `Data Type: `*anything, (3) = `Storage: `*rectangular, (4) = `Order: `*Fortran_order})

 

84.526

(1)

st := time():
ExportMatrix(InputFile, S, format=rectangular, mode=ascii);
time()-st;

537066525

 

61.926

(2)


Diehard's results


Full test suite (about 5 hours of computational time)

Command :
dieharder -g 202 -f Maple_mt19937_N=5e7.txt -a > Diehard___ALL___Maple_mt19937_N=5e7


The results are compared to those obtained for Diehard's mt19937.
Two ways are used :

  - 1 - In a first stage one generates a stream of PRN and store it in an ASCII file (just as we did with Maple).
         The whole suite of tests is then run on this file.
         Commands (-g 013 codes for mt19937):

         dieharder -S 1 -g 013 -o -t 50000000 > Diehard_mt19937_N=5e7.txt
         dieharder -g 202 -f Diehard_mt19937_N=5e7.txt -a > Diehard___ALL___Diehard_mt19937_N=5e7



  - 2 - The whole suite is run by invoking directectly mt19937 "online"
         Commands :
         dieharder -S 1 -g 013 -t 50000000 -a > Diehard___ALL___Online


A UNIX diff command has been used to verify that the two files Maple_mt19937_N=5e7.txt and
 Diehard_mt19937_N=5e7.txt were identical (thet were).

Note that the Diehard doens't responds identically depending on the stream of random numbers comes from a file
or is generated online (this last [- 2 -] situation seems to give better results).-

Résumé (114 tests):
   - * - Maple's  and Diehard's  mt19937 respond exactly the same way when the stream of random
          numbers is read from an ASCII file (8 tests failed (******) and 6 weak (**)).
   - * - Diehard's  mt19937 fails 0 test and is weak on 4 tests when the stream is generated online
 

 

restart:

dir := currentdir():
FromMapleFile     := cat(dir, "Diehard___ALL___Maple_mt19937_N=5e7"):
FromDiehardFile   := cat(dir, "Diehard___ALL___diehard_mt19937_N=5e7"):
FromDiehardNoFile := cat(dir, "Diehard___ALL___Online"):


printf("                           ======================|======================|======================|\n"):
printf("                          |   From Maple's file  | From Diehard's File  | Diehard online test  |\n"):
printf("==========================|======================|======================|======================|\n"):
printf("          test       ntup | p.value   Assessment | p.value   Assessment | p.value   Assessment |\n"):
printf("==========================|======================|======================|======================|\n"):


for k from 1 to 9 do
  LMF  := readline(FromMapleFile):
  LDF  := readline(FromDiehardFile):
  LDNF := readline(FromDiehardNoFile):
end do:


while LMF <> 0 do
  if StringTools:-Search("|", LMF) > 0 then
    res := StringTools:-StringSplit(LMF, "|")[[1, 2, 5, 6]];
    printf("%-20s  %3d | %1.7f ", res[1], parse(res[2]), parse(res[3]));
      if StringTools:-Search("WEAK"  , res[4]) > 0 then printf("    **     |")
    elif StringTools:-Search("FAILED", res[4]) > 0 then printf("  ******   |")
    else printf("  PASSED   |")
    end if:
  end if:
  LMF  := readline(FromMapleFile):

  if StringTools:-Search("|", LDF) > 0 then
    res := StringTools:-StringSplit(LDF, "|")[[5, 6]];
    printf(" %1.7f ", parse(res[1]));
      if StringTools:-Search("  WEAK"  , res[2]) > 0 then printf("     **    |")
    elif StringTools:-Search("  FAILED", res[2]) > 0 then printf("   ******  |")
    else printf("   PASSED  |")
    end if:
  end if:
  LDF  := readline(FromDiehardFile):
                     
  if StringTools:-Search("|", LDNF) > 0 then
    res := StringTools:-StringSplit(LDNF, "|")[[5, 6]];
    printf(" %1.7f ", parse(res[1]));
      if StringTools:-Search("WEAK"  , res[2]) > 0 then printf("     **    |")
    elif StringTools:-Search("FAILED", res[2]) > 0 then printf("   ******    |")
    else printf("   PASSED  |")
    end if:
    printf("\n"):
  end if:
  LDNF := readline(FromDiehardNoFile):


end do:

                           ======================|======================|======================|
                          |   From Maple's file  | From Diehard's File  | Diehard online test  |
==========================|======================|======================|======================|
          test       ntup | p.value   Assessment | p.value   Assessment | p.value   Assessment |
==========================|======================|======================|======================|
   diehard_birthdays    0 | 0.9912651   PASSED   | 0.9912651    PASSED  | 0.8284550    PASSED  |
      diehard_operm5    0 | 0.1802226   PASSED   | 0.1802226    PASSED  | 0.5550587    PASSED  |
  diehard_rank_32x32    0 | 0.3099035   PASSED   | 0.3099035    PASSED  | 0.9575440    PASSED  |
    diehard_rank_6x8    0 | 0.2577249   PASSED   | 0.2577249    PASSED  | 0.3915666    PASSED  |
   diehard_bitstream    0 | 0.5519218   PASSED   | 0.5519218    PASSED  | 0.9999462      **    |
        diehard_opso    0 | 0.1456442   PASSED   | 0.1456442    PASSED  | 0.7906533    PASSED  |
        diehard_oqso    0 | 0.4882425   PASSED   | 0.4882425    PASSED  | 0.9574014    PASSED  |
         diehard_dna    0 | 0.0102880   PASSED   | 0.0102880    PASSED  | 0.5149193    PASSED  |
diehard_count_1s_str    0 | 0.1471956   PASSED   | 0.1471956    PASSED  | 0.9517290    PASSED  |
diehard_count_1s_byt    0 | 0.1158707   PASSED   | 0.1158707    PASSED  | 0.1568255    PASSED  |
 diehard_parking_lot    0 | 0.1148982   PASSED   | 0.1148982    PASSED  | 0.1611173    PASSED  |
    diehard_2dsphere    2 | 0.9122204   PASSED   | 0.9122204    PASSED  | 0.2056657    PASSED  |
    diehard_3dsphere    3 | 0.9385972   PASSED   | 0.9385972    PASSED  | 0.3620517    PASSED  |
     diehard_squeeze    0 | 0.2686977   PASSED   | 0.2686977    PASSED  | 0.8611266    PASSED  |
        diehard_sums    0 | 0.1602355   PASSED   | 0.1602355    PASSED  | 0.5103248    PASSED  |
        diehard_runs    0 | 0.1235328   PASSED   | 0.1235328    PASSED  | 0.9402086    PASSED  |
        diehard_runs    0 | 0.6341956   PASSED   | 0.6341956    PASSED  | 0.3274267    PASSED  |
       diehard_craps    0 | 0.0243605   PASSED   | 0.0243605    PASSED  | 0.1844482    PASSED  |
       diehard_craps    0 | 0.2952043   PASSED   | 0.2952043    PASSED  | 0.1407422    PASSED  |
 marsaglia_tsang_gcd    0 | 0.0000000   ******   | 0.0000000    ******  | 0.5840531    PASSED  |
 marsaglia_tsang_gcd    0 | 0.0000000   ******   | 0.0000000    ******  | 0.8055035    PASSED  |
         sts_monobit    1 | 0.9397218   PASSED   | 0.9397218    PASSED  | 0.9018886    PASSED  |
            sts_runs    2 | 0.8092469   PASSED   | 0.8092469    PASSED  | 0.2247600    PASSED  |
          sts_serial    1 | 0.2902851   PASSED   | 0.2902851    PASSED  | 0.9223063    PASSED  |
          sts_serial    2 | 0.9541680   PASSED   | 0.9541680    PASSED  | 0.6140772    PASSED  |
          sts_serial    3 | 0.4090798   PASSED   | 0.4090798    PASSED  | 0.2334754    PASSED  |
          sts_serial    3 | 0.5474851   PASSED   | 0.5474851    PASSED  | 0.7370361    PASSED  |
          sts_serial    4 | 0.7282286   PASSED   | 0.7282286    PASSED  | 0.2518826    PASSED  |
          sts_serial    4 | 0.9905724   PASSED   | 0.9905724    PASSED  | 0.6876253    PASSED  |
          sts_serial    5 | 0.8297711   PASSED   | 0.8297711    PASSED  | 0.2123014    PASSED  |
          sts_serial    5 | 0.9092172   PASSED   | 0.9092172    PASSED  | 0.3532615    PASSED  |
          sts_serial    6 | 0.4976615   PASSED   | 0.4976615    PASSED  | 0.9967160      **    |
          sts_serial    6 | 0.9853355   PASSED   | 0.9853355    PASSED  | 0.5537414    PASSED  |
          sts_serial    7 | 0.9675717   PASSED   | 0.9675717    PASSED  | 0.3804243    PASSED  |
          sts_serial    7 | 0.4446567   PASSED   | 0.4446567    PASSED  | 0.0923678    PASSED  |
          sts_serial    8 | 0.7254384   PASSED   | 0.7254384    PASSED  | 0.4544030    PASSED  |
          sts_serial    8 | 0.8984816   PASSED   | 0.8984816    PASSED  | 0.7501155    PASSED  |
          sts_serial    9 | 0.8255134   PASSED   | 0.8255134    PASSED  | 0.4260288    PASSED  |
          sts_serial    9 | 0.6609663   PASSED   | 0.6609663    PASSED  | 0.5622308    PASSED  |
          sts_serial   10 | 0.9984397     **     | 0.9984397      **    | 0.5789212    PASSED  |
          sts_serial   10 | 0.7987434   PASSED   | 0.7987434    PASSED  | 0.8599317    PASSED  |
          sts_serial   11 | 0.5552886   PASSED   | 0.5552886    PASSED  | 0.3546752    PASSED  |
          sts_serial   11 | 0.4417852   PASSED   | 0.4417852    PASSED  | 0.5042245    PASSED  |
          sts_serial   12 | 0.3843880   PASSED   | 0.3843880    PASSED  | 0.6723639    PASSED  |
          sts_serial   12 | 0.1514682   PASSED   | 0.1514682    PASSED  | 0.9428701    PASSED  |
          sts_serial   13 | 0.5396454   PASSED   | 0.5396454    PASSED  | 0.5793677    PASSED  |
          sts_serial   13 | 0.9497671   PASSED   | 0.9497671    PASSED  | 0.3370774    PASSED  |
          sts_serial   14 | 0.3616613   PASSED   | 0.3616613    PASSED  | 0.4372343    PASSED  |
          sts_serial   14 | 0.3996251   PASSED   | 0.3996251    PASSED  | 0.5185021    PASSED  |
          sts_serial   15 | 0.3847188   PASSED   | 0.3847188    PASSED  | 0.3188851    PASSED  |
          sts_serial   15 | 0.1012968   PASSED   | 0.1012968    PASSED  | 0.1631942    PASSED  |
          sts_serial   16 | 0.9974802     **     | 0.9974802      **    | 0.6645914    PASSED  |
          sts_serial   16 | 0.1157822   PASSED   | 0.1157822    PASSED  | 0.3465564    PASSED  |
         rgb_bitdist    1 | 0.4705599   PASSED   | 0.4705599    PASSED  | 0.8627740    PASSED  |
         rgb_bitdist    2 | 0.7578920   PASSED   | 0.7578920    PASSED  | 0.3296790    PASSED  |
         rgb_bitdist    3 | 0.9934502   PASSED   | 0.9934502    PASSED  | 0.5558012    PASSED  |
         rgb_bitdist    4 | 0.3674201   PASSED   | 0.3674201    PASSED  | 0.1607977    PASSED  |
         rgb_bitdist    5 | 0.7930273   PASSED   | 0.7930273    PASSED  | 0.9999802      **    |
         rgb_bitdist    6 | 0.8491477   PASSED   | 0.8491477    PASSED  | 0.3774760    PASSED  |
         rgb_bitdist    7 | 0.1537432   PASSED   | 0.1537432    PASSED  | 0.4715169    PASSED  |
         rgb_bitdist    8 | 0.9454030   PASSED   | 0.9454030    PASSED  | 0.9890644    PASSED  |
         rgb_bitdist    9 | 0.2017856   PASSED   | 0.2017856    PASSED  | 0.0571014    PASSED  |
         rgb_bitdist   10 | 0.9989305     **     | 0.9989305      **    | 0.4575834    PASSED  |
         rgb_bitdist   11 | 0.4441883   PASSED   | 0.4441883    PASSED  | 0.4960057    PASSED  |
         rgb_bitdist   12 | 0.7074388   PASSED   | 0.7074388    PASSED  | 0.6808850    PASSED  |
rgb_minimum_distance    2 | 0.9604056   PASSED   | 0.9604056    PASSED  | 0.8859729    PASSED  |
rgb_minimum_distance    3 | 0.5143592   PASSED   | 0.5143592    PASSED  | 0.3266204    PASSED  |
rgb_minimum_distance    4 | 0.3779106   PASSED   | 0.3779106    PASSED  | 0.3537417    PASSED  |
rgb_minimum_distance    5 | 0.4861264   PASSED   | 0.4861264    PASSED  | 0.9032057    PASSED  |
    rgb_permutations    2 | 0.9206310   PASSED   | 0.9206310    PASSED  | 0.8052940    PASSED  |
    rgb_permutations    3 | 0.9299743   PASSED   | 0.9299743    PASSED  | 0.2209750    PASSED  |
    rgb_permutations    4 | 0.8330345   PASSED   | 0.8330345    PASSED  | 0.5819945    PASSED  |
    rgb_permutations    5 | 0.2708879   PASSED   | 0.2708879    PASSED  | 0.9276941    PASSED  |
      rgb_lagged_sum    0 | 0.0794660   PASSED   | 0.0794660    PASSED  | 0.9918681    PASSED  |
      rgb_lagged_sum    1 | 0.5279555   PASSED   | 0.5279555    PASSED  | 0.1304600    PASSED  |
      rgb_lagged_sum    2 | 0.0433872   PASSED   | 0.0433872    PASSED  | 0.1149961    PASSED  |
      rgb_lagged_sum    3 | 0.0028004     **     | 0.0028004      **    | 0.2731577    PASSED  |
      rgb_lagged_sum    4 | 0.0000074     **     | 0.0000074      **    | 0.8978870    PASSED  |
      rgb_lagged_sum    5 | 0.1332411   PASSED   | 0.1332411    PASSED  | 0.2065880    PASSED  |
      rgb_lagged_sum    6 | 0.0412128   PASSED   | 0.0412128    PASSED  | 0.7611867    PASSED  |
      rgb_lagged_sum    7 | 0.0225446   PASSED   | 0.0225446    PASSED  | 0.4810145    PASSED  |
      rgb_lagged_sum    8 | 0.0087433   PASSED   | 0.0087433    PASSED  | 0.3120378    PASSED  |
      rgb_lagged_sum    9 | 0.0000000   ******   | 0.0000000    ******  | 0.1334315    PASSED  |
      rgb_lagged_sum   10 | 0.4147842   PASSED   | 0.4147842    PASSED  | 0.2334790    PASSED  |
      rgb_lagged_sum   11 | 0.0206564   PASSED   | 0.0206564    PASSED  | 0.6491578    PASSED  |
      rgb_lagged_sum   12 | 0.0755835   PASSED   | 0.0755835    PASSED  | 0.5332069    PASSED  |
      rgb_lagged_sum   13 | 0.3112028   PASSED   | 0.3112028    PASSED  | 0.4194447    PASSED  |
      rgb_lagged_sum   14 | 0.0000000   ******   | 0.0000000    ******  | 0.2584573    PASSED  |
      rgb_lagged_sum   15 | 0.0890059   PASSED   | 0.0890059    PASSED  | 0.0007064      **    |
      rgb_lagged_sum   16 | 0.2962076   PASSED   | 0.2962076    PASSED  | 0.1344984    PASSED  |
      rgb_lagged_sum   17 | 0.2696070   PASSED   | 0.2696070    PASSED  | 0.2242021    PASSED  |
      rgb_lagged_sum   18 | 0.0826388   PASSED   | 0.0826388    PASSED  | 0.0450341    PASSED  |
      rgb_lagged_sum   19 | 0.0000000   ******   | 0.0000000    ******  | 0.5508302    PASSED  |
      rgb_lagged_sum   20 | 0.0101437   PASSED   | 0.0101437    PASSED  | 0.4290150    PASSED  |
      rgb_lagged_sum   21 | 0.1417859   PASSED   | 0.1417859    PASSED  | 0.1624411    PASSED  |
      rgb_lagged_sum   22 | 0.0160264   PASSED   | 0.0160264    PASSED  | 0.5204838    PASSED  |
      rgb_lagged_sum   23 | 0.0535167   PASSED   | 0.0535167    PASSED  | 0.6571892    PASSED  |
      rgb_lagged_sum   24 | 0.0000000   ******   | 0.0000000    ******  | 0.8578906    PASSED  |
      rgb_lagged_sum   25 | 0.8453426   PASSED   | 0.8453426    PASSED  | 0.3568988    PASSED  |
      rgb_lagged_sum   26 | 0.2113484   PASSED   | 0.2113484    PASSED  | 0.9755715    PASSED  |
      rgb_lagged_sum   27 | 0.1903762   PASSED   | 0.1903762    PASSED  | 0.4356739    PASSED  |
      rgb_lagged_sum   28 | 0.0733066   PASSED   | 0.0733066    PASSED  | 0.8354990    PASSED  |
      rgb_lagged_sum   29 | 0.0000000   ******   | 0.0000000    ******  | 0.1716599    PASSED  |
      rgb_lagged_sum   30 | 0.0932124   PASSED   | 0.0932124    PASSED  | 0.0732090    PASSED  |
      rgb_lagged_sum   31 | 0.0000000   ******   | 0.0000000    ******  | 0.3497910    PASSED  |
      rgb_lagged_sum   32 | 0.0843455   PASSED   | 0.0843455    PASSED  | 0.5441949    PASSED  |
     rgb_kstest_test    0 | 0.4399862   PASSED   | 0.4399862    PASSED  | 0.9766581    PASSED  |
     dab_bytedistrib    0 | 0.0748312   PASSED   | 0.0748312    PASSED  | 0.7035800    PASSED  |
             dab_dct  256 | 0.0919474   PASSED   | 0.0919474    PASSED  | 0.3985889    PASSED  |
        dab_filltree   32 | 0.1227533   PASSED   | 0.1227533    PASSED  | 0.7390925    PASSED  |
        dab_filltree   32 | 0.6819630   PASSED   | 0.6819630    PASSED  | 0.1773611    PASSED  |
       dab_filltree2    0 | 0.1774773   PASSED   | 0.1774773    PASSED  | 0.2088828    PASSED  |
       dab_filltree2    1 | 0.1718216   PASSED   | 0.1718216    PASSED  | 0.2257006    PASSED  |
        dab_monobit2   12 | 0.9999881     **     | 0.9999881      **    | 0.8084149    PASSED  |

 

 


 

Download DIEHARD_test_of_MAPLE_MersenneTwister.mw

A lot of supplementary details are given in the attached file.
I let the readers discover by themselves if Maple's implementation of the Mersenne Twister PRNG is correct or not.
Beyond this exercise, I hope this work will be useful to people who could be tempted to test their own generator.

 

 

In the applications I am working on, the information are often represented by hierarchical tables (that is tables where some entries can also be tables, and so on).
To help people to understand how this information is organized, I have thought to representent this hierarchical table as a tree graph.
Once this graph built, it becomes very simple to find where a "terminal leaf", that is en entry which is no longer a table, is located in the original table (by location I mean the sequence of indices for which the entry is this "terminal leaf".

The code provided here is pretension free and I do not doubt a single second  that people here will be able to improve it.
I published it for i thought other people could face the same kind of problems that I do.


 

restart

with(GraphTheory):
interface(version);

`Standard Worksheet Interface, Maple 2015.2, Mac OS X, December 21 2015 Build ID 1097895`

(1)

gh := proc(T)
  global s, counter, types:
  local  i:
  if type(T, table) then
    for i in [indices(T, nolist)] do
      if type(T[i], table) then
         s := s, op(map(u -> [i, u], [indices(T[i], nolist)] ));
      else
         counter := counter+1:
         types   := types, _Z_||counter = whattype(T[i]);
         s       := s, [i, _Z_||counter];
      end if:
      thisproc(T[i]):
    end do:
  else
    return s
  end if:
end proc:

t := table([a1=[alpha=1, beta=2], a2=table([a21=2, a22=table([a221=x, a222=table([a2221={1, 2, 3}, a2222=Matrix(2, 2), a2223=u3, a2224=u4])])]), a3=table([a31=u, a32=v])]);

global s, counter, types:
s       := NULL:
counter := 0:
types   := NULL:

ghres := gh(t):
types := [types]:

t := table([a1 = [alpha = 1, beta = 2], a3 = table([a32 = v, a31 = u]), a2 = table([a22 = table([a222 = table([a2222 = (Matrix(2, 2, {(1, 1) = 0, (1, 2) = 0, (2, 1) = 0, (2, 2) = 0})), a2223 = u3, a2221 = {1, 2, 3}, a2224 = u4]), a221 = x]), a21 = 2])])

(2)


These 3 lines determine the set of edges of the form ['t', v], that are not been captured by procedure h.
They correspond to "first level" indices of table t (v in {a1, a2, a3} in the example above)

L := convert(op~(1, [ghres]), set):     
R := convert(op~(2, [ghres]), set):
FirstLevelEdges := map(u -> ['t', u], L union R minus R):


Complete the set of the edges, build the graph representation TG of table t and draw TG.

edges := convert~({ghres, FirstLevelEdges[]}, set):
TG := Graph(edges):

HighlightVertex(TG, Vertices(TG), white):
p := DrawGraph(TG, style=tree, root='t'):
 


The first line is used to change the the "terminal leaves" of names  _Z_n by their type.

eval(t);

p       := subs(types, p):
enlarge := plottools:-transform((x,y) -> [3*x, y]):

plots:-display(enlarge(p), size=[1000, 400]);

table([a1 = [alpha = 1, beta = 2], a3 = table([a32 = v, a31 = u]), a2 = table([a22 = table([a222 = table([a2222 = (Matrix(2, 2, {(1, 1) = 0, (1, 2) = 0, (2, 1) = 0, (2, 2) = 0})), a2223 = u3, a2221 = {1, 2, 3}, a2224 = u4]), a221 = x]), a21 = 2])])

 

 


This procedure is used to find the "indices path" to a terminal leaf.
FindLeaf is then applied to all the terminal leaves.

FindLeaf := proc(TG, leaf)
   local here:
   here := GraphTheory:-ShortestPath(TG, 't', leaf)[1..-2]:
   here := cat(convert(here[1], string), convert(here[2..-1], string)):
   here := StringTools:-SubstituteAll(here, ",", "]["):
   here := parse(here);
end proc:

# where is a2221

printf("%a\n", FindLeaf(TG, a2221));

t[a2][a22][a222]

 

 


 

Download Table_Unfolding_2.mw

 

1 2 Page 1 of 2