Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem I. 266. (April 2011)

I. 266. Many computer programs use the special case of the linear congruence method to generate ``random numbers''.

Suppose we are given k integers (a1,a2,...,ak), being the coefficients of the congruence. We are also give k initial values (R1,R2,...,Rk). The next pseudo random number is then defined recursively according to the formula R_{n+1} =\big(a_1 \cdot
R_{n-k+1} +a_2 \cdot R_{n-k+2} +\dots +a_k \cdot R_n \big) \bmod M. It is a natural expectation that the generated pseudo random integers sooner or later attain every possible value and we should not be able to guess the next term of the sequence based on the previous terms.

By using a spreadsheet application and the linear congruence method above, create 1000 pseudo random numbers and compare them with the random numbers generated by the spreadsheet application. Use the value k=10 (being the length of the coefficient vector, and the initial value vector). Use M=50 (hence the pseudo random integers are distributed in the interval [0,49]). Use the columns A:K to generate the random numbers. The coefficients and initial values should be put in the first row. These numbers are arbitrary two-digit integers specified by us.

In order to do the comparison, first use the random numbers in column K with references and make pairs in the column N:O. Then, by interpreting these as coordinate pairs, graph them on a PointXY diagram. This diagram should not contain any legend and the points should fill in the available space. The other column P:Q for the comparison should consist of similar pairs of random numbers obtained by the built-in random number generator of the spreadsheet application. These numbers should be graphed on a similar but different diagram.

As a second method for the comparison, you should count how many times each number occurs. This should be done to the right of column Q: first by using your random numbers, then in a different column, the random numbers of the spreadsheet application. You should sort these occurrences into ascending order and plot them together on a column chart. Correct results should appear even if the sheet is recomputed.

Your spreadsheet (i266.xls, i266.ods, ...) should be submitted in a compressed file (i266.zip) together with a short documentation (i266.txt, i266.pdf, ...) also containing the name and version number of your spreadsheet application and a brief description of your solution.

(10 pont)

Deadline expired on May 10, 2011.


Sorry, the solution is available only in Hungarian. Google translation

Megoldásokról

Összességében a beküldött megoldások jól sikerültek. A feladat könnyűnek mutatkozott. Sajnos kevés munka érkezett. A legtöbb gondot az álvéletlenszámokból a koordináta számpárok előállítása okozta.

Ha M3 cellától lefelé, 1-től kezdve sorszámokat állítunk elő, akkor egy lehetséges megoldás

N3: =INDEX($K$3:$K$10000;M3*2;1) és

O3: =INDEX($K$3:$K$10000;M3*2+1;1)

Minta megoldás: linkong.xls


Statistics:

4 students sent a solution.
10 points:Barta 111 János, Gema Barnabás, Leitereg András.
9 points:Szabó 928 Attila.

Problems in Information Technology of KöMaL, April 2011