Recent

Author Topic: [SOLVED] MWC Random number generator  (Read 3982 times)

Nitorami

  • Sr. Member
  • ****
  • Posts: 481
[SOLVED] MWC Random number generator
« on: February 18, 2017, 09:12:26 pm »
I found a simple MWC random generator written in x86 assembly in an older thread of this forum, modified it a bit and and compared it to a Pascal version. Surprisingly, the Pascal code is just as fast or even faster than the assembler routine.

But, the output of the two routines is slightly different. When running both generators in parallel, their outputs will start to differ after a few calls. The difference is 1 at first, but then avalanches, of course.

Both versions reasonably pass the statistical tests I did, and should be good enough for my purpose. But, testing ten million numbers does not mean a lot, and I am a bit concerned that there may be a mistake in one of the generators which reduces its theoretical period length.

The asm code is very simple and I think it should do the same as the Pascal routine but it does not... guess it has to do with the handling of the carry bit. Does anyone have sufficient knowledge of assembler to tell where the difference is ?

Code: Pascal  [Select][+][-]
  1. {$mode objfpc}
  2. {$asmmode intel}
  3. {$OPTIMIZATION ON}
  4.  
  5. uses sysutils;
  6. var T1: TDateTime;
  7.  
  8.  
  9. function MWC: dword; inline;
  10. var   t          : qword;
  11. const c          : dword = 100;
  12.       rngseed    : dword = 100;
  13.       Multiplier : dword = 1791398085;
  14. begin
  15.   t := qword (multiplier) * rngseed + c;
  16.   c   := hi (t);
  17.   rngseed := lo(t);
  18.   result  := lo(t);
  19. end;
  20.  
  21.  
  22. function MWC_ASM: dword; assembler; inline;
  23. //FUNCTION AsmRand (rangw: dword): dword; pascal; assembler;
  24. //returns integer 0..Range-1
  25. { High quality random numbers based on Multiply With Carry, by prof. Marsaglia
  26.      ::            x(n)=a*x(n-1)+carry mod 2^32                       ::
  27.         The period of the generator is a*2^31-1.
  28.  multiplier a can be selected from the following list (any one will do):
  29.  1791398085 1929682203 1683268614 1965537969 1675393560
  30.  1967773755 1517746329 1447497129 1655692410 1606218150
  31.  2051013963 1075433238 1557985959 1781943330 1893513180
  32.  1631296680 2131995753 2083801278 1873196400 1554115554}
  33. const C          : dword = 100;
  34.       RngSeed    : dword = 100;
  35.       Multiplier : dword = 1791398085;
  36.   ASM
  37.   MOV EAX, rngseed
  38.   MUL Multiplier       //64 bit multiplication, carry in EDX
  39.   ADD EAX, C           //add previous carry
  40.   MOV RngSeed, EAX     //update seed
  41.   MOV C, EDX           //update carry, random number generation done
  42. END;
  43.  
  44.  
  45. const Num = 2000*100000;
  46. var i,j: longint;
  47. begin
  48.   writeln;
  49.   writeln ('Compare MWC : MWC_ASM');
  50.   for i := 1 to 10 do writeln (mwc:12,mwc_asm:12);
  51.  
  52.   T1 := Now;
  53.   for i := num downto 0 do mwc;
  54.   writeln;
  55.   writeln ('------------- TIME MWC : ',(Now-T1)*3600*24*1e9/Num:3:3, ' ns. --------------------');
  56.  
  57.   T1 := Now;
  58.   for j := num downto 0 do mwc_asm;
  59.   writeln;
  60.   writeln ('---------- TIME MWC_ASM : ',(Now-T1)*3600*24*1e9/Num:3:3, ' ns. --------------------');
  61. end.
  62.  

« Last Edit: February 19, 2017, 11:52:03 pm by Nitorami »

ASerge

  • Hero Member
  • *****
  • Posts: 2222
Re: MWC Random number generator
« Reply #1 on: February 19, 2017, 10:48:49 am »
In the assembler the variable name is its address, not the value

Thaddy

  • Hero Member
  • *****
  • Posts: 14197
  • Probably until I exterminate Putin.
Re: MWC Random number generator
« Reply #2 on: February 19, 2017, 11:31:03 am »
Not here... It takes the value.. BASM compatible syntax.
Specialize a type, not a var.

ASerge

  • Hero Member
  • *****
  • Posts: 2222
Re: MWC Random number generator
« Reply #3 on: February 19, 2017, 02:15:52 pm »
Not here... It takes the value.. BASM compatible syntax.
You are right, I was wrong.
Well then
Code: ASM  [Select][+][-]
  1. ASM
  2.   MOV EAX, rngseed
  3.   MUL Multiplier       //64 bit multiplication, carry in EDX
  4.   ADD EAX, C           //add previous carry
  5.   ADC EDX, 0 // <- This appended
  6.   MOV RngSeed, EAX     //update seed
  7.   MOV C, EDX           //update carry, random number generation done
  8. END;

Nitorami

  • Sr. Member
  • ****
  • Posts: 481
[SOLVED] Re: MWC Random number generator
« Reply #4 on: February 19, 2017, 11:11:45 pm »
Thank you - that clarifies the issue.

 

TinyPortal © 2005-2018