1. Algorithm needed for random number filtering

Hello,
I have an Arduino that uses some transistors as avalanche noise generators.
The Arduino uses analog to digital converters, to take the noise and produce hopefully random numbers in the range 0-1024. But, there is a distinct prevalence of randoms in a range that is influenced by the voltage supplied to the noise generators. Pretty much a bell curve in the middle of the range, and a abberation of massive amounts of zeros.
I have used two noise generators with two inputs, then add the two numbers to make a number 0-2048 to try flatten the bell but its not working as well as hoped. I also drop the zeros.

My current method is to discard all numbers with samples above a certain limit, then add some samples to be the same as samples just less than the limit, giving hopefully 256 or more numbers with samples in a close range. But I have to manually tweak that limit value to get the 256. Is there a programmatical way to determine the limit by a first pass through the data?
My maths is hopeless BTW, google is no help.

I need to have a method of reading the random data, to determine the limit value, instead of a hit and miss approach. Google gives examples that are waaaay beyond my math!

new topic     » topic index » view message » categorize

2. Re: Algorithm needed for random number filtering

My main code is below, but here is a verbal example : Say you have 120 samples of the number 1, 50 samples of the number 2, 50 of 3, 100 of 4, 70 of 5.
I would set the limit "maxi" to 100; that would allow 4 as valid, and discard 1; then add the occasions of 2 and 3 (table lookup) to give samples of 2. 5 would need to be discarded as there is nothing left to add the missing 30 to. Note I could not take some of the samples off 1 and add to 5, because then it would not be random.
I have a few files of 470K of randoms to process.

procedure tagit() 
   integer needed, stillok, pc 
   integer i1, i2, i3 
   sequence s1, s2, s3, s4, s5, s6, s7, s8, s9 
   i1 = 0 
   rc = 1 
   while i1 < 2048 do  
   	 i1 = i1 + 1 
   	 if tbl[i1] > 0 then   -- this one part of the 256 
   	 	  needed = maxi - tbl[i1]  -- data is loaded in this table 
   	 	  pc = floor(needed / 100) * vari -- percentage 
   	 	  stillok = needed - pc 
   	 	  i2 = 0 
   	 	  while i2 < length(leftovers) do -- leftovers is the distribution table 
   	 	  	 i2 = i2 + 1  
   	 	  	 s1 = leftovers[i2] 
   	 	  	 s2 = s1[001..006] -- number of samples 
   	 	  	 s3 = s1[007..010] -- number identifier 
   	 	  	 s4 = value(s2) 
   	 	  	 i3 = s4[2] 
   	 	  	 if i3 < needed then  
   	 	  	 	  if i3 > stillok then  
   	 	  	 	  	 rc = 0 
   	 	  	 	  	 s5 = sprintf("%04d",{i1})  
   	 	  	 	  	 tbl[i1] = tbl[i1] + i3   -- consolidate 
   	 	  	 	  	 s6 = sprintf("%06d",{tbl[i1]}) 
   	 	  	 	  	 leftovers[i2] = "0000000000"  -- set for removal 
   	 	  	 	  	 s8 = lookup[i1] 
   	 	  	 	  	 if length(s8) = 10 then  
   	 	  	 	  	    s7 = s5 & s6 & s3 
   	 	  	 	  	    lookup[i1] = s7 
   	 	  	 	  	    exit 
   	 	  	 	  	   else  
   	 	  	 	  	   	s9 = s8[11..length(s8)] 
   	 	  	 	  	   	s7 = s5 & s6 & s9 & s3  
   	 	  	 	  	   	lookup[i1] = s7 
   	 	  	 	  	   	exit 
   	 	  	 	  	 end if 
   	 	  	 	  end if 
   	 	  	 	end if 
   	 	  	end while 
   	 	 end if  
   	 end while	  
end procedure 	 
new topic     » goto parent     » topic index » view message » categorize

3. Re: Algorithm needed for random number filtering

Not sure if I understand the problem correctly. You have HW generated noise stored in files and want to filter it that so that what is left is pure randomness?

I would create a count array as large as the desired range (eg, length 1024 if you want values 0-1023) and then fill up that array by reading the next value in the file and incrementing its index. At each iteration the distribution for that index is checked to determine that it remains within a boundary that you set. if the distribution is good its count in the array is incremented and the value is recorded in the output sequence. If any value would breach the boundary that value is repeatedly added with the Golden Ratio of the array length and tried again until it succeeds. Even a string of completely null values will still produce a modestly random output. The only tricky bit really is computing the distribution at each iteration.

