[Rd] Weakness in Knuth-TAOCP RNG (fwd) (PR#1336)
ripley@stats.ox.ac.uk
ripley@stats.ox.ac.uk
Fri, 1 Mar 2002 07:38:12 +0100 (MET)
Attachments don't really work with R-bugs. To save us trying to unpick
this manually, could you re-send it as the body of a message to R-bugs
in reply to this one, or quoting (PR#1336) in the subject, please?
On Fri, 1 Mar 2002 schutz@wehi.edu.au wrote:
> 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
> _._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._
>
--
Brian D. Ripley, ripley@stats.ox.ac.uk
Professor of Applied Statistics, http://www.stats.ox.ac.uk/~ripley/
University of Oxford, Tel: +44 1865 272861 (self)
1 South Parks Road, +44 1865 272860 (secr)
Oxford OX1 3TG, UK Fax: +44 1865 272595
-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-
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
_._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._