From: George Spelvin <lkml@sdf.org>
To: Jason@zx2c4.com, lkml@sdf.org
Cc: linux-kernel@vger.kernel.org, tytso@mit.edu
Subject: Re: [RFC PATCH] random: add get_random_max() function
Date: Mon, 25 Mar 2019 01:14:30 GMT [thread overview]
Message-ID: <201903250114.x2P1EUQG004384@sdf.org> (raw)
In-Reply-To: <CAHmME9p3TR6ESekKRQxFsfQe3rZp7T4-4WLOn-SL98zUnAo2DQ@mail.gmail.com>
P.S. The cited paper calls your algorithm the "OpenBSD algorithm"
and has a bunch of benchmarks comparing it to others in Fisher-Yates
shuffles of sizes 1e3..1e9.
Including all overhead (base PRNG, shuffle), it's 3x slower for
32-bit operations and 8x slower for 64-bit up to arrays of size
1e6, after which cache misses slow all algorithms, reducing the
ratio.
If you want a faster division-based agorithm, the "Java algorithm"
does 1+retries divides:
unsigned long java(unsigned long s)
{
unsigned long x, r;
do {
x = random_integer();
r = x % s;
} while (x - r > -s);
return r;
}
next prev parent reply other threads:[~2019-03-25 1:16 UTC|newest]
Thread overview: 4+ messages / expand[flat|nested] mbox.gz Atom feed top
[not found] <201903241244.x2OCiL8P011277@sdf.org>
2019-03-24 20:47 ` [RFC PATCH] random: add get_random_max() function Jason A. Donenfeld
2019-03-25 0:28 ` George Spelvin
2019-03-25 1:14 ` George Spelvin [this message]
[not found] ` <201903270655.x2R6tDjo020894@sdf.org>
2019-03-28 10:00 ` [RFC PATCH v2] " George Spelvin
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=201903250114.x2P1EUQG004384@sdf.org \
--to=lkml@sdf.org \
--cc=Jason@zx2c4.com \
--cc=linux-kernel@vger.kernel.org \
--cc=tytso@mit.edu \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).