simple 16-bit random number generator
Bee
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
John Little
> simple 16-bit random number generator
>
> Do you have a favorite?
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
Bee
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?
Kazuo Teramoto
> 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.
John Little
> > 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.
"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"?
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
Milo
>
>>> 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
Christian Brabandt
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
Charles E Campbell Jr
> 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
Christian Brabandt
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 <200...@calcentral.com> 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