Re: OT: RFC, PRNG

cr88192 wrote:

this algo seems confusing, and seems to work in reverse, so I am not
certain.


Actually, I noticed it was incorrect, and had a small bug besides that.
Running a fixed version now, but it it's awkwardly slow. (Though I
expect the period to be something too large to find with such a simple
method.)

However, the fact that xor is used (instead of addition) concerns me a
bit as it means that the state can only contain xor-sums of the values
in the initial state. Which initial state values are used in a specific
generated value is constant per stream position. This is something I
actually did verify, and wrote a small app to find which initial state
values are xored together in a particular stream position.

This is a quick verification tool, it can directly calculate the 10000th
generated number without generating the ones before it, and quite a few
initial state values are obviously irrelevant for generating it.

#include <stdio.h>
#include <time.h>
#include <stdint.h>

uint32_t origstate[128];
uint32_t basm_rand_state[128];
uint32_t basm_rand_pos=0;

uint32_t basm_rand()
{
int i, j, k;

i=basm_rand_pos;
j=(i+127-61)%127;
k=(i+127-31)%127;
basm_rand_state[i]^=basm_rand_state[j];
basm_rand_state[i]^=basm_rand_state[k];
basm_rand_pos=(i+1)%127;

return(basm_rand_state[i]);
}

int xorthing[127]=
{
1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0,
0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1,
0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0,
0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1,
1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1,
1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0,
0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1,
0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
};

int main()
{
uint32_t thingy,thingy2;
int i,b;
srand(time(0));

for(i=0;i<128;i++)
basm_rand_state[i]=rand()+(rand()<<7)+(rand()<<15)+(rand()<<21);
memcpy(origstate,basm_rand_state,sizeof(basm_rand_state));

for(i=0;i<10000;i++)
thingy=basm_rand();

thingy2=0;
for(i=0;i<127;i++)
if(xorthing[i])
thingy2^=origstate[i];

if(thingy==thingy2)
printf("they do equal");

return 0;
}

Also, here's the tool for finding which initial state values affect a
particular generated value:

#include <stdio.h>

#define num_item 10000

int state[128][128];

int main()
{
int i,b;

memset(state,0,sizeof(state));
for(i=0;i<128;i++)
state[i][i]=1;

for(i=0;i<num_item;i++)
{
for(b=0;b<127;b++)
{
state[i%127][b]^=state[(i+66)%127][b];
state[i%127][b]^=state[(i+96)%127][b];
}
}
printf("{");
for(b=0;b<127;b++)
printf("%2u,",state[(i-1)%127][b]);
printf("}\n");

return 0;
}
.

Relevant Pages

  • Re: basics
    ... >int main ... You are using the wrong form of seekg so that it is unclear where the ... file pointer is after this function call. ... ios_base::pos_type, a stream position. ...
    (alt.comp.lang.learn.c-cpp)
  • Re: ? Modeless Dialog: No OnInitDialog, No Template (No Controls)
    ... and therefore using it is incorrect. ... BOOL CDialog::Create ... int x, int y, int nWidth, int nHeight, ... HWND hWndParent, HMENU nIDorHMenu, LPVOID lpParam) ...
    (microsoft.public.vc.mfc)
  • Re: help w/ c/c++ problem
    ... Standard REQUIRES main to return an int. ... Then it is still incorrect. ... The function called at program startup is named main. ...
    (comp.lang.c)
  • Re: Problems with Harbison & Steele
    ... > Yesterday I embarrassed myself on sci.crypt with some incorrect C ... and mapping characters.166) In all cases the argument is an int, ... value of which shall be representable as an unsigned char or shall equal ... The function takes an int as input, but the value should either be EOF ...
    (comp.lang.c)
  • Re: Segmentation fault when compiled binary is executed
    ... int mainisn't incorrect, ... Ending mainwith a call to exitisn't incorrect ... Casting the return value of malloc() is ... you might read the C FAQ along with the resource you cited: ...
    (comp.lang.c)