simple 16-bit random number generator

[Bee-9]

simple 16-bit random number generator

Do you have a favorite?

I need small numbers randomized each iteration within a function. The
following seems to work well for application.

Converted the forth code:

\ 16-bit random number generator, Leo Brodie 'Starting Forth'
VARIABLE RND  HERE RND ! ( seed )
: RANDOM ( -- u ) RND @ 31421 * 6927 + DUP RND ! ;
: CHOOSE ( u -- u ) RANDOM UM* SWAP DROP ; \ 0 u within

To a vim script:

let rnd = localtime() % 0x10000

function! Random()
  let g:rnd = (g:rnd * 31421 + 6927) % 0x10000
  return g:rnd
endfun

function! Choose(n) " 0 n within
  return (Random() * a:n) / 0x10000
endfun

--
You received this message from the "vim_use" maillist.
Do not top-post! Type your reply below the text you are replying to.
For more information, visit http://www.vim.org/maillist.php

[John Little-4]

On Sep 18, 3:05 am, Bee <[hidden email]> wrote:
> simple 16-bit random number generator
>
> Do you have a favorite?

Yeah, I know it's not what you've asked for, but I've been stung more
than once by use of "simple" random numbers and so I try to go much
further than "simple" if something better is handy, such as the
standard library.  The following took less than the time to type this
post:

function! Random()
    if !exists("s:seeded")
        call libcallnr("libc.so.6", "srand", localtime() )
        let s:seeded = 1
    endif
    return libcallnr("libc.so.6", "rand", 0 ) % 65536
endfun

You might have to adjust that "libc.so.6" for your OS.

Regards, John

--
You received this message from the "vim_use" maillist.
Do not top-post! Type your reply below the text you are replying to.
For more information, visit http://www.vim.org/maillist.php

[Bee-9]

On Sep 17, 3:09 pm, John Little <[hidden email]> wrote:

> On Sep 18, 3:05 am, Bee <[hidden email]> wrote:
>
> > simple 16-bit random number generator
>
> > Do you have a favorite?
>
> Yeah, I know it's not what you've asked for, but I've been stung more
> than once by use of "simple" random numbers and so I try to go much
> further than "simple" if something better is handy, such as the
> standard library.  The following took less than the time to type this
> post:
>
> function! Random()
>     if !exists("s:seeded")
>         call libcallnr("libc.so.6", "srand", localtime() )
>         let s:seeded = 1
>     endif
>     return libcallnr("libc.so.6", "rand", 0 ) % 65536
> endfun
>
> You might have to adjust that "libc.so.6" for your OS.

I like the idea of system utilities, but... Not available on this Mac.

How have you been "stung"?

Where/what is libc.so.6 ?

The rng I converted from forth to vim has a good distribution.

Anyone have a way of "binning" both?

--
You received this message from the "vim_use" maillist.
Do not top-post! Type your reply below the text you are replying to.
For more information, visit http://www.vim.org/maillist.php

[Kazuo Teramoto-2]

On Fri, Sep 17, 2010 at 12:05 PM, Bee <[hidden email]> wrote:
> simple 16-bit random number generator
>

If you compiled your vim with python support you can use the python
random lib, its use the Mersenne twister to generate random numbers
and is very good (MT is very fast too, I use a optimized C code for my
Monte Carlo simulations)

Something like this:

function! Random()
   python from random import randint
   python from vim import command
   python command("return %d" % randint(0,65536))
endfun

Regards,
Kazuo
--
«Dans la vie, rien n'est à craindre, tout est à comprendre»
Marie Sklodowska Curie.

--
You received this message from the "vim_use" maillist.
Do not top-post! Type your reply below the text you are replying to.
For more information, visit http://www.vim.org/maillist.php

[John Little-4]

> > You might have to adjust that "libc.so.6" for your OS.
>
> I like the idea of system utilities, but... Not available on this Mac.

I'm sure the standard library is available on Macs, but what
"dynamically linked libraries" are on Macs I've no idea, except that
OS X is BSD derived I thought.  Have a look for something like /lib/
libc* or /usr/lib/libc*.

> How have you been "stung"?

In one case test coverage was compromised by the random numbers
repeating after 65536 numbers; each test used some power of 2, like 64
or 128.   In another integer to float to integer conversions lost
bits, causing password generation code to repeat sequences of
passwords after a variable number of passwords; once you'd got a
password in one of the known sequences you could predict every
password thereafter.

Regards, John

--
You received this message from the "vim_use" maillist.
Do not top-post! Type your reply below the text you are replying to.
For more information, visit http://www.vim.org/maillist.php

[Milo]

On 09/18/2010 09:42 AM, John Little wrote:
>
>>> You might have to adjust that "libc.so.6" for your OS.
>>
>> I like the idea of system utilities, but... Not available on this Mac.
>
> I'm sure the standard library is available on Macs, but what
> "dynamically linked libraries" are on Macs I've no idea, except that
> OS X is BSD derived I thought.  Have a look for something like /lib/
> libc* or /usr/lib/libc*.

Exactly. On GNU/Linux platform it's easy to check dynamic dependencies
using ldd. On OS X try otool.

>> How have you been "stung"?
>
> In one case test coverage was compromised by the random numbers
> repeating after 65536 numbers; each test used some power of 2, like 64
> or 128.   In another integer to float to integer conversions lost
> bits, causing password generation code to repeat sequences of
> passwords after a variable number of passwords; once you'd got a
> password in one of the known sequences you could predict every
> password thereafter.
>
> Regards, John
>

Well, you can always think about using some cipher/hash to generate
piece of data with good entropy. Most of modern algos (AES, Camellia,
Twofish, Serpent) are doing good job here. Data encrypted using them is
passing many of randomness tests.

--
Regards,
Milo

--
You received this message from the "vim_use" maillist.
Do not top-post! Type your reply below the text you are replying to.
For more information, visit http://www.vim.org/maillist.php

[Christian Brabandt]

Hi John!

On Fr, 17 Sep 2010, John Little wrote:

> On Sep 18, 3:05 am, Bee <[hidden email]> wrote:
> function! Random()
>     if !exists("s:seeded")
>         call libcallnr("libc.so.6", "srand", localtime() )
>         let s:seeded = 1
>     endif
>     return libcallnr("libc.so.6", "rand", 0 ) % 65536
> endfun
>
> You might have to adjust that "libc.so.6" for your OS.

This reminds me, that I have wished a rand() function for very long.

So here is a very simple patch. It doesn't add much to the footprint. I
am not sure, how portable the code is, though:


--- a/runtime/doc/eval.txt
+++ b/runtime/doc/eval.txt
@@ -4522,6 +4522,9 @@
                This can be used to avoid some things that would remove the
                popup menu.

+rand()                                         *rand()*
+               Returns a pseudo-random positive integer Number.
+
                                                        *E726* *E727*
 range({expr} [, {max} [, {stride}]])                           *range()*
                Returns a |List| with Numbers:
diff --git a/src/eval.c b/src/eval.c
--- a/src/eval.c
+++ b/src/eval.c
@@ -653,6 +653,7 @@
 static void f_prevnonblank __ARGS((typval_T *argvars, typval_T *rettv));
 static void f_printf __ARGS((typval_T *argvars, typval_T *rettv));
 static void f_pumvisible __ARGS((typval_T *argvars, typval_T *rettv));
+static void f_rand __ARGS((typval_T *argvars, typval_T *rettv));
 static void f_range __ARGS((typval_T *argvars, typval_T *rettv));
 static void f_readfile __ARGS((typval_T *argvars, typval_T *rettv));
 static void f_reltime __ARGS((typval_T *argvars, typval_T *rettv));
@@ -7829,6 +7830,7 @@
     {"prevnonblank",   1, 1, f_prevnonblank},
     {"printf",         2, 19, f_printf},
     {"pumvisible",     0, 0, f_pumvisible},
+    {"rand",           0, 0, f_rand},
     {"range",          1, 3, f_range},
     {"readfile",       1, 3, f_readfile},
     {"reltime",                0, 2, f_reltime},
@@ -14224,6 +14226,18 @@
        rettv->vval.v_number = 1;
 #endif
 }
+/*
+ * "rand()" function
+ */
+    static void
+f_rand(argvars, rettv)
+    typval_T   *argvars;
+    typval_T   *rettv;
+{
+    rettv->v_type = VAR_NUMBER;
+    srand((varnumber_T)time(NULL));
+    rettv->vval.v_number = rand();
+}


regards,
Christian

--
You received this message from the "vim_use" maillist.
Do not top-post! Type your reply below the text you are replying to.
For more information, visit http://www.vim.org/maillist.php

[Charles E Campbell Jr]

Bee wrote:
> simple 16-bit random number generator
>
> Do you have a favorite?
>
> I need small numbers randomized each iteration within a function. The
> following seems to work well for application.
>
>  

Rndm.vim, available at
http://mysite.verizon.net/astronaut/vim/index.html#RNDM, passes Knuth's
test pretty well.  From Rndm's help:


The pseudo-random number generator used herein was developed at MIT.

I used D. Knuth's ent program (http://www.fourmilab.ch/random/) and
generated
one million (1,000,000) values using a C program variant: >
    rv= Rndm()/3906.25   (which divides one million into 256 equal regions)
and converted each value into bytes.  The report from Knuth's ent program:

    Entropy = 7.999825 bits per byte.

    Optimum compression would reduce the size
    of this 1000000 byte file by 0 percent.

    Chi square distribution for 1000000 samples is 242.41, and randomly
    would exceed this value 70.44 percent of the times.

    Arithmetic mean value of data bytes is 127.5553 (127.5 = random).
    Monte Carlo value for Pi is 3.135732543 (error 0.19 percent).
    Serial correlation coefficient is 0.001313 (totally uncorrelated = 0.0).

These values are quite good (a true random source, for example, had a
chi square distribution value of 249.51, for example -- from Knuth's page).

Regards,
Chip Campbell

--
You received this message from the "vim_use" maillist.
Do not top-post! Type your reply below the text you are replying to.
For more information, visit http://www.vim.org/maillist.php

[Christian Brabandt]

Hi Shlomi!

On Sa, 18 Sep 2010, Shlomi Fish wrote:

> Hi Christian,
>
> On Saturday 18 September 2010 14:49:29 Christian Brabandt wrote:
> > Hi John!
> >
> > On Fr, 17 Sep 2010, John Little wrote:
> > > On Sep 18, 3:05 am, Bee <[hidden email]> wrote:
> > > function! Random()
> > >
> > >     if !exists("s:seeded")
> > >    
> > >         call libcallnr("libc.so.6", "srand", localtime() )
> > >         let s:seeded = 1
> > >    
> > >     endif
> > >     return libcallnr("libc.so.6", "rand", 0 ) % 65536
> > >
> > > endfun
> > >
> > > You might have to adjust that "libc.so.6" for your OS.
> >
> > This reminds me, that I have wished a rand() function for very long.
> >
> > So here is a very simple patch. It doesn't add much to the footprint. I
> > am not sure, how portable the code is, though:
>
> According to man rand on Linux:
>
> {{{
> The  functions  rand()  and  srand() conform to SVr4, 4.3BSD, C89, C99,
> POSIX.1-2001.    The   function   rand_r()   is   from    POSIX.1-2001.
> POSIX.1-2008 marks rand_r() as obsolete.
> }}}
>
> And man time:
>
> {{{
> CONFORMING TO
>        SVr4, 4.3BSD, C89, C99, POSIX.1-2001.  POSIX does not specify any error
>        conditions.
> }}}

I know. But I don't know, whether this applies to all Windows versions.

>
> However, see below:
>
[...]
>
> This is wrong. You're calling srand with the current time on every invocation
> which will:
>
> 1. Yield non-predictable and non-reproducible results.
>
> 2. If two calls are done one right after the other within the same wall-clock
> second, it will yield the exact same value.
 
True. I thought, this would be good enough[™] for an editor.

Well, attached is an updated patch, that allows you to seed the random
generator and returns values between 0 and 32767

> A better idea would be to provide a binding for srand as well, so the
> user can set a seed and get predictable results. An even better idea
> may be to provide a consistent pseudo-random-number generator which
> will yield the same results on all platforms. See:
>
> http://www.haifux.org/lectures/79/

I don't know much about windows and looking at the slides, portability
seems to be a serious problem.

regards,
Christian

--
You received this message from the "vim_use" maillist.
Do not top-post! Type your reply below the text you are replying to.
For more information, visit http://www.vim.org/maillist.php