Tomasevic et al 2019a - Revision history

Rimni: /* 4. Simulation results */

2021-05-28T12:42:58Z

‎4. Simulation results

Rimni at 12:36, 28 May 2021

2021-05-28T12:36:11Z

Rimni at 12:34, 28 May 2021

2021-05-28T12:34:31Z

Rimni: /* 2. Problem statement */

2021-05-28T12:34:02Z

‎2. Problem statement

Rimni at 10:39, 23 April 2020

2020-04-23T10:39:14Z

Rimni at 10:16, 23 April 2020

2020-04-23T10:16:10Z

Show changes

Rimni at 14:41, 22 April 2020

2020-04-22T14:41:18Z

Rimni at 14:07, 22 April 2020

2020-04-22T14:07:38Z

Rimni at 14:03, 22 April 2020

2020-04-22T14:03:10Z

Rimni at 13:53, 22 April 2020

2020-04-22T13:53:11Z

@@ Line 425: / Line 425: @@
 ==4. Simulation results==
-Theoretical finding of the analytical approach conducted in the previuos section is also verified by means of software simulation. An appropriate program that simulates the procedure of random number generation elaborated in Section 2 is implemented. Random number generator from [11] is exploited in this simulation. For keeping the record of randomly numbers generated so far (implementation of set <math>I</math>) a structure called ''interval tree'' is used. It is a modification of standard binary search tree [12], whose nodes correspond to <math>I</math> –intervals instead of single values. An example of such a tree is given in Figure 4.
+Theoretical finding of the analytical approach conducted in the previuos section is also verified by means of software simulation. An appropriate program that simulates the procedure of random number generation elaborated in Section 2 is implemented. Random number generator from [11] is exploited in this simulation. For keeping the record of randomly numbers generated so far (implementation of set <math>I</math>) a structure called ''interval tree'' is used. It is a modification of standard binary search tree [12], whose nodes correspond to <math>I</math> –intervals instead of single values. An example of such a tree is given in [[#img-4|Figure 4]].
+<div id='img-4'></div>
 {| style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: auto;max-width: auto;"
 |-
@@ Line 437: / Line 437: @@
 Each node has two integer fields for lower and upper bounds of the corresponding interval and two pointer fields to its left and right subtrees, so memory consumed is <math>O</math>(<math>M</math>) where <math>M</math> is the maximum number of nodes (<math>I</math> –intervals). All intervals in the left subtree are lower, while the intervals in the right subtree are higher, so an efficient binary search is possible with average time complexity of <math>O</math>(log <math>M</math>) [12].
-The experimental results are presented in Table 1. The size of random number range (<math>N</math> – first column) is varied from 100 to 10000000. For each value of <math>N</math>, the results are averaged over 10 experiments. Theoretically expected number of <math>I</math> – intervals is calculated from analytical model as <math display="inline">M_a=\frac{({N+1})^{2}}{4N}</math>and given in the second column. The statistics about the maximum number of nodes (<math>I</math> – intervals) in the interval tree is collected (<math>M_s</math> – third column). Fourth column shows a relative difference between the results of analytical and simulation models calculated as <math>d_m = abs (( M_{a}-M_{s}) / M_{a}) </math>. As this difference decreases with <math>N</math> and become negligible, it is evident that the results of analytical model perfectly match the experimental results. Also, the number of generated values included into tree when the number of nodes reaches the maximum <math>M</math> is also kept (<math>P</math> – fifth column). Then, an average size of an <math>I</math> – interval is calculated as <math>l_{avg} =  P/ M_s</math> (sixth column).
+The experimental results are presented in [[#tab-1|Table 1]]. The size of random number range (<math>N</math> – first column) is varied from 100 to 10000000. For each value of <math>N</math>, the results are averaged over 10 experiments. Theoretically expected number of <math>I</math> – intervals is calculated from analytical model as <math display="inline">M_a=\frac{({N+1})^{2}}{4N}</math>and given in the second column. The statistics about the maximum number of nodes (<math>I</math> – intervals) in the interval tree is collected (<math>M_s</math> – third column). Fourth column shows a relative difference between the results of analytical and simulation models calculated as <math>d_m = abs (( M_{a}-M_{s}) / M_{a}) </math>. As this difference decreases with <math>N</math> and become negligible, it is evident that the results of analytical model perfectly match the experimental results. Also, the number of generated values included into tree when the number of nodes reaches the maximum <math>M</math> is also kept (<math>P</math> – fifth column). Then, an average size of an <math>I</math> – interval is calculated as <math>l_{avg} =  P/ M_s</math> (sixth column).
 <div class="center" style="font-size: 75%;">
 '''Table 1'''. Experimental results</div>
 {| style="margin: 1em auto 0.1em auto;border-collapse: collapse;font-size:85%;width:60%;"
 |-

@@ Line 106: / Line 106: @@
 |}
-In a given step, these probabilities depend on current positions of <math>I</math>–intervals of used numbers within range <math>R</math>. Three possible layouts of range <math>R</math> are shown in Figure 2. <math>I</math>–intervals are sequenced from 1 to <math>r_i</math> and again represented by shaded boxes, while intervening <math>S</math>–intervals of unused numbers are represented by white boxes.
+In a given step, these probabilities depend on current positions of <math>I</math>–intervals of used numbers within range <math>R</math>. Three possible layouts of range <math>R</math> are shown in [[#img-2|Figure 2]]. <math>I</math>–intervals are sequenced from 1 to <math>r_i</math> and again represented by shaded boxes, while intervening <math>S</math>–intervals of unused numbers are represented by white boxes.
 {| style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: auto;max-width: auto;"
 |-
@@ Line 400: / Line 401: @@
-Let <math display="inline">f(i)={r}_{i+1}</math>. The average number of <math>I</math>–intervals as a function of current number of steps <math>i</math> is shown in Figure 3. First and second derivation of this function are
+Let <math display="inline">f(i)={r}_{i+1}</math>. The average number of <math>I</math>–intervals as a function of current number of steps <math>i</math> is shown in [[#img-3|Figure 3]]. First and second derivation of this function are
 <div class="auto" style="text-align: center;">
@@ Line 414: / Line 415: @@
 For <math>N \gg 1</math> it gives <math>M\approx N/4</math> which represents the solution of the stated problem.
 {| style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: auto;max-width: auto;"
 |-

@@ Line 56: / Line 56: @@
 For the sake of clarity of the following presentation and analysis, during the process of random generation we will maintain two sets. The record of numbers generated so far is kept as a set of integers (denoted as <math>I</math>). In order to save the space, it is implemented in an appropriate form of intervals of consecutive integers. These intervals of already used numbers will be referred as <math>I</math>–intervals. The remaining numbers from <math>R</math> are kept in a set of unused integers (denoted as <math>S</math>), also implemented in the form of intervals (<math>S</math>–intervals). In both set implementations, only lower and upper bound for each interval are recorded in memory. The interval can have only one element, referred to as ''single element interval'' (e.g., <math>[a, a]</math>), or more than one element, referred to as ''multiple element interval'' (e.g., [<math>a</math>, <math>b</math>], <math>a < b</math>). Since <math>S</math> and <math>I</math> sets are complements in respect to set <math>R</math> (i.e., <math> S+I=R</math>), in practical implementation it is sufficient to maintain only one of these sets for memory efficiency. [[#img-1|Figure 1]] illustrates alternating layout of  <math>I</math>–intervals and <math>S</math>–intervals within the set <math>R</math>. Used numbers are denoted as circles and <math>I</math>–intervals are represented as shaded boxes, while unused numbers are denoted with squares and <math>S</math>–intervals are represented as white boxes.
 {| style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: auto;max-width: auto;"
 |-

@@ Line 54: / Line 54: @@
 Let the random number generator (RNG) generates integers from the given range <math>[1\cdots N] </math> (denoted as set <math>R</math>) long enough to guarantee that each number from <math>R</math> appears at least once. After RNG generates a number, the check is made if this number is already generated before. If not, it is used in application and some record of numbers generated so far is updated; otherwise, RNG generates a new number. The process is carried on until all numbers from <math>R</math> are generated and included into the record.
-For the sake of clarity of the following presentation and analysis, during the process of random generation we will maintain two sets. The record of numbers generated so far is kept as a set of integers (denoted as <math>I</math>). In order to save the space, it is implemented in an appropriate form of intervals of consecutive integers. These intervals of already used numbers will be referred as <math>I</math>–intervals. The remaining numbers from <math>R</math> are kept in a set of unused integers (denoted as <math>S</math>), also implemented in the form of intervals (<math>S</math>–intervals). In both set implementations, only lower and upper bound for each interval are recorded in memory. The interval can have only one element, referred to as ''single element interval'' (e.g., <math>[a, a]</math>), or more than one element, referred to as ''multiple element interval'' (e.g., [<math>a</math>, <math>b</math>], <math>a < b</math>). Since <math>S</math> and <math>I</math> sets are complements in respect to set <math>R</math> (i.e., <math> S+I=R</math>), in practical implementation it is sufficient to maintain only one of these sets for memory efficiency. Figure 1 illustrates alternating layout of  <math>I</math>–intervals and <math>S</math>–intervals within the set <math>R</math>. Used numbers are denoted as circles and <math>I</math>–intervals are represented as shaded boxes, while unused numbers are denoted with squares and <math>S</math>–intervals are represented as white boxes.
+For the sake of clarity of the following presentation and analysis, during the process of random generation we will maintain two sets. The record of numbers generated so far is kept as a set of integers (denoted as <math>I</math>). In order to save the space, it is implemented in an appropriate form of intervals of consecutive integers. These intervals of already used numbers will be referred as <math>I</math>–intervals. The remaining numbers from <math>R</math> are kept in a set of unused integers (denoted as <math>S</math>), also implemented in the form of intervals (<math>S</math>–intervals). In both set implementations, only lower and upper bound for each interval are recorded in memory. The interval can have only one element, referred to as ''single element interval'' (e.g., <math>[a, a]</math>), or more than one element, referred to as ''multiple element interval'' (e.g., [<math>a</math>, <math>b</math>], <math>a < b</math>). Since <math>S</math> and <math>I</math> sets are complements in respect to set <math>R</math> (i.e., <math> S+I=R</math>), in practical implementation it is sufficient to maintain only one of these sets for memory efficiency. [[#img-1|Figure 1]] illustrates alternating layout of  <math>I</math>–intervals and <math>S</math>–intervals within the set <math>R</math>. Used numbers are denoted as circles and <math>I</math>–intervals are represented as shaded boxes, while unused numbers are denoted with squares and <math>S</math>–intervals are represented as white boxes.
 {| style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: auto;max-width: auto;"

@@ Line 505: / Line 505: @@
 <div class="auto" style="text-align: left;width: auto; margin-left: auto; margin-right: auto;font-size: 85%;">
-[1]	Knuth, D. The Art of computer programming, 3rd ed. Vol. 2: Seminumerical Algorithms, Addison Wesley, 1997.
+[1]	Knuth, D. The Art of computer programming. 3rd ed. Vol. 2: Seminumerical Algorithms, Addison Wesley, 1997.
 [2]	Zaman S.U., Ghosh R. Review on fifteen statistical tests proposed by NIST. J. of Theor. Phys. and Cryptogr., 1:18-31, 2012.

@@ Line 90: / Line 90: @@
 ==3. Analytical solution==
-Let us assume that in step <math>t = i</math>, <math>1 \leq i \leq N</math>, an element <math>x_i</math> is chosen from ''S'' and moved to ''I''. After that, the number of elements in ''S'' is <math> N - i </math>. Let the number of ''I''–intervals after adding <math>x_i</math> to ''I ''be denoted as <math>r_i</math>. In the next step <math>t = i + 1</math>, <math>i\neq N</math>, an element <math>x_{i+1}</math> is chosen from ''S.'' As previosly elaborated, its inclusion into ''I'' can lead to:
+Let us assume that in step <math>t = i</math>, <math>1 \leq i \leq N</math>, an element <math>x_i</math> is chosen from ''S'' and moved to <math>I</math>. After that, the number of elements in ''S'' is <math> N - i </math>. Let the number of ''I''–intervals after adding <math>x_i</math> to ''I ''be denoted as <math>r_i</math>. In the next step <math>t = i + 1</math>, <math>i\neq N</math>, an element <math>x_{i+1}</math> is chosen from ''S.'' As previosly elaborated, its inclusion into ''I'' can lead to:
 :* decreased number of ''I''–intervals - <math>r_i -1</math> (merging of two intervals),

@@ Line 72: / Line 72: @@
 :1. if it is not adjacent to any of existing <math>I</math>–intervals, a new <math>I</math>–interval  <math>[x_i, x_i]</math> is created,
-:2. if it is adjacent to only one interval [<math>a, b]</math>, this <math>I</math>–interval is extended with <math>x_i</math> (e.g., if <math>x_i  = a – 1</math>, interval <math>[a, b]</math> is extended to <math>[x_i, b]</math> or if <math>x_i = b + 1</math>, interval <math>[a, b]</math> is extended to <math>[a, x_i]</math>),
+:2. if it is adjacent to only one interval [<math>a, b]</math>, this <math>I</math>–interval is extended with <math>x_i</math> (e.g., if <math>x_i = a-1</math>, interval <math>[a, b]</math> is extended to <math>[x_i, b]</math> or if <math>x_i = b + 1</math>, interval <math>[a, b]</math> is extended to <math>[a, x_i]</math>),
 :3. if it is adjacent to two <math>I</math>–intervals <math>[a, b]</math> and <math>[c, d]</math> in a way that <math>x_i = b + 1</math> and <math>x_i = c - 1</math>, these two intervals are merged into interval <math>[a, d]</math> (<math>x_i</math> previously corresponded to a single element <math>S</math>–interval).

@@ Line 72: / Line 72: @@
 :1. if it is not adjacent to any of existing <math>I</math>–intervals, a new <math>I</math>–interval  <math>[x_i, x_i]</math> is created,
-:2. if it is adjacent to only one interval [<math>a, b]</math>, this <math>I</math>–interval is extended with <math>x_i</math> <br/>(e.g., if ''x<sub>i</sub>''  = ''a ''– 1, interval [''a'', ''b''] is extended to [''x<sub>i</sub>'', ''b'']<br/>or if ''x<sub>i</sub>'' = ''b ''+ 1, interval [''a'', ''b''] is extended to [''a'', ''x<sub>i</sub>'']),
+:2. if it is adjacent to only one interval [<math>a, b]</math>, this <math>I</math>–interval is extended with <math>x_i</math> (e.g., if <math>x_i  = a – 1</math>, interval <math>[a, b]</math> is extended to <math>[x_i, b]</math> or if <math>x_i = b + 1</math>, interval <math>[a, b]</math> is extended to <math>[a, x_i]</math>),
-:3. if it is adjacent to two ''I''–intervals [''a'', ''b''] and [''c'', ''d''] in a way that ''x<sub>i</sub>'' = ''b ''+ 1 and ''x<sub>i</sub>'' = ''c ''– 1, these two intervals are merged into interval [''a'', ''d''] (''x<sub>i</sub>'' previously corresponded to a single element ''S''–interval).
+:3. if it is adjacent to two <math>I</math>–intervals <math>[a, b]</math> and <math>[c, d]</math> in a way that <math>x_i = b + 1</math> and <math>x_i = c - 1</math>, these two intervals are merged into interval <math>[a, d]</math> (<math>x_i</math> previously corresponded to a single element <math>S</math>–interval).
-Obviously, after an element ''x<sub>i</sub>'' is included into ''I'', three outcomes are possible in a step:
+Obviously, after an element <math>x_i</math> is included into <math>I</math>, three outcomes are possible in a step:
-:* number of ''I''–intervals is increased by 1 (cases A and B.1),
+:* number of <math>I</math>–intervals is increased by 1 (cases A and B.1),
-:* number of ''I''–intervals stays the same (case B.2),
+:* number of <math>I</math>–intervals stays the same (case B.2),
-:* number of ''I''–intervals is decreased by 1 (case B.3).
+:* number of <math>I</math>–intervals is decreased by 1 (case B.3).
-In step ''t'' = 1, the number of ''I''–intervals is 1. Then, it increases until some maximum ''M'' is reached as new ''I''–intervals are created''. ''After reaching maximum, it is expected that ''I''–intervals are progessively coalescing, and their number will fall until only one interval, [1, ''N''], remains in step ''t'' = ''N'' (all elements from ''S'' are now moved to ''I'', ''S'' = Ø'' ''and ''I'' = ''R'').
+In step <math>t = 1</math>, the number of <math>I</math>–intervals is 1. Then, it increases until some maximum <math>M</math> is reached as new <math>I</math>–intervals are created. After reaching maximum, it is expected that <math>I</math>–intervals are progessively coalescing, and their number will fall until only one interval, [1, <math>N</math>], remains in step <math>t = N</math> (all elements from <math>S</math> are now moved to <math>I</math>, <math>S=\O</math>  and <math>I= R</math>).
-For practical viability of this procedure, one of the crucial things is the memory needed for keeping the record of generated elements in set ''I'' (and also of unused elements in ''S''). Memory requirements are directly proportional to ''M ''since ''I ''can be implemented as a dynamic structure in which only upper and lower bound of each interval are recorded, as it will be explained in Section 4. In the following sections, the maximum number of ''I''–intervals ''M ''is determined by both analytical and simulation means.
+For practical viability of this procedure, one of the crucial things is the memory needed for keeping the record of generated elements in set <math>I</math> (and also of unused elements in <math>S</math>). Memory requirements are directly proportional to <math>M</math> since <math>I</math> can be implemented as a dynamic structure in which only upper and lower bound of each interval are recorded, as it will be explained in Section 4. In the following sections, the maximum number of <math>I</math>–intervals <math>M</math> is determined by both analytical and simulation means.
 ==3. Analytical solution==

@@ Line 66: / Line 66: @@
 Let we start with set of integers <math>S = \left\{x | 1 \leq x \leq N\right\}</math> (i.e., <math>S = R</math>) and an empty set <math>I = \O</math>. In each step, we randomly choose an element <math>x_i</math> from <math>S</math> and move it to <math>I</math>; i.e., <math>S=S-[x_i]</math> and <math>I=I+[x_i]</math>. Consequently, after <math>N</math> steps we will have <math>S = \O</math> and <math>I = R</math>. In each step, the record of numbers already chosen and included into <math>I</math> is updated in the following way:
-:A. In step <math>t = 1</math>, an element <math>x_1 \in \epsilon  S</math>  is randomly chosen and included into <math>I</math>. Now, there is only one <math>I</math>-interval, [<math>x_1</math>, <math>x_1</math>].
+:A. In step <math>t = 1</math>, an element <math>x_1 \in   S</math>  is randomly chosen and included into <math>I</math>. Now, there is only one <math>I</math>-interval, [<math>x_1</math>, <math>x_1</math>].
 :B. In step <math>t = i,  2 \le i \le N</math>, currently randomly chosen element <math>x_i \in S</math> is checked for adjacency to existing <math>I</math>–intervals with three possible outcomes: