1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.
Dismiss Notice

Welcome To SNBForums

SNBForums is a community for anyone who wants to learn about or discuss the latest in wireless routers, network storage and the ins and outs of building and maintaining a small network.

If you'd like to post a question, simply register and have at it!

While you're at it, please check out SmallNetBuilder for product reviews and our famous Router Charts, Ranker and plenty more!

Adventures in random: Nanoseconds

Discussion in 'Asuswrt-Merlin' started by smasher, Nov 17, 2019.

  1. smasher

    smasher Regular Contributor

    Joined:
    Jun 21, 2019
    Messages:
    83
    I was experimenting with the nanosecond counter (/proc/timer_list) from which nanoseconds can be derived by this:
    Code:
    awk 'NR==3 {print $3}' /proc/timer_list | egrep -o '.{9}$'
    After millions of tests, in loops with various delays, the 3rd digit in that string (millisecond; one thousandths of a second) always showed a strong bias towards 6 and 7, away from 0. That bias was observed as strong as 3.989:1 in a test with over 3 million samples, and random delays in the loop of 0-100ms.

    Here's output of "ent -c", looking only at the milliseconds in that test:
    Code:
    *************
    ** Colum 3 :
    Value Char Occurrences Fraction
     48   0       149132   0.047788
     49   1       203716   0.065279
     50   2       224348   0.071890
     51   3       250520   0.080276
     52   4       269017   0.086204
     53   5       328622   0.105303
     54   6       594926   0.190638
     55   7       566125   0.181409
     56   8       290911   0.093219
     57   9       243400   0.077995
    
    Total:       3120717   1.000000
    
    Entropy = 3.187371 bits per byte.
    
    Optimum compression would reduce the size
    of this 3120717 byte file by 60 percent.
    
    Chi square distribution for 3120717 samples is 93308622.59, and randomly
    would exceed this value less than 0.01 percent of the times.
    
    Arithmetic mean value of data bytes is 53.1826 (127.5 = random).
    Monte Carlo value for Pi is 4.000000000 (error 27.32 percent).
    Serial correlation coefficient is -0.029210 (totally uncorrelated = 0.0).
    
    
    nb, the statistics reported above reflect a comparison with an input of raw bytes, not decimal numbers. Ideally, a random set of decimal numbers, of the same size, should look more like this:
    Code:
    Value Char Occurrences Fraction
     48   0       312072   0.100000
     49   1       312072   0.100000
     50   2       312072   0.100000
     51   3       312072   0.100000
     52   4       312072   0.100000
     53   5       312072   0.100000
     54   6       312072   0.100000
     55   7       312071   0.100000
     56   8       312071   0.100000
     57   9       312071   0.100000
    
    Total:       3120717   1.000000
    
    Entropy = 3.321928 bits per byte.
    
    Optimum compression would reduce the size
    of this 3120717 byte file by 58 percent.
    
    Chi square distribution for 3120717 samples is 76769638.20, and randomly
    would exceed this value less than 0.01 percent of the times.
    
    Arithmetic mean value of data bytes is 52.5000 (127.5 = random).
    Monte Carlo value for Pi is 4.000000000 (error 27.32 percent).
    Serial correlation coefficient is 0.000000 (totally uncorrelated = 0.0).
    
    
    In testing, the ten-thousandths of a second showed a weaker bias, which continued through to about the microsecond range. The least significant digit (nanoseconds) showed no bias.

    I saw similar biases in the milliseconds with delays in the loop ranging from zero (full speed) to 0-1000ms random delays. I didn't test with delays longer than 1000ms, because it would take ridiculously long to gather a large enough data-set to run meaningful tests.

    This got me thinking about ways to generate random numbers (and random strings) on this device, and in the near future I'll post a shell-script that I'm very happy with.

    Based on my observations, deriving random numbers from the nanosecond counter is not best practice, on these devices.

    RT-AC68U
    Merlin 384.13
     
    Last edited: Nov 17, 2019
    L&LD likes this.