Matematické Fórum

Witiko · 27. 08. 2011 11:54 — Editoval Witiko (27. 08. 2011 12:11)

Dobrý den. Mějme algoritmus, který při konstantách a, b a m navrací m-dlouhou sekvenci pseudonáhodných čísel v intervalu (0; 1).
$f(x) : ((ax + b) mod m) / m\nl{}\{a; b; m; x\} \matsymb{in} N\nl{}\{a; b\} < m$

Zajímalo by mě, jak zvolit konstanty tak, abych zajistil, že při libovolném x nebude (ax + b) dělitelné m. V opačném případě by totiž algoritmus mohl navrátit 0, což není kýžené.

FailED · 27. 08. 2011 12:34

b nesmí být násobkem GCD(a,m)

(GCD je největší společný dělitel)

Witiko · 28. 08. 2011 15:55 — Editoval Witiko (28. 08. 2011 15:57)

Díky za odpověď. Zdá se, že tomu nejspíš tak bude, ačkoliv se mi nedaří reprodukovat myšlenkové pochody, kterými jsi k tomu došel (s hledáním využití GCD a LCM jsem měl vždy problém). Každopádně většinou jsou v generátorech pseudonáhodného šumu jako konstanty a a m volena velká prvočísla, jejichž GCD je 1. Tzn. standardem nejspíš bude, že navracená čísla jsou v intervalu <0; 1).

FailED · 28. 08. 2011 16:21 — Editoval FailED (28. 08. 2011 21:14)

Přesně tak, jde o to, že rovnice $ax+b\equiv 0\pmod {m}$ má pro a, m nesoudělná vždycky řešení.

Kdyby existovala taková dvě $x_{1,2},\quad |x_2-x_1|<m,\quad ax_1+b\equiv ax_2+b \pmod {m}$ , bylo by $(ax_1+b)-(ax_2+b)=a(x_1-x_2)$ dělitelné m a tedy $x_1-x_2$ dělitelné m - tedy nutně $x_1=x_2$ . Proto když vezmeme m po sobě jdoucích x, proběhne ax+b všechny možné zbytky po dělení m.

Podobně to funguje pro soudělná a, m; (ax+b) mod m potom "obskáče" všechny zbytky dělitelné GCD(a,m).

Witiko · 29. 08. 2011 23:52 — Editoval Witiko (30. 08. 2011 00:15)

↑ FailED:: Nejedná se o Tvojí chybu, ale modulární aritmetika a kongruence není součástí středoškolského učiva, což mi znemožňuje Tvé vysvětlení v celistvosti pochopit. Pokusím se do toho ale proniknout. :-)

Edit: Ok, mám základní průpravu, tzn. $a(x_1 - x_2)\equiv 0\pmod {m}$ implikuje pravdivost $x_1 - x_2\equiv 0\pmod {m}$ jelikož a a m jsou nesoudělné a proto musí být částí dělitelnou m $x_1 - x_2$ , že?

FailED · 30. 08. 2011 20:42

ano

Witiko · 30. 08. 2011 21:17

Děkuju za trpělivost. :-)

Matematické Fórum

#1 27. 08. 2011 11:54 — Editoval Witiko (27. 08. 2011 12:11)

Generátor pseudonáhodných čísel

#2 27. 08. 2011 12:34

Re: Generátor pseudonáhodných čísel

#3 28. 08. 2011 15:55 — Editoval Witiko (28. 08. 2011 15:57)

Re: Generátor pseudonáhodných čísel

#4 28. 08. 2011 16:21 — Editoval FailED (28. 08. 2011 21:14)

Re: Generátor pseudonáhodných čísel

#5 29. 08. 2011 23:52 — Editoval Witiko (30. 08. 2011 00:15)

Re: Generátor pseudonáhodných čísel

#6 30. 08. 2011 20:42

Re: Generátor pseudonáhodných čísel

#7 30. 08. 2011 21:17

Re: Generátor pseudonáhodných čísel

Zápatí