suggestion for rand()

[WesL]

A couple of years ago, I posted a message concerning the rand() function not giving very random results.  (See https://forum.pellesc.de/index.php?topic=7047.msg26739 and related post https://forum.pellesc.de/index.php?topic=3193.msg12069)  After doing a little digging, I realize now that what I was pointing out was not really a "bug" but rather an inherent weakness in the algorithm.

Just for fun, I decided to look at what the Pelles C implementation of rand() was actually doing.  After examining the "show disassembly" code, I was able to write C code that produces the same results.  The algorithm used is a linear congruential generator (LCG) with a "shuffle," akin to what is recommended in Numerical Recipes, 2nd Ed (1992).

Interestingly, in Numerical Recipes, 3rd Ed (2007), the authors basically state that times have changed and they now give the following warning: "Never use a generator principally based on a linear congruential generator (LCG)..." and "Never use a generator that warns against using its low-order bits as being completely random. That was good advice once, but it now indicates an obsolete algorithm (usually a LCG)."  This last point about the low-order bits being non-random is what my original post was about.

The book shows three examples of modern algorithms which vary in speed and period, the fastest of which (Ranq1) is described as the "Recommended generator for everyday use."  It's far better than the LCG methods and is very efficient: 3 XOR's, 3 shifts, and 1 multiply.  Seems perfectly suited for rand().

Just a suggestion, but it seems to me that a more modern algorithm would be in order for Pelles C rand().

[TimoVJL]

like this one ?

EDIT: visual rand

Code: [Select]

#define WIN32_LEAN_AND_MEAN
#include <windows.h>

LRESULT CALLBACK WndProc(HWND, UINT, WPARAM, LPARAM);

char *szAppName = "WinFrame";
char *szFrameClass = "cWinFrame";
HWND hFrame;
HANDLE hInst;

void __cdecl WinMainCRTStartup(void) {ExitProcess(WinMain(GetModuleHandle(NULL), NULL, NULL, SW_SHOW));}

int WINAPI WinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance,
LPSTR lpCmdLine, int nCmdShow)
{
WNDCLASSEX wcx;
MSG msg;

wcx.cbSize = sizeof(WNDCLASSEX);
wcx.style = CS_HREDRAW | CS_VREDRAW | CS_OWNDC;
wcx.lpfnWndProc = (WNDPROC) WndProc;
wcx.cbClsExtra = 0;
wcx.cbWndExtra = 0;
wcx.hInstance = hInstance;
wcx.hIcon = LoadIcon(NULL, IDI_APPLICATION);
wcx.hCursor = LoadCursor(NULL, IDC_ARROW);
wcx.hbrBackground= 0;
wcx.lpszMenuName = NULL;
wcx.lpszClassName= szFrameClass;
wcx.hIconSm = 0;

if (!RegisterClassEx(&wcx))
return 0;
hInst = hInstance;

hFrame = CreateWindowEx(0, szFrameClass, szAppName,
WS_OVERLAPPEDWINDOW,
CW_USEDEFAULT, CW_USEDEFAULT,
280, 300,
NULL, NULL, hInst, NULL);
if(!hFrame) return 0;
ShowWindow(hFrame, nCmdShow);
while(GetMessage(&msg, NULL, 0, 0))
{
TranslateMessage(&msg);
DispatchMessage(&msg);
}
return msg.wParam;
}

DWORD WINAPI ThreadProc(LPVOID lpParam);

LRESULT CALLBACK WndProc(HWND hWnd, UINT uMsg, WPARAM wParam, LPARAM lParam)
{
switch(uMsg) {
case WM_CREATE:
CreateThread(NULL, 0, (LPTHREAD_START_ROUTINE) ThreadProc, hWnd, 0, NULL);
return 0;
case WM_DESTROY:
PostQuitMessage(0);
return 0;
}
return DefWindowProc(hWnd, uMsg, wParam, lParam);
}

DWORD WINAPI ThreadProc(LPVOID lpParam)
{
//HWND hWnd = (HWND)lpParam;
HDC hDC = GetDC((HWND)lpParam);
int i = 256000;
while(i--) {
int x = rand() % 255;
int y = rand() % 255;
//SetPixel(hDC, x, y, 0x808080);
SetPixel(hDC, x, y, RGB(x,y,69));
Sleep(0);
}
ReleaseDC((HWND)lpParam, hDC);
SetWindowText((HWND)lpParam, "Done");
return 0;
}

[WesL]

Yes, that's the one.  The original Numerical Methods code implements the algorithm using a C++ style struct (used like a class).  My own translation to C style functions didn't involve pointers but instead used returned values like rand() does.  And I added small wrapper functions for compatibility with standard srand() and rand().

I would have posted my own code, but the Numerical Recipes website (http://numerical.recipes/licenses/redistribute.html) says, "We never give permission for Numerical Recipes source code to be posted on any public server," and that translations to another computer language "are 'derivative works' and still subject to our copyright."  Seems silly for code published in a book, but there you go.  It also says that you are allowed to distribute a program that contains the code as long as the code is not visible, so I thought it would be okay for a compiler like Pelles that does not distribute its source code.

This algorithm is not as robust as something like Mersenne Twister, but it seems perfect for rand() --- fast enough and more than good enough for the casual user of random numbers.

[jj2007]

The Numerical Recipes generators are flawed, they don't pass the PractRand suite. For a list of really good PRNGs, see deltarho's work. In particular, PCGII-32 and MsWs are worth a look.

[WesL]

I'm certainly no expert in random number algorithms.  I got interested in this after I wrote a simple program to simulate rolling a pair of dice for a stats class I teach.  The results came out all wacky due to the non-random nature of rand().  I've since learned that for an LCG, the lower order bits are not very random.  I was doing something like "rand() % 6" which depends solely on the lower bits.  (Numerical Recipes specifically warns not to do this.)

I understand that rand() is not really supposed to be for heavy duty use, but it should be sufficient enough that someone could use it for basic stuff without having to have special knowledge of random number algorithms.  So I can't recommend anything in particular.  My main point is that surely a better algorithm could be used.  I'll leave the details to you experts. :-)

[TimoVJL]

Something about of rand