So, this idea doesn't discard any values but just transforms any errant ones into something more acceptable.

Another idea would be to run a known k2ypt0 algorithm in counter mode (ie, 0, 1, 2, 3..) and just add/xor the output with the HW values. you could even start the counter with a large random number and use an odd large step factor (eg, GR x algo bitsize). Well there are lots of possibilities.

Some might say the first rule of x2yt092aphy is "Don't roll your own" but you really can if start with a sensible base.

Spock

new topic     » goto parent     » topic index » view message » categorize

4. Re: Algorithm needed for random number filtering

Better yet:
Randomize between 0 and 8192 and divide by 8, then you get lots of samples in the middle of the bell
or 16384 and divide by 16 ofc

new topic     » goto parent     » topic index » view message » categorize

5. Re: Algorithm needed for random number filtering

fizzpopsoft said...

to try flatten the bell but its not working

Here is a very simple demonstration of Von Neuman's technique.
To keep things simple I am using 4 bit numbers, it should not be difficult to extend to any (even) power of 2.
First, I generate 2,000,000 random numbers and record the initial distribution (idist).
I average each consecutive pair to create a bell curve distribution (bdist).
To remove bias, sample each (non overlapping) pair of bits: make 01 -> 1, 10 -> 0, and ignore 00 and 11. (rdist)

sequence idist = repeat(0,16), 
         bdist = repeat(0,16), 
         rdist = repeat(0,16) 
 
integer bits = 0 
integer r1, r2, r3 = 0 
for i=1 to 1000000 do 
    -- initial distribution 
    r1 = rand(16) 
    idist[r1] += 1 
    r2 = rand(16) 
    idist[r2] += 1 
    -- make a bell curve distribution 
    r1 = round((r1+r2)/2) 
    bdist[r1] += 1 
    -- remove bias 
    for j=1 to 1 do 
        r2 = and_bits(r1,3) 
        if r2=1 
        or r2=2 then 
            r3 = r3*2+and_bits(r2,1) 
            bits += 1 
            if bits=4 then 
                rdist[r3+1] += 1 
                r3 = 0 
                bits = 0 
            end if 
        end if 
        -- (must use 0..15 not 1..16 here, hence the -1/+1) 
        r1 = floor((r1-1)/4)+1 
    end for 
end for 
  
procedure showdist(sequence d) 
integer di, maxdi = 0, tdi = 0 
    for i=1 to length(d) do 
        di = d[i] 
        if di>maxdi then 
            maxdi = di 
        end if 
        tdi += di 
    end for 
    printf(1,"(%d samples)\n",tdi) 
    for i=1 to length(d) do 
        printf(1,"%s\n",{repeat('*',round((d[i]/maxdi)*80))}) 
    end for 
end procedure 
 
puts(1,"initial\n") 
showdist(idist) 
puts(1,"biased\n") 
showdist(bdist) 
puts(1,"recovered\n") 
showdist(rdist) 

output:

initial 
(2000000 samples) 
******************************************************************************** 
******************************************************************************* 
******************************************************************************** 
******************************************************************************** 
******************************************************************************** 
******************************************************************************** 
******************************************************************************** 
******************************************************************************* 
******************************************************************************** 
******************************************************************************** 
******************************************************************************* 
******************************************************************************* 
******************************************************************************** 
******************************************************************************** 
******************************************************************************* 
******************************************************************************** 
biased 
(1000000 samples) 
*** 
************* 
*********************** 
********************************** 
******************************************** 
******************************************************* 
***************************************************************** 
*************************************************************************** 
******************************************************************************** 
********************************************************************** 
************************************************************ 
************************************************* 
*************************************** 
**************************** 
****************** 
******** 
recovered 
(125088 samples) 
******************************************************************************** 
****************************************************************************** 
******************************************************************************** 
****************************************************************************** 
******************************************************************************* 
***************************************************************************** 
******************************************************************************* 
******************************************************************************** 
******************************************************************************* 
******************************************************************************* 
****************************************************************************** 
****************************************************************************** 
******************************************************************************* 
******************************************************************************* 
****************************************************************************** 
**************************************************************************** 
EDIT: corrected algorithm

new topic     » goto parent     » topic index » view message » categorize

6. Re: Algorithm needed for random number filtering

Thanks gents,
I will test different methods then put the results through known randomness tests.

new topic     » goto parent     » topic index » view message » categorize

Search



Quick Links

User menu

Not signed in.

Misc Menu