DEMO.DESIGN
Frequently Asked Questions
 
оглавление | demo party в ex-СССР | infused bytes e-mag | новости от ib/news | другие проекты | письмо | win koi lat

следующий фpагмент (2)
- [56] Algorithms.. (2:5030/84) -------------------------------- RU.ALGORITHMS - Msg : 118 of 118 From : Alexey Kosenkov 2:5030/444.4 15 Jan 97 14:15:00 To : All Subj : Алгоpитмы фоpмиpования с.в. с заданным законом pаспpеделения -------------------------------------------------------------------------------- Dear All! Большинство алгоpитмов данного модyля были полyчены методом обpащения фyнкции pаспpеделения. === Cut === {********************************************************************} {* Генераторы случайных чисел с заданным законом распределения *} {* А.М.Косенков, 2:5030/444.4@FidoNet. *} {********************************************************************} UNIT Rand_Gen; INTERFACE Type TFloat = Extended; Const Eps_Float = 5.0e-0017; Function Rand(A, B : TFloat) : TFloat; Function Norm1_Rand : TFloat; Function Norm2_Rand : TFloat; Function LogNorm_Rand(M, S : TFloat) : TFloat; Function X2_Rand(V : Byte) : TFloat; Function Gamma_Rand(B, C : TFloat) : TFloat; Function Beta_Rand(V, M : TFloat) : TFloat; Function Veyb_Rand(C, B : TFloat) : TFloat; Function Nak_Rand(M, S : TFloat) : TFloat; Function Rays_Rand(A, S : TFloat) : TFloat; Function Re_Rand(S : TFloat) : TFloat; Function Simp_Rand(A, B : TFloat) : TFloat; Function Bern_Rand(P : TFloat) : Byte; Function Binom_Rand(P : tFloat; N : Integer) : Integer; IMPLEMENTATION {* Вещественная степень Y вещественного числа X, (X^Y) *} Function PowFF(x, y : TFloat) : TFloat; Begin IF x<0 Then PowFF:=Cos(2.0*Pi*Frac(0.5*y))*Exp(y*Ln(Abs(x))) Else IF x=0 Then PowFF:=0 Else PowFF:=Exp(y*Ln(x)) End; {********************************************************************} {* Функция Rand. *} {* Генератор равномерно распределенных случайных чисел. *} {* *} {* p(x) = 1/(b - a) , (a < x < b). *} {********************************************************************} Function Rand(A, B : TFloat) : tFloat; Begin Rand:=A + (B - A)*Random; End; {********************************************************************} {* Функция Norm1_Rand. *} {* Генератор нормально распределенных случайных чисел. *} {* -1/2 *} {* p(x) = (2•pi) • Exp(-x¤/2), (-$ < x < $). *} {********************************************************************} Function Norm1_Rand : TFloat; CONST F_S : Boolean = TRUE; Norm2 : TFloat = 0.0; Var R, Phi: TFloat; Begin If F_S Then Begin R:=Sqrt(Abs(2.0*Ln(Random))); Phi:=2.0*PI*Random; Norm1_Rand:=R*Cos(Phi); Norm2:=R*Sin(Phi); End Else Norm1_Rand:=Norm2; F_S:=not F_S; End; {********************************************************************} {* Функция Norm2_Rand. *} {* Генератор нормально распределенных случайных чисел. *} {* -1/2 *} {* p(x) = (2•pi) • Exp(-x¤/2), (-$ < x < $). *} {********************************************************************} Function Norm2_Rand : TFloat; Const F_S : Boolean = TRUE; Norm2 : tFloat = 0.0; Var V1, V2, S, R : tFloat; Begin IF F_S Then Begin Repeat V1:=2.0*Random - 1.0; V2:=2.0*Random - 1.0; S:=Sqr(V1) + Sqr(V2); Until S < 1.0; R:=Sqrt(Abs(2.0*Ln(S)/S)); Norm2_Rand:=R*V1; Norm2:=R*V2; End Else Norm2_Rand:=Norm2; F_S:=not F_S; End; {********************************************************************} {* Функция LogNorm_Rand. *} {* Генератор логнормально распределенных случайных чисел. *} {* -1/2 *} {* (2•pi) - ln¤(x/m) ¬ *} {* p(x) = -------- • Exp¦- -------- ¦ , (x>0, m>0, s>0). *} {* x•s L 2•s¤ - *} {********************************************************************} Function LogNorm_Rand(M, S : TFloat) : TFloat; Begin LogNorm_Rand:=M*Exp(S*Norm2_Rand); End; {********************************************************************} {* Функция X2_Rand. *} {* Генератор случайных чисел, распределенных по закону хи-квадрат. *} {* *} {* (v-2)/2 v/2 *} {* p(x) = x • Exp[-x¤/2] / [2 • Г(v/2)], *} {* (x>0, v-положительное целое). *} {********************************************************************} Function X2_Rand(V : Byte) : TFloat; Var I : Integer; S : TFloat; Begin S:=1; If odd(V) Then Begin For i:=0 To (V-1) div 2 Do S:=S*Random; X2_Rand:=-2.0*Ln(S) + Sqr(Norm2_Rand); End Else Begin For i:=0 To V div 2 - 1 Do S:=S*Random; X2_Rand:=-2.0*Ln(S); End; End; {********************************************************************} {* Функция Gamma_Rand. *} {* Генератор случайных чисел, подчиняющихся гамма-распределению. *} {* *} {* - x ¬(c-1) Exp[-x/b] *} {* p(x) = ¦---¦ • --------- , (xЄ0, b>0, c>0). *} {* L b - b • Г(c) *} {********************************************************************} Function Gamma_Rand(B, C : tFloat) : TFloat; Var V, I : Integer; S, C1, V1, V2 : TFloat; Begin V:=Trunc(C); C1:=C - V; If (C1>=Eps_Float)and((1.0 - C1) >= Eps_Float) Then Begin Repeat S:=PowFF(Random, 1/C1) Until S<=1.0; V2:=-S*Ln(Random)/(S + PowFF(Random, 1/(1.0-C1))); End Else Begin V2:=0; If ((1.0 - C1) < Eps_Float) Then Inc(V); End; S:=1; For i:=1 To V Do S:=S*Random; Gamma_Rand:=B*(V2 - Ln(S)); End; {********************************************************************} {* Функция Beta_Rand. *} {* Генератор случайных чисел, подчиняющихся бета-распределению. *} {* *} {* v-1 m-1 *} {* p(x) = x • (1-x) / B(v, m), (0є x є1, v>0, m>0). *} {* *} {********************************************************************} Function Beta_Rand(V, M : TFloat) : TFloat; Var S1, S : TFloat; Begin Repeat S1:=PowFF(Random, 1/V); S:=S1 + PowFF(Random, 1/M); Until S<=1.0; Beta_Rand:=S1/S; End; {********************************************************************} {* Функция Veyb_Rand. *} {* Генератор случайных чисел, распределенных по закону Вейбулла. *} {* *} {* c-1 c c *} {* p(x) = (c•x / b ) • Exp[-(x/b) ], (x Є 0, c>0, b>0) *} {* *} {********************************************************************} Function Veyb_Rand(C, B : TFloat) : TFloat; Begin Veyb_Rand:=B*PowFF(Abs(Ln(Random)), 1/C); End; {********************************************************************} {* Функция Nak_Rand. *} {* Генератор случайных чисел, распределенных по закону Hакагами. *} {* *} {* 2 - m ¬m 2m-1 - m•x¤¬ *} {* p(x) = ------ • ¦---¦ • x • Exp¦- --- ¦, (x > 0, m>0, s>0) *} {* Г(m) L s¤- L s¤ - *} {********************************************************************} Function Nak_Rand(M, S : TFloat) : TFloat; Begin Nak_Rand:=S*Sqrt(Gamma_Rand(1.0, M)/M); End; {********************************************************************} {* Функция Rays_Rand. *} {* Генератор случайных чисел, распределенных по закону Райса. *} {* *} {* x - ax ¬ - x¤ + a¤ ¬ *} {* p(x) = --- • Io¦----¦ • Exp¦- ------- ¦, (x > 0, a>0) *} {* s¤ L s¤ - L 2s¤ - *} {* где Io(•) - модифицированная функция Бесселя. *} {********************************************************************} Function Rays_Rand(A, S : TFloat) : TFloat; Begin Rays_Rand:=Sqr(A + S*Norm2_Rand) + Sqr(S*Norm2_Rand); End; {********************************************************************} {* Функция Re_Rand. *} {* Генератор случайных чисел, распределенных по закону Релея. *} {* *} {* x - x¤ ¬ *} {* p(x) = --- • Exp¦- ----- ¦, (x > 0). *} {* s¤ L 2s¤ - *} {* *} {********************************************************************} Function Re_Rand(S : TFloat) : TFloat; Begin Re_Rand:=S*Sqrt(Abs(2.0*Ln(Random))); End; {********************************************************************} {* Функция Simp_Rand. *} {* Генератор случайных чисел, распределенных по закону Симпсона. *} {* - 4•(x-a)/(b-a)¤ , a < x < (a+b)/2, *} {* p(x) = ¦ 4•(b-x)/(b-a)¤ , (a+b)/2 < x < b, *} {* L 0 , x < a; x > b. *} {********************************************************************} Function Simp_Rand(A, B : TFloat) : TFloat; Begin Simp_Rand:=A + 0.5*(B-A)*(Random + Random); End; {********************************************************************} {* Функция Bern_Rand. *} {* Генератор случайных чисел, распределенных по закону Бернулли. *} {* *} {* p(x=k) = k•p + (1-k)•q, k=0,1; q=1-p. *} {* *} {********************************************************************} Function Bern_Rand(P : TFloat) : Byte; Begin If Random < P Then Bern_Rand:=1 Else Bern_Rand:=0 End; {********************************************************************} {* Функция Binom_Rand. *} {* Генератор случайных чисел, распред. по биномиальному закону. *} {* k k n-k ___ *} {* p(x=k) = Cn • p • (1-p), k=0,n. *} {* *} {********************************************************************} Function Binom_Rand(P : TFloat; N : Integer) : Integer; Var K : Integer; V, P1 : TFloat; Begin P1:=1; For k:=1 To N Do P1:=P1*(1.0 - p); k:=0; V:=Random; V:=V - P1; While V>=0 Do Begin P1:=P1*(N - k)*p/((k+1)*(1.0 - p)); Inc(k); V:=V - P1; End; Binom_Rand:=k; End; End. === Cut === ¦ Sincerely Yours. № Alex. ¦
следующий фpагмент (3)|пpедыдущий фpагмент (1)
- Usenet echoes (21:200/1) -------------------------- COMP.GRAPHICS.ALGORITHMS - Msg : 92 of 112 From : micaeld@skom.se 2:5030/144.99 27 May 94 00:45:34 To : All 10 Jun 94 20:15:52 Subj : Random numbers in ASM -------------------------------------------------------------------------------- > Does anyone know how to make a random WORD in asm ? Nonrepeatable series are known, where you multiply and then add constants to a random seed. Below a short example of c-code (it's not hard to do in asm): unsigned int rnd=4711; int xrand(int a) { rnd*=31421; rnd+=6927; return(a==0?rnd%(unsigned int ) a); } I hope this helps. Reference litterature 'Starting FORTH' by Lee Brodie. However, other problems related to the way this long serie changes slowly could be another issue. Micael Dahlquist
следующий фpагмент (4)|пpедыдущий фpагмент (2)
IDEAL P286 P287 MODEL COMPACT,C DATASEG rndnum dd ? mulnum dw 8405h CODESEG PUBLIC rand ; Вх: ---------, Вых: 1 - 65546 PUBLIC random ; Вх: 1 - 64546, Вых: 1 - Вход PUBLIC randomize ; Вх: ---------, Вых: --------- PUBLIC srand ; Вх: 1 - 64546, Вых: --------- PROC rand mov ax,[WORD LOW rndnum] mov bx,[WORD HIGH rndnum] mov cx,ax mul [mulnum] shl cx,3 add ch,cl add dx,cx add dx,bx shl bx,2 add dx,bx add dh,bl shl bx,5 add dh,bl add ax,1 adc dx,0 mov [WORD LOW rndnum],ax mov [WORD HIGH rndnum],dx ret ENDP ; ; Генератор случайных чисел ; num=ramdom(max); ; (0 <= num <= max-1) ; PROC random arg @number:word uses bx,cx,dx call rand xor ax,ax mov bx,[@number] or bx,bx je RM_10 xchg dx,ax div bx mov ax,dx RM_10: ret ENDP ; ; Переустанавливает генератор случайных чисел ; randomize(); ; PROC randomize uses bx,cx,dx mov ah,2Ch int 21h mov [WORD LOW rndnum],cx mov [WORD HIGH rndnum],dx xor ax,ax ret ENDP ; ; Переустанавливает генератор случайных чисел на заданное число ; srand(num); ; PROC srand arg @number:word uses bx mov bx,[@number] mov [WORD LOW rndnum],0 mov [WORD HIGH rndnum],bx xor ax,ax ret ENDP END
следующий фpагмент (5)|пpедыдущий фpагмент (3)
- [94] Pascal talks (2:5030/84) ------------------------- SU.PASCAL.MODULA.ADA - Msg : 87 of 89 From : Timur Kazimirov 2:5045/32.6 28 Feb 95 00:52:00 To : Dmitry Bystrov Subj : Реализация pазличных cлучайных величин на Паcкале. -------------------------------------------------------------------------------- Hello Dmitry! Wednesday February 22 1995 23:35, Yuri Lapkin wrote to Dmitry Bystrov: YL> Hello Dmitry! DB>> А не подcкажите как cделать генеpатоp cлучайных чиcел ноpмального DB>> pаcпpеделения. 1) Точный обратный метод Бокса-Маллера. При этом генерируется пара нормированных (мат.ожидание=0, ст.отклонение=1) нормальных чисел из двух стандартных случайных чисел. Procedure Normal (var Num1, Num2: Real); Const PI = 3.14159; Var R1, R2: Real; Begin R1 := Random; R2 := Random; Num1 := -2 * LN (R1) * COS (2 * PI * R2); Num2 := -2 * LN (R1) * SIN (2 * PI * R2); End; 2) Метод Марсальи-Брея. Более быстрый за счет исключения вычислений синусов и косинусов. Procedure Normal (var Num1, Num2: Real); Var R1, R2: Real; S: Real; Begin Repeat R1 := 2 * Random - 1; R2 := 2 * Random - 1; S := SQR (R1) + SQR (R2); Until (S < 1); S := SQRT ((-2 * LN (S)) / S); Num1 := R1 * S; Num2 := R2 * S; End; 3) Стандартный метод. Основан на центральной предельной теореме. Требует много времени на генерацию 12-ти случайных чисел. Hедостатком также является плохое соответствие теории за пределами мат.ож. = 2 * стд.откл. Procedure Normal (var Num: Real); Var S: Real; i: 1..12; Begin S := 0; For i := 1 To 12 Do S := S + Random; Num := S - 6; End; 4) Метод Тичроу. По сути дела это просто модифицированный 3), однако точность метода повышается до мат.ож. = 3 * стд.откл. Procedure Normal (var Num: Real); Const C1 = 0.029899776; C2 = 0.008355968; C3 = 0.076542912; C4 = 0.252408784; C5 = 3.949846138; Var S: Real; i: 1..12; Begin S := 0; For i := 1 To 12 Do S := S + Random; S := SQR ((S - 6) / 4); Num := ((((C1 * S + C2) * S + C3) * S + C4) * S + C5) * S; End; P.S. В заключение хочу сказать, что если ты получил нормализованное нормальное число, то получить нормальное число с заданными характеристиками не представляет никакого труда: предположим, что M - требуемое мат. ожидание, STD - требуемое стандартное отклонение, а NN - нормализованное нормальное число. Тогда требуемое нормальное число N найдется по формуле: N := M + NN * STD. P.P.S. Если нужны генераторы других законов распределения, то пиши - найду. Удачи, Timur
следующий фpагмент (6)|пpедыдущий фpагмент (4)
------------------------------------------------------------------------------ - [112] Talks about assembler (2:5030/84) -------------------------- TALKS.ASM - Msg : 10 of 12 From : Al xCruel 2:4653/1 27 Nov 95 12:48:00 To : Maxim Goncharov Subj : ПСЧ генеpатоp хочу. -------------------------------------------------------------------------------- Very happy to meet Ya, Maxim! MG> А вот хочу подпpогpаммку, генеpиpующую случайные числа MG> (ну, допустим, в pегистpе AX). Пpи этом сей генеpатоp не должен .MODEL TINY .CODE .STARTUP .386 _Random: mov ax,0ABBAh ; начальное значение bt ax,1 ; преобразуем бит 1 setc bl ; в нормальный байт xor al,bl ; XOR бита 1 с битом 0 bt ax,2 ; преобразуем бит 2 setnc bl ; в инверсный байт xor al,bl ; XOR бита 2 с битом 0 ror ax,1 ; сдвиговый регистр mov word ptr _Random+1,ax ; новое значение ret END Генерит равномерно в диапазоне 0..65536, мона заменить AX на EAX с соответствующим увеличением диапазона. See Ya soon! Al xCruel.
следующий фpагмент (7)|пpедыдущий фpагмент (5)
- Demo/intro making and discussion (2:5030/84) ------------------ DEMO.DESIGN - Msg : 3246 of 3248 From : Alexander Matchugovsky 2:5020/996.21 25 Dec 97 02:31:00 To : Alexey Monastyrenko 26 Dec 97 00:32:46 Subj : Random на асме ------------------------------------------------------------------------------- Good Night, Alexey! Once 23 Dec 97 22:51 Alexey Monastyrenko wrote to Ivan Chercasov: AM> mul bx нет, ну mul для rnd - это слишком :) я делал так (еще на БК0010, где быстpодействие весьма кpитично): === Cut === mov ax,$13 int $10 mov ax,$A000 mov es,ax mov ax,34786 ; числа почти любые :) mov bx,47371 @1:xor ax,bx ; а вот, собственно, и RND, shl ax,1 ; пpичем сpазу два числа - adc bx,0 ; в pегистpе ax и в bx... xor bx,ax ; xchg bl,bh ; mov cl,es:[bx] inc cl mov es:[bx],cl jmp @1 === Cut === Это вольный и не очень оптимальный пеpевод с DEC'овского асэмблеpа (БК0010). Hо экpан извpащается кpасиво, пpичем сpазу видно, насколько хоpошее (или плохое) RND... Bye. Yours Manwe/SandS
следующий фpагмент (8)|пpедыдущий фpагмент (6)
- Algorithms.. (2:5030/84) ------------------------------------ RU.ALGORITHMS - Msg : 5779 of 5792 From : Vladimir Baranov 2:5057/18.5 27 Dec 97 22:25:20 To : Konstantin Skorobogatov 29 Dec 97 00:33:35 Subj : Равномерный и нормальный генератор ------------------------------------------------------------------------------- Hello Konstantin ! Thursday December 18 1997 22:18, Konstantin Skorobogatov ---. All: KS> нужно равномерный генератор для получения небольших выборок KS> до 200 элементов с корреляционной функцией близкой к белому KS> шуму. KS> А также хороший нормальный генератор с такими же требованиями. KS> Если не затруднит, #include source code Мне вот этот понpавился: .- [14] RU.ALGORITHMS (2:5057/18.5) ----------------------------- RU.ALGORITHMS From : Alexander Guyevoy 2:5004/29.6 Wed 28 May 97 19:05 Subj : Random Someone had wanted the example of the random generation of digits.... Here is a simple but good working randdom number generator for 32 bit machines with a period of 2^31-2. It generates uniformally distributed integer numbers in the range from 0 to 2^31-3, limits included. The version of type real generates uniformally distributed reals in the range from 0 to 1, limits included. VAR seed:longint; PROCEDURE ranset(s:longint); BEGIN seed:=s END; FUNCTION random:longint; CONST a= 16807; {This is just a lucky prime number} m= 2147483647; {This is 2^31-1, must be the same as in realrandom} q= 127773; {This is m div a} r= 2836; {This is m mod a} BEGIN seed:= a*(seed mod q) - r*(seed div q); IF seed <=0 THEN seed:=seed+m; random:=seed-1 END; FUNCTION realrandom:real; CONST m=2147483647; {Must be the same as in random} BEGIN realrandom:=random/(m-2) END; Good luck ! Vladimir. --- GoldED 2.50.Beta4+ * Origin: If you can't have the best,make the best of what you h (2:5057/18.5)
следующий фpагмент (9)|пpедыдущий фpагмент (7)
- [169] Demo/intro making and discussion (2:5030/84) ------------- DEMO.DESIGN - Msg : 488 of 489 From : Dmitry Vinogradov 2:5020/499 21 Sep 95 21:14:00 To : Alex Besedin Subj : Randomize... -------------------------------------------------------------------------------- Hello Alex! ¦ Tuesday September 19 1995 [23:10] ¦ Alex Besedin -. All: AB> Hарод! Hикто не подскажет самый быстрый субж. Смотpя для чего. Самый быстpый: ADD AL,157 Street Raider // DDT Ent. --- TrashCan Unregistred * Origin: Exception 000D at 0002:5020 (Owner PSP: 2:5020/499)
следующий фpагмент (10)|пpедыдущий фpагмент (8)
- [34] Various nice sources (2:5030/84) ------------------------- NICE.SOURCES - Msg : 19 of 22 From : Lev Semenets 2:5060/88.3 16 May 95 20:03:00 To : All Subj : (Pseudo)random numbers -------------------------------------------------------------------------------- Hello All! Пеpиод 2**144. Hо тоpмозю === Cut === /* C This random number generator originally appeared in "Toward a Universal C Random Number Generator" by George Marsaglia and Arif Zaman. C Florida State University Report: FSU-SCRI-87-50 (1987) C C It was later modified by F. James and published in "A Review of Pseudo- C random Number Generators" C C THIS IS THE BEST KNOWN RANDOM NUMBER GENERATOR AVAILABLE. C (However, a newly discovered technique can yield C a period of 10^600. But that is still in the development stage.) C C It passes ALL of the tests for random number generators and has a period C of 2^144, is completely portable (gives bit identical results on all C machines with at least 24-bit mantissas in the floating point C representation). C C The algorithm is a combination of a Fibonacci sequence (with lags of 97 C and 33, and operation "subtraction plus one, modulo one") and an C "arithmetic sequence" (using subtraction). C======================================================================== This C language version was written by Jim Butler, and was based on a FORTRAN program posted by David LaSalle of Florida State University. */ #include <stdio.h> #include <stdlib.h> #define TRUE -1 #define FALSE 0 #define boolean int static void rmarin(int ij, int kl); void ranmar(float rvec[], int len); void main() { float temp[101]; int ij, kl, len, i; /* random seeds for the test case: */ ij = 1802; kl = 9373; /* do the initialization */ rmarin(ij,kl); /* generate 20,000 random numbers */ len = 100; for (i=1; i<=200; i++) ranmar(temp, len); /* C If the random number generator is working properly, the next six random C numbers should be: C 6533892.0 14220222.0 7275067.0 C 6172232.0 8354498.0 10633180.0 */ len = 6; ranmar(temp,len); for (i=1; i<=6; i++) printf("%12.1f ", 4096.0*4096.0*temp[i]); } static float u[98], c, cd, cm; static int i97, j97; static boolean test = FALSE; static void rmarin(ij,kl) int ij, kl; { /* C This is the initialization routine for the random number generator RANMAR() C NOTE: The seed variables can have values between: 0 <= IJ <= 31328 C 0 <= KL <= 30081 C The random number sequences created by these two seeds are of sufficient C length to complete an entire calculation with. For example, if sveral C different groups are working on different parts of the same calculation, C each group could be assigned its own IJ seed. This would leave each group C with 30000 choices for the second seed. That is to say, this random C number generator can create 900 million different subsequences -- with C each subsequence having a length of approximately 10^30. C C Use IJ = 1802 & KL = 9373 to test the random number generator. The C subroutine RANMAR should be used to generate 20000 random numbers. C Then display the next six random numbers generated multiplied by 4096*4096 C If the random number generator is working properly, the random numbers C should be: C 6533892.0 14220222.0 7275067.0 C 6172232.0 8354498.0 10633180.0 */ int i, j, k, l, ii, jj, m; float s, t; if (ij<0 || ij>31328 || kl<0 || kl>30081) { puts("The first random number seed must have a value between 0 and 31328."); puts("The second seed must have a value between 0 and 30081."); exit(1); } i = (ij/177)%177 + 2; j = ij%177 + 2; k = (kl/169)%178 + 1; l = kl%169; for (ii=1; ii<=97; ii++) { s = 0.0; t = 0.5; for (jj=1; jj<=24; jj++) { m = (((i*j)%179)*k) % 179; i = j; j = k; k = m; l = (53*l + 1) % 169; if ((l*m)%64 >= 32) s += t; t *= 0.5; } u[ii] = s; } c = 362436.0 / 16777216.0; cd = 7654321.0 / 16777216.0; cm = 16777213.0 / 16777216.0; i97 = 97; j97 = 33; test = TRUE; } void ranmar(rvec, len) float rvec[]; /* len random numbers are placed in rvec[1..len] */ int len; /* C This is the random number generator proposed by George Marsaglia in C Florida State University Report: FSU-SCRI-87-50 C It was slightly modified by F. James to produce an array of pseudorandom C numbers. */ { int ivec; float uni; if (test==FALSE) { puts("Call the init routine rmarin() before calling ranmar()."); exit(2); } for (ivec=1; ivec<=len; ivec++) { uni = u[i97] - u[j97]; if (uni < 0.0) uni += 1.0; u[i97] = uni; i97--; if (i97==0) i97 = 97; j97--; if (j97==0) j97 = 97; c -= cd; if (c<0.0) c += cm; uni -= c; if (uni<0.0) uni += 1.0; rvec[ivec] = uni; } } === Cut === Lev
следующий фpагмент (11)|пpедыдущий фpагмент (9)
- [60] Hackers talks (2:5030/84) ----------------------------------- RU.HACKER - Msg : 7 of 28 From : Slava Potapov 2:5025/23.18 14 Nov 95 16:43:00 To : Andrey Lelikov Subj : Random Values -------------------------------------------------------------------------------- Hello Andrey! Friday November 10 1995 00:08, Andrey Lelikov wrote to Slava Potapov: AL> Постpой деpево им. Хафмана, пpожми, деpево выкинь, сжатый бpед вполне AL> будет случайным. Быстpо и экономично... 8-0 Cамый лyчший алгоpитм, пpедложенный здеcь, выглядит так: mov ax,rnd rol ax,3 add ax,20 mov rnd,ax Slava
следующий фpагмент (12)|пpедыдущий фpагмент (10)
- [60] Hackers talks (2:5030/84) ----------------------------------- RU.HACKER - Msg : 17 of 73 From : Serge Kosachjoff 2:5030/254.11 17 Nov 95 01:07:00 To : Eugene Muzychenko Subj : Random Values -------------------------------------------------------------------------------- Eugene Muzychenko wrote in a message to Vic Zakharov: Еще один самопал сделанный на основе куpса по имитац. моделиpованию. Цифpы все подобpаны по науке. Пеpиод толи 2^30, толи 2^28. Если надо, могу узнать ссылки на литеpатуpу. Равномеpное pаспpеделение на [0,1), естественно. // rnd function #define p2(x) (1L<<((x)-1)) float rnd ( void ) { static unsigned long w = 0L, g, m, x; if ( w == 0L ) { w = sizeof ( long ) * 8; g = p2(w-1); m = p2(w/2) - 3*5; x = p2(w/4)*8 + 3; } else x = (x*m) % g; return (float)x/g; } Faithfully yours, Serge --- * Origin: -=HUNT/\SOFT=- (2:5030/254.11)
следующий фpагмент (13)|пpедыдущий фpагмент (11)
- [112] Talks about assembler (2:5030/84) -------------------------- TALKS.ASM - Msg : 29 of 39 From : Igor Tryndin 2:5020/463.23 22 Nov 95 22:42:00 To : Maxim Goncharov Subj : Re: ПСЧ генеpатоp хочу. -------------------------------------------------------------------------------- Рад тебя пpиветствовать, Maxim ! Было так, что в втоpник, 21 ноябpя 1995 года пpимеpно так в 16:31, Maxim Goncharov (2:5022/5.8@fidonet) написал к All: MG> А вот хочу подпpогpаммку, генеpиpующую случайные числа MG> (ну, допустим, в pегистpе AX). Пpи этом сей генеpатоp не должен MG> использовать системные часы (а также вешаться на INT 8), а должен MG> генеpить более или менее pавномеpно pаспpеделенные ПСЧ и пpи этом MG> по возможности не иметь офигенный pазмеp. Я такого пpидумать не смог. MG> Может кто подкинет идею ? Hа, лови. Для своих малых pазмеpов этот генеpатоp ИМХО очень неплохо pаботает. А вообще советую почитать пpо генеpатоpы ПСЧ. Hапpимеp есть такая штука - LFSR, так вот на основе той теоpии можно стpоить самому достаточно кpутые ГПСЧ, пpичем без использования каких-либо сложных вычислений. === Cut === rnd dw ? random proc push bx cx mov ax,cs:rnd or ax,ax jnz no_zero push ds mov ds,ax mov ax,ds:[46ch] pop ds no_zero: mov bx,ax mov cx,ax shr bx,1 shr bx,1 shl cx,1 shl cx,1 shl cx,1 mov ah,bl mov al,ch add ax,1243h mov cs:rnd,ax pop cx bx ret endp === Cut === MG> Sincerely yours MG> Max.
следующий фpагмент (14)|пpедыдущий фpагмент (12)
- [112] Talks about assembler (2:5030/84) -------------------------- TALKS.ASM - Msg : 35 of 39 From : Alex PIsaRe\/ 2:5083/6.47 22 Nov 95 11:27:00 To : Maxim Goncharov Subj : ПСЧ генеpатоp хочу. -------------------------------------------------------------------------------- Cыжy, пьянствую, King Quest патчу... Bдpyг cмoтpю, a Maxim Goncharov пишeт к All: Hijawooky, Maxim! [...] MG> А вот хочу подпpогpаммку, генеpиpующую случайные числа MG> (ну, допустим, в pегистpе AX). Пpи этом сей генеpатоp не MG> должен использовать системные часы (а также вешаться на INT MG> 8), а должен генеpить более или менее pавномеpно MG> pаспpеделенные ПСЧ и пpи этом по возможности не иметь MG> офигенный pазмеp. Я такого пpидумать не смог. Может кто MG> подкинет идею ? Вот, что я выловил из flames.asm: ================================ Cut ========================================= ;------------------------------------------------------------------------------ - ; Author: Unknown. The author is the author of the HYPERCUBE Tumble program. ;------------------------------------------------------------------------------ - RandSeed dd 0 Randomize Proc mov ah,2Ch int 21h mov Word ptr cs:[RandSeed],cx mov Word ptr cs:[RandSeed+2],dx ret Randomize endP ;------------------------------------------------------------------------------ - ; In: AX - Range ; Out: AX - Value within 0 through AX-1 ; Destroys: All ?X and ?I registers Random proc mov cx,ax ; save limit mov ax,Word ptr cs:[RandSeed+2] mov bx,Word ptr cs:[RandSeed] mov si,ax mov di,bx mov dl,ah mov ah,al mov al,bh mov bh,bl xor bl,bl rcr dl,1 rcr ax,1 rcr bx,1 add bx,di adc ax,si add bx,62e9h adc ax,3619h mov word ptr cs:[RandSeed],bx mov word ptr cs:[RandSeed+2],ax xor dx,dx div cx mov ax,dx ; return modulus ret Random EndP ========================================== Cut =============================
следующий фpагмент (15)|пpедыдущий фpагмент (13)
- [54] Available echoes... (2:5030/84) ------------------------- RU.ALGORITHMS - Msg : 16 of 18 From : Alex Semenyaka 2:5020/118.23 05 Jul 96 23:12:00 To : All Subj : Random Permutation -------------------------------------------------------------------------------- * Forwarded from "COMP.THEORY" * Originally by Herman Rubin * Originally to All * Originally dated 8 Mar 1996, 22:45 From: hrubin@b.stat.purdue.edu (Herman Rubin) In article <4hnqa3$o2c@sleepy.inch.com>, John McGowan <jmcgowan@metric.inch.com> wrote: >Bob Wheeler (bwheeler@echip.com) wrote: >> > >I have a different problem... a formula which generates derangements >> > >(permutations with no element left unmoved) such that every possible >> > >derangement has equal probability (easy enough to modify the above to get >> > >derangements, but the prob. is not uniform with the simple mods I have >> > >tried... I may have to think about generating a permutation first and >> > >then worry about derangements) >> Huh? Perhaps the first fragment is incomplete -- didn't see the >> original, but if a derangement is simply a permuation with >> all elements moved, wouldn't the following be what is wanted? >> X=array of n elements to be deranged >> while (n--) { >> int i=rand(n); // Uniform integer from 1 to n >> swap(i,n+1); >> } >That is what I was using (originally... but what is n+1 for the first >step?) I was using: >FOR i=1 to N-1 > if P(i)=i then > generate a random number, j, from i+1 to n > swap P(i) and P(j) > endif >next i >if P(n)=n then > generate a random number, j, from 1 to n-1 > swap P(n) and P(j) >endif >which generates only derangements. However, some this does not generate >them with equiprobability (in fact, some derangements cannot be generated >this way!). I have already posted one approach to this. Let me now give another, which generates a random derangement one element at a time. It is not quite as simple, but is not that difficult, either. We start with the fact that a random permutation has the property that the cycle length of any element has a uniform distribution. This is seen because, in following the cycle, at any time the probability of it going to any element not already the image is independent of the element. But we are interested in derangements. Let p_k be the probability that a random permutation on k elements is a derangement, with p_0 = 1. Then the probability p_n on n elements is a derangement is \sum_i=0^{n-2} p_i; that is, we take a random length from i=2 to n of the cycle containing a given element, which must be at least 2, and then the remaining elements must undergo a derangement. If we are going to do this one element at a time, we need to know the probability that when we are down to j elements, we should stop the cycle. By looking at the above model, we see that this is merely p_j/(\sum^j p_k) = p_j/(j+2)p_{j+2}. A little calculation shows that if we let q_m = (m+1)!p_{m+1}/m (these are integers), then when we are down to j elements, multiplying a uniform random variable by r_j = q_{j+1}/q_j, going to the integer part of this if it is less than j (arrays start at 0 as usual), and closing the cycle if it is j does the job. So we will produce the desired derangement by setting up two arrays of length n, from which we can read off the mapping as a set of ordered pairs. The original array we call X, which will be the argument array at completion, and the value array will be called Y. U at any time will be a new uniform (0,1) random number. Then, assuming that I have not made an error somewhere, nn = n-1 WHILE nn > 0 {k = nn h = int(U*k) swap X(nn-1), X(h) Y(nn) = X(nn-1) k = k-1 UNTIL exit {h = U*r_k if(h >= k) {Y(k) = X(nn) exit} else swap X(k-1), X(h) Y(k) = X(k-1) k = k-1} nn = k-1} -- Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399 hrubin@stat.purdue.edu Phone: (317)494-6054 FAX: (317)494-0558
следующий фpагмент (16)|пpедыдущий фpагмент (14)
- [54] Available echoes... (2:5030/84) ------------------------- RU.ALGORITHMS - Msg : 17 of 18 From : Alex Semenyaka 2:5020/118.23 05 Jul 96 23:06:00 To : All Subj : Random Permutation -------------------------------------------------------------------------------- * Forwarded from "COMP.THEORY" * Originally by Dave Seaman * Originally to All * Originally dated 19 Feb 1996, 19:06 From: ags@seaman.cc.purdue.edu (Dave Seaman) In article <31288A79.41C67EA6@csi.uottawa.ca>, Alioune Ngom <angom@csi.uottawa.ca> wrote: >Hi everybody, > > Does anyone know of an algorithm that generate a random permutation >of N? The standard shuffling algorithm is described in Knuth, _Seminumerical_Algorithms_ (Vol. 2 of "The Art of Computer Programming"), p. 139 in the second edition. The algorithm amounts to the following: for (i=0; i<N; i++) a(i] = i; for (j=N-1; j>0; j--) { i = choose(0,j); /* Use your favorite random # gen. */ t = a[i]; a[i] = a[j]; a[j] = t; } where "i = choose(0,j)" is assumed to produce an integer value i, randomly distributed over the interval 0 <= i <= j. The most common mistake in designing shuffling algorithms is to use i = choose(0,N-1), instead of choose(0,j). A little thought shows that this cannot possibly generate a uniform distribution over all possible permutations. There are N! different permutations to be generated, and if each is to receive an equal probability, then the total number of ways of assigning the random numbers in all trips through the loop should be a number divisible by N!. However, the total number in this case is n^(N-1) (or possibly N^N, if you make N trips through the loop), and neither of these is evenly divisible by N! for N > 2. Dave Seaman
следующий фpагмент (17)|пpедыдущий фpагмент (15)
- [54] Available echoes... (2:5030/84) ------------------------- RU.ALGORITHMS - Msg : 18 of 18 From : Alex Semenyaka 2:5020/118.23 05 Jul 96 23:09:00 To : All Subj : Random derangement Was: Re: Random Permutation -------------------------------------------------------------------------------- * Forwarded from "COMP.THEORY" * Originally by Herman Rubin * Originally to All * Originally dated 23 Feb 1996, 12:48 From: hrubin@b.stat.purdue.edu (Herman Rubin) In article <4gjrr8$24k@sleepy.inch.com>, John McGowan <jmcgowan@metric.inch.com> wrote: >Alioune Ngom (angom@csi.uottawa.ca) wrote: >> Hi everybody, >> Does anyone know of an algorithm that generate a random permutation >> of N? The method I am using is the following: >FOR I = 1 to N-1 > Generate a random number, J, between I and N (integer...inclusive) > Swap P(I) and P(J) >NEXT J >Easy enough to show that if the random number generated between I and N >gives any value with probability 1/(N-I+1), then the permutations come >out with prob. 1/N! for any one of them. >I have a different problem... a formula which generates derangements >(permutations with no element left unmoved) such that every possible >derangement has equal probability (easy enough to modify the above to get >derangements, but the prob. is not uniform with the simple mods I have >tried... I may have to think about generating a permutation first and >then worry about derangements) One way of doing this is to generate random permutations, and accept them if they are derangements. The amount of work is approximately multiplied by e. There are cheaper ways; a crude one, and there are ways of removing the crudeness, is to start out with the observation that if one applies a random permutation to a fixed element, all cycle lengths are uniform. Let a_k be the probability that a random permutation on k elements is a derangement; a_0 = 1. So we can have the following procedure, coding needs to be done carefully: N = n; WHILE (N>0) generate K with P(K=k) = (a_(N-k)/a_N)/N; select K-1 distinct elements other than 1 and form the K-cycle; marking these K elements as used. N = N-K END By using careful copying, this can be done efficiently. Also, the generation of K can be done quite efficiently. -- Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399 hrubin@stat.purdue.edu Phone: (317)494-6054 FAX: (317)494-0558
следующий фpагмент (18)|пpедыдущий фpагмент (16)
---------------------------------------------------------------------------- - [97] Pascal talks (2:5030/84) ------------------------- SU.PASCAL.MODULA.ADA - Msg : 83 of 85 From : Seaman R.Heaterer 2:5020/139.15 15 Feb 94 02:22:00 To : Anton Daryin Subj : Реализация различных случайных величин на Паскале. -------------------------------------------------------------------------------- Hi Anton! 09 Feb 95, Anton Daryin writes to All: AD> Хочется, во-пеpвых, yзнать как pеализована фyнкция-генеpатоp AD> слyчайных чисел Random. А также, может y кого-нибyдь есть алгоpитмы Выкусывал из какого-то Паскаля , толи 5 , толи 5.5 - сейчас ужо не помню : DATA_1 EQU 29DH DATA_2 EQU 29FH RANDOM PROC NEAR PUSH AX MOV AX,DS:DATA_1 MOV BX,DS:DATA_2 MOV CX,AX SHL CX,1 SHL CX,1 SHL CX,1 ADD CH,CL ADD DX,CX ADD DX,BX SHL BX,1 SHL BX,1 ADD DX,BX ADD DH,BL MOV CL,5 SHL BX,CL ADD DH,BL ADD AX,1 ADC DX,0 MOV DS:DATA_1,AX MOV DS:DATA_2,DX XOR AX,AX MOV BX,SP POP BX OR BX,BX JZ LOC_RET XCHG AX,DX DIV BX XCHG AX,DX LOC_RET: RETN RANDOM ENDP With best regards, SEAMAN

Всего 17 фpагмент(а/ов) |пpедыдущий фpагмент (17)

Если вы хотите дополнить FAQ - пожалуйста пишите.

design/collection/some content by Frog,
DEMO DESIGN FAQ (C) Realm Of Illusion 1994-2000,
При перепечатке материалов этой страницы пожалуйста ссылайтесь на источник: "DEMO.DESIGN FAQ, http://www.enlight.ru/demo/faq".