[Rd] Weakness in Knuth-TAOCP RNG (fwd) (PR#1336)

schutz@wehi.edu.au schutz@wehi.edu.au
Fri, 1 Mar 2002 07:06:38 +0100 (MET)


  This message is in MIME format.  The first part should be readable text,
  while the remaining parts are likely unreadable without MIME-aware tools.
  Send mail to mime@docserver.cac.washington.edu for more info.

---559023410-1141662977-1014960253=:3119
Content-Type: TEXT/PLAIN; CHARSET=iso-8859-1
Content-Transfer-Encoding: QUOTED-PRINTABLE
Content-ID: <Pine.SOL.4.33.0203011649142.3119@unix09.wehi.edu.au>

Don Knuth recently updated its RNG, following the discovery of a
weakness in the seed initialisation (see
http://Sunburn.Stanford.EDU/~knuth/news02.html), so I believe that the
corresponding code in R should be updated as well. If it may be usefull,
I attach a patch to do the change.

Notes:

  - only a few lines of code have really changed, but the order of the
    functions has changed in Knuth's original code, so the patch is
    longer than it should really be;
  - Despite Knuth's request that no change should be made to the code,
    the present R code (1.5.0-devel and previous) contains a change (the
    line "long ran_x[KK];" is commented, and ran_x is defined elsewhere
    in the program). The patch contains the _same_ change; I let you
    decide if this is acceptable in regard to Knuth's request.

Frederic
--
Fr=E9d=E9ric SCH=DCTZ                      email: schutz@wehi.edu.au
Genetics and Bioinformatics Group
The Walter and Eliza Hall Institute of Medical Research
Phone: +61 3 9345 2627               Fax: +61 3 9347 0852
Post Office
Royal Melbourne Hospital, 3050
Victoria, Australia

---559023410-1141662977-1014960253=:3119
Content-Type: TEXT/PLAIN; CHARSET=US-ASCII; NAME="RNG.c.patch"
Content-Transfer-Encoding: BASE64
Content-ID: <Pine.SOL.4.33.0203011624131.3119@unix09.wehi.edu.au>
Content-Description: 
Content-Disposition: ATTACHMENT; FILENAME="RNG.c.patch"

LS0tIFJORy5jLm9sZAlGcmkgTWFyICAxIDA4OjQyOjQ1IDIwMDINCisrKyBS
TkcuYwlGcmkgTWFyICAxIDE0OjI2OjA4IDIwMDINCkBAIC01NDMsNiArNTQz
LDcgQEANCiAjZGVmaW5lIHJhbl94ICAgICAgICAgICAgIGR1bW15DQogDQog
LyogPT09PT09PT09PT09PT09PT09PSAgS251dGggVEFPQ1AgPT09PT09PT09
PT09PT09PT09PT09PT09PT0gKi8NCisvKiBGcm9tIGh0dHA6Ly93d3ctY3Mt
ZmFjdWx0eS5TdGFuZm9yZC5FRFUvfmtudXRoL3Byb2dyYW1zL3JuZy5jICov
DQogDQogICAgICAgICAgLyogUGxlYXNlIGRvIE5PVCBhbHRlciB0aGlzIHBh
cnQgb2YgdGhlIGNvZGUgKi8NCiANCkBAIC01NTEsMTUgKzU1MiwxNyBAQA0K
ICAqICAgIEl0IGlzIGV4cGxhaW5lZCBpbiBTZW1pbnVtZXJpY2FsIEFsZ29y
aXRobXMsIDNyZCBlZGl0aW9uLCBTZWN0aW9uIDMuNg0KICAqICAgIChvciBp
biB0aGUgZXJyYXRhIHRvIHRoZSAybmQgZWRpdGlvbiAtLS0gc2VlDQogICog
ICAgICAgIGh0dHA6Ly93d3ctY3MtZmFjdWx0eS5zdGFuZm9yZC5lZHUvfmtu
dXRoL3Rhb2NwLmh0bWwNCi0gKiAgICBpbiB0aGUgY2hhbmdlcyB0byBwYWdl
cyAxNzEgYW5kIGZvbGxvd2luZyBvZiBWb2x1bWUgMikuICAgICAgICAgICAg
ICAqLw0KKyAqICAgIGluIHRoZSBjaGFuZ2VzIHRvIFZvbHVtZSAyIG9uIHBh
Z2VzIDE3MSBhbmQgZm9sbG93aW5nKS4gICAgICAgICAgICAgICovDQorDQor
LyogICAgTi5CLiBUaGUgTU9ESUZJQ0FUSU9OUyBpbnRyb2R1Y2VkIGluIHRo
ZSA5dGggcHJpbnRpbmcgKDIwMDIpIGFyZQ0KKyAgICAgIGluY2x1ZGVkIGhl
cmU7IHRoZXJlJ3Mgbm8gYmFja3dhcmRzIGNvbXBhdGliaWxpdHkgd2l0aCB0
aGUgb3JpZ2luYWwuICovDQogDQogLyogICAgSWYgeW91IGZpbmQgYW55IGJ1
Z3MsIHBsZWFzZSByZXBvcnQgdGhlbSBpbW1lZGlhdGVseSB0bw0KICAqICAg
ICAgICAgICAgICAgICB0YW9jcEBjcy5zdGFuZm9yZC5lZHUNCiAgKiAgICAo
YW5kIHlvdSB3aWxsIGJlIHJld2FyZGVkIGlmIHRoZSBidWcgaXMgZ2VudWlu
ZSkuIFRoYW5rcyEgICAgICAgICAgICAqLw0KIA0KIC8qKioqKioqKioqKiog
c2VlIHRoZSBib29rIGZvciBleHBsYW5hdGlvbnMgYW5kIGNhdmVhdHMhICoq
KioqKioqKioqKioqKioqKiovDQotDQotLyogdGhlIG9sZCBDIGNhbGxpbmcg
Y29udmVudGlvbnMgYXJlIHVzZWQgaGVyZSwgZm9yIHJlYXNvbnMgb2YgcG9y
dGFiaWxpdHkgKi8NCisvKioqKioqKioqKioqIGluIHBhcnRpY3VsYXIsIHlv
dSBuZWVkIHR3bydzIGNvbXBsZW1lbnQgYXJpdGhtZXRpYyAqKioqKioqKioq
Lw0KIA0KICNkZWZpbmUgS0sgMTAwICAgICAgICAgICAgICAgICAgICAgLyog
dGhlIGxvbmcgbGFnICovDQogI2RlZmluZSBMTCAgMzcgICAgICAgICAgICAg
ICAgICAgICAvKiB0aGUgc2hvcnQgbGFnICovDQpAQCAtNTY4LDEwICs1NzEs
MTMgQEANCiANCiAvKmxvbmcgcmFuX3hbS0tdOyAqLyAgICAgICAgICAgICAg
ICAgICAvKiB0aGUgZ2VuZXJhdG9yIHN0YXRlICovDQogDQotLyogdm9pZCBy
YW5fYXJyYXkobG9uZyBhYVtdLGludCBuKSAqLw0KKyNpZmRlZiBfX1NURENf
Xw0KK3ZvaWQgcmFuX2FycmF5KGxvbmcgYWFbXSxpbnQgbikNCisjZWxzZQ0K
IHZvaWQgcmFuX2FycmF5KGFhLG4pICAgIC8qIHB1dCBuIG5ldyByYW5kb20g
bnVtYmVycyBpbiBhYSAqLw0KICAgbG9uZyAqYWE7ICAgLyogZGVzdGluYXRp
b24gKi8NCiAgIGludCBuOyAgICAgIC8qIGFycmF5IGxlbmd0aCAobXVzdCBi
ZSBhdCBsZWFzdCBLSykgKi8NCisjZW5kaWYNCiB7DQogICByZWdpc3RlciBp
bnQgaSxqOw0KICAgZm9yIChqPTA7ajxLSztqKyspIGFhW2pdPXJhbl94W2pd
Ow0KQEAgLTU4MCw1NyArNTg2LDU3IEBADQogICBmb3IgKDtpPEtLO2krKyxq
KyspIHJhbl94W2ldPW1vZF9kaWZmKGFhW2otS0tdLHJhbl94W2ktTExdKTsN
CiB9DQogDQorLyogdGhlIGZvbGxvd2luZyByb3V0aW5lcyBhcmUgZnJvbSBl
eGVyY2lzZSAzLjYtLTE1ICovDQorLyogYWZ0ZXIgY2FsbGluZyByYW5fc3Rh
cnQsIGdldCBuZXcgcmFuZG9tcyBieSwgZS5nLiwgIng9cmFuX2Fycl9uZXh0
KCkiICovDQorDQorI2RlZmluZSBRVUFMSVRZIDEwMDkgLyogcmVjb21tZW5k
ZWQgcXVhbGl0eSBsZXZlbCBmb3IgaGlnaC1yZXMgdXNlICovDQorbG9uZyBy
YW5fYXJyX2J1ZltRVUFMSVRZXTsNCitsb25nIHJhbl9hcnJfc2VudGluZWw9
LTE7DQorbG9uZyAqcmFuX2Fycl9wdHI9JnJhbl9hcnJfc2VudGluZWw7IC8q
IHRoZSBuZXh0IHJhbmRvbSBudW1iZXIsIG9yIC0xICovDQorDQorI2RlZmlu
ZSByYW5fYXJyX25leHQoKSAoKnJhbl9hcnJfcHRyPj0wPyAqcmFuX2Fycl9w
dHIrKzogcmFuX2Fycl9jeWNsZSgpKQ0KK2xvbmcgcmFuX2Fycl9jeWNsZSgp
DQorew0KKyAgcmFuX2FycmF5KHJhbl9hcnJfYnVmLFFVQUxJVFkpOw0KKyAg
cmFuX2Fycl9idWZbMTAwXT0tMTsNCisgIHJhbl9hcnJfcHRyPXJhbl9hcnJf
YnVmKzE7DQorICByZXR1cm4gcmFuX2Fycl9idWZbMF07DQorfQ0KKw0KICNk
ZWZpbmUgVFQgIDcwICAgLyogZ3VhcmFudGVlZCBzZXBhcmF0aW9uIGJldHdl
ZW4gc3RyZWFtcyAqLw0KICNkZWZpbmUgaXNfb2RkKHgpICAoKHgpJjEpICAg
ICAgICAgIC8qIHVuaXRzIGJpdCBvZiB4ICovDQotI2RlZmluZSBldmVuaXpl
KHgpICgoeCkmKE1NLTIpKSAgIC8qIG1ha2UgeCBldmVuICovDQogDQotLyog
dm9pZCByYW5fc3RhcnQobG9uZyBzZWVkKSAqLw0KKyNpZmRlZiBfX1NURENf
Xw0KK3ZvaWQgcmFuX3N0YXJ0KGxvbmcgc2VlZCkNCisjZWxzZQ0KIHZvaWQg
cmFuX3N0YXJ0KHNlZWQpICAgIC8qIGRvIHRoaXMgYmVmb3JlIHVzaW5nIHJh
bl9hcnJheSAqLw0KICAgbG9uZyBzZWVkOyAgICAgICAgICAgIC8qIHNlbGVj
dG9yIGZvciBkaWZmZXJlbnQgc3RyZWFtcyAqLw0KKyNlbmRpZg0KIHsNCiAg
IHJlZ2lzdGVyIGludCB0LGo7DQogICBsb25nIHhbS0srS0stMV07ICAgICAg
ICAgICAgICAvKiB0aGUgcHJlcGFyYXRpb24gYnVmZmVyICovDQotICByZWdp
c3RlciBsb25nIHNzPWV2ZW5pemUoc2VlZCsyKTsNCisgIHJlZ2lzdGVyIGxv
bmcgc3M9KHNlZWQrMikmKE1NLTIpOw0KICAgZm9yIChqPTA7ajxLSztqKysp
IHsNCiAgICAgeFtqXT1zczsgICAgICAgICAgICAgICAgICAgICAgLyogYm9v
dHN0cmFwIHRoZSBidWZmZXIgKi8NCiAgICAgc3M8PD0xOyBpZiAoc3M+PU1N
KSBzcy09TU0tMjsgLyogY3ljbGljIHNoaWZ0IDI5IGJpdHMgKi8NCiAgIH0N
Ci0gIGZvciAoO2o8S0srS0stMTtqKyspIHhbal09MDsNCiAgIHhbMV0rKzsg
ICAgICAgICAgICAgIC8qIG1ha2UgeFsxXSAoYW5kIG9ubHkgeFsxXSkgb2Rk
ICovDQotICBzcz1zZWVkJihNTS0xKTsNCi0gIHQ9VFQtMTsgd2hpbGUgKHQp
IHsNCi0gICAgZm9yIChqPUtLLTE7aj4wO2otLSkgeFtqK2pdPXhbal07ICAv
KiAic3F1YXJlIiAqLw0KLSAgICBmb3IgKGo9S0srS0stMjtqPktLLUxMO2ot
PTIpIHhbS0srS0stMS1qXT1ldmVuaXplKHhbal0pOw0KLSAgICBmb3IgKGo9
S0srS0stMjtqPj1LSztqLS0pIGlmKGlzX29kZCh4W2pdKSkgew0KLSAgICAg
IHhbai0oS0stTEwpXT1tb2RfZGlmZih4W2otKEtLLUxMKV0seFtqXSk7DQor
ICBmb3IgKHNzPXNlZWQmKE1NLTEpLHQ9VFQtMTsgdDsgKSB7ICAgICAgIA0K
KyAgICBmb3IgKGo9S0stMTtqPjA7ai0tKSB4W2oral09eFtqXSwgeFtqK2ot
MV09MDsgLyogInNxdWFyZSIgKi8NCisgICAgZm9yIChqPUtLK0tLLTI7aj49
S0s7ai0tKQ0KKyAgICAgIHhbai0oS0stTEwpXT1tb2RfZGlmZih4W2otKEtL
LUxMKV0seFtqXSksDQogICAgICAgeFtqLUtLXT1tb2RfZGlmZih4W2otS0td
LHhbal0pOw0KLSAgICB9DQogICAgIGlmIChpc19vZGQoc3MpKSB7ICAgICAg
ICAgICAgICAvKiAibXVsdGlwbHkgYnkgeiIgKi8NCiAgICAgICBmb3IgKGo9
S0s7aj4wO2otLSkgIHhbal09eFtqLTFdOw0KICAgICAgIHhbMF09eFtLS107
ICAgICAgICAgICAgLyogc2hpZnQgdGhlIGJ1ZmZlciBjeWNsaWNhbGx5ICov
DQotICAgICAgaWYgKGlzX29kZCh4W0tLXSkpIHhbTExdPW1vZF9kaWZmKHhb
TExdLHhbS0tdKTsNCisgICAgICB4W0xMXT1tb2RfZGlmZih4W0xMXSx4W0tL
XSk7DQogICAgIH0NCiAgICAgaWYgKHNzKSBzcz4+PTE7IGVsc2UgdC0tOw0K
ICAgfQ0KICAgZm9yIChqPTA7ajxMTDtqKyspIHJhbl94W2orS0stTExdPXhb
al07DQogICBmb3IgKDtqPEtLO2orKykgcmFuX3hbai1MTF09eFtqXTsNCi19
DQotDQotLyogdGhlIGZvbGxvd2luZyByb3V0aW5lcyBhcmUgZnJvbSBleGVy
Y2lzZSAzLjYtLTE1ICovDQotLyogYWZ0ZXIgY2FsbGluZyByYW5fc3RhcnQs
IGdldCBuZXcgcmFuZG9tcyBieSwgZS5nLiwgIng9cmFuX2Fycl9uZXh0KCki
ICovDQotDQotI2RlZmluZSBRVUFMSVRZIDEwMDkgLyogcmVjb21tZW5kZWQg
cXVhbGl0eSBsZXZlbCBmb3IgaGlnaC1yZXMgdXNlICovDQotbG9uZyByYW5f
YXJyX2J1ZltRVUFMSVRZXTsNCi1sb25nIHJhbl9hcnJfc2VudGluZWw9LTE7
DQotbG9uZyAqcmFuX2Fycl9wdHI9JnJhbl9hcnJfc2VudGluZWw7IC8qIHRo
ZSBuZXh0IHJhbmRvbSBudW1iZXIsIG9yIC0xICovDQotDQotI2RlZmluZSBy
YW5fYXJyX25leHQoKSAoKnJhbl9hcnJfcHRyPj0wPyAqcmFuX2Fycl9wdHIr
KzogcmFuX2Fycl9jeWNsZSgpKQ0KLWxvbmcgcmFuX2Fycl9jeWNsZSgpDQot
ew0KLSAgcmFuX2FycmF5KHJhbl9hcnJfYnVmLFFVQUxJVFkpOw0KLSAgcmFu
X2Fycl9idWZbMTAwXT0tMTsNCi0gIHJhbl9hcnJfcHRyPXJhbl9hcnJfYnVm
KzE7DQotICByZXR1cm4gcmFuX2Fycl9idWZbMF07DQorICBmb3IgKGo9MDtq
PDEwO2orKykgcmFuX2FycmF5KHgsS0srS0stMSk7IC8qIHdhcm0gdGhpbmdz
IHVwICovDQorICByYW5fYXJyX3B0cj0mcmFuX2Fycl9zZW50aW5lbDsNCiB9
DQogDQogLyogPT09PT09PT09PT09PT09PT09PT09IGVuZCBvZiBLbnV0aCdz
IGNvZGUgPT09PT09PT09PT09PT09PT09PT09PSAqLw0K
---559023410-1141662977-1014960253=:3119--

-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-
r-devel mailing list -- Read http://www.ci.tuwien.ac.at/~hornik/R/R-FAQ.html
Send "info", "help", or "[un]subscribe"
(in the "body", not the subject !)  To: r-devel-request@stat.math.ethz.ch
_._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._