OpenEuphoria

1. Algorithm needed for random number filtering

• Posted by fizzpopsoft Dec 04, 2016
• 1227 views

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!

3. Re: Algorithm needed for random number filtering

• Posted by Spock Dec 04, 2016
• 1218 views

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

5. Re: Algorithm needed for random number filtering

• Posted by petelomax Dec 04, 2016
• 1236 views

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) 
******************************************************************************** 
****************************************************************************** 
******************************************************************************** 
****************************************************************************** 
******************************************************************************* 
***************************************************************************** 
******************************************************************************* 
******************************************************************************** 
******************************************************************************* 
******************************************************************************* 
****************************************************************************** 
****************************************************************************** 
******************************************************************************* 
******************************************************************************* 
****************************************************************************** 
****************************************************************************