NetBSD Problem Report #38883

From martin@duskware.de  Sat Jun  7 12:13:47 2008
Return-Path: <martin@duskware.de>
Received: from mail.netbsd.org (mail.netbsd.org [204.152.190.11])
	by narn.NetBSD.org (Postfix) with ESMTP id 15AC763B8BC
	for <gnats-bugs@gnats.netbsd.org>; Sat,  7 Jun 2008 12:13:47 +0000 (UTC)
Message-Id: <20080607063229.4E69163B8BC@narn.NetBSD.org>
Date: Sat,  7 Jun 2008 06:32:29 +0000 (UTC)
From: 10.50@free.fr
Reply-To: 10.50@free.fr
To: netbsd-bugs-owner@NetBSD.org
Subject: Replace the algorithm used by random (3) by the Mersenne Twister (mertwist.c)
X-Send-Pr-Version: www-1.0

>Number:         38883
>Category:       lib
>Synopsis:       Replace the algorithm used by random (3) by the Mersenne Twister (mertwist.c)
>Confidential:   no
>Severity:       non-critical
>Priority:       low
>Responsible:    lib-bug-people
>State:          closed
>Class:          change-request
>Submitter-Id:   net
>Arrival-Date:   Sat Jun 07 12:15:00 +0000 2008
>Closed-Date:    Sat Dec 31 05:08:05 +0000 2022
>Last-Modified:  Sat Dec 31 05:08:05 +0000 2022
>Originator:     Vincent Habchi
>Release:        current
>Organization:
>Environment:
>Description:
The Mersenne Twister algorithm has a virtually infinite period, a very smooth distribution and meets all but the most stringent requirements (read: cryptographic use) for a pseudorandom (PR) generator. Furthermore it is fast and already implemented in src/sys/lib/libkern/mertwist.c. It is therefore superior to the current random (3) algorithm we use.

Thus, why not implement it as the standard algorithm for random (3) group of calls?


>How-To-Repeat:

>Fix:

>Release-Note:

>Audit-Trail:
From: David Holland <dholland-bugs@netbsd.org>
To: 10.50@free.fr, gnats-bugs@netbsd.org
Cc: lib-bug-people@netbsd.org, gnats-admin@netbsd.org,
	netbsd-bugs@netbsd.org
Subject: Re: lib/38883: Replace the algorithm used by random (3) by the
	Mersenne Twister (mertwist.c)
Date: Mon, 25 Aug 2008 03:23:54 +0000

 On Sat, Jun 07, 2008 at 12:15:01PM +0000, 10.50@free.fr wrote:
  > The Mersenne Twister algorithm has a virtually infinite period, a
  > very smooth distribution and meets all but the most stringent
  > requirements (read: cryptographic use) for a pseudorandom (PR)
  > generator. Furthermore it is fast and already implemented in
  > src/sys/lib/libkern/mertwist.c. It is therefore superior to the
  > current random (3) algorithm we use.
  > 
  > Thus, why not implement it as the standard algorithm for random (3)
  > group of calls?

 We can't (or at least shouldn't) do this because it would break the
 initstate() and setstate() interface to random(3).

 If it's vastly better, it might be worth that breakage, but that's not
 the impression I have.

 -- 
 David A. Holland
 dholland@netbsd.org

From: Alan Barrett <apb@cequrux.com>
To: gnats-bugs@NetBSD.org
Cc: netbsd-bugs@NetBSD.org
Subject: Re: lib/38883: Replace the algorithm used by random (3) by the
	Mersenne Twister (mertwist.c)
Date: Mon, 25 Aug 2008 12:22:56 +0200

 On Mon, 25 Aug 2008, David Holland wrote:
 >   > Thus, why not implement it as the standard algorithm for random (3)
 >   > group of calls?
 >  
 >  We can't (or at least shouldn't) do this because it would break the
 >  initstate() and setstate() interface to random(3).

 Do people really expect the kind of repatability offered by the
 initstate/getstate interface to persist across operating system
 upgrades?  In other words, do we guarantee that values returned by
 initstate befoer an upgrade may be passed to setstate after an upgrade?

 Even if we do need to retain this level of compatibility, there seem
 to be enough unused values in the first (int) of the state array that
 we could encode which algorithm is used.  Old algorithms would still
 have to work as if the old value of MAX_TYPES were retained, but it's
 nevertheless possible to add new algotithms.

 --apb (Alan Barrett)

From: David Holland <dholland-bugs@netbsd.org>
To: Alan Barrett <apb@cequrux.com>
Cc: gnats-bugs@NetBSD.org, netbsd-bugs@NetBSD.org
Subject: Re: lib/38883: Replace the algorithm used by random (3) by the
	Mersenne Twister (mertwist.c)
Date: Sun, 31 Aug 2008 19:00:51 +0000

 On Mon, Aug 25, 2008 at 12:22:56PM +0200, Alan Barrett wrote:
  > On Mon, 25 Aug 2008, David Holland wrote:
  > >  > Thus, why not implement it as the standard algorithm for random (3)
  > >  > group of calls?
  > >  
  > >  We can't (or at least shouldn't) do this because it would break the
  > >  initstate() and setstate() interface to random(3).
  > 
  > Do people really expect the kind of repatability offered by the
  > initstate/getstate interface to persist across operating system
  > upgrades?  In other words, do we guarantee that values returned by
  > initstate befoer an upgrade may be passed to setstate after an upgrade?

 I'm not sure. I once came very close to writing code that did, but
 that was a long time ago and used getstate() as well as setstate(),
 which we don't seem to support.

  > Even if we do need to retain this level of compatibility, there seem
  > to be enough unused values in the first (int) of the state array that
  > we could encode which algorithm is used.  Old algorithms would still
  > have to work as if the old value of MAX_TYPES were retained, but it's
  > nevertheless possible to add new algotithms.

 That sounds promising though, provided that it's actually worth
 deploying another algorithm.

 -- 
 David A. Holland
 dholland@netbsd.org

State-Changed-From-To: open->closed
State-Changed-By: dholland@NetBSD.org
State-Changed-When: Sat, 31 Dec 2022 05:08:05 +0000
State-Changed-Why:
I don't think there's ever really been any reason to think that the
Mersenne Twister is any better than the random(3) we already have,
and I vaguely recall some situation some years back where it turned
out to be worse. Anyway, changing the implementation would create a
bunch of compat headaches and it's not worth doing without a clear
benefit.


>Unformatted:

NetBSD Home
NetBSD PR Database Search

(Contact us) $NetBSD: query-full-pr,v 1.47 2022/09/11 19:34:41 kim Exp $
$NetBSD: gnats_config.sh,v 1.9 2014/08/02 14:16:04 spz Exp $
Copyright © 1994-2022 The NetBSD Foundation, Inc. ALL RIGHTS RESERVED.