www-legal-discuss mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Luc Maisonobe <Luc.Maison...@free.fr>
Subject Fwd: Re: implementing the WELL generators
Date Thu, 23 Sep 2010 18:34:50 GMT
Hi,

In the Apache commons-math project (one of the subprojects under Apache
commons umbrella), we implement a lot of mathematical algorithm. One of
our recent work was related to pseudo-random number generators and we
wanted to add some recent (say post 2000) algorithms published by some
Canadian mathematicians to complement our existing ones.

These algorithms are described in a paper:
<http://www.iro.umontreal.ca/~lecuyer/myftp/papers/wellrng.pdf>. There
are no restriction on using the algorithm in the paper. There are also
reference implementations of the algorithm available at the authors web
site, but one set of implementations
<http://www.iro.umontreal.ca/~panneton/well/> is restricted to
"personal, academic, or non-commercial purposes" and the other set
<http://www.iro.umontreal.ca/~simardr/ssj/indexe.html> is published
under the GPL license.

The implementation we created is completely independent from the
reference implementations. We used only the first set of reference
implementation to produce reference test data and used that data to test
our implementation. No line of code was copied and we relied on the
paper for working.

To be really sure our use was fait, we asked the authors. His complete
answer is below. The most important part (at least to me) seems to be
"If you reimplement the code, this is a gray zone, but we do not have a
patent on the algorithm".

So I think we have a clean room implementation of an algorithm without
any patent.

Do you think this is OK and can publish this code under the Apache
Software Licence ?

thanks in advance,
Luc, on behalf of the Apache Commons Math team


-------- Message original --------
Sujet: Re: implementing the WELL generators
Date : Mon, 20 Sep 2010 22:06:07 -0400
De : Pierre L'Ecuyer <lecuyer@iro.umontreal.ca>
Répondre à : lecuyer@iro.umontreal.ca
Pour : luc.maisonobe@free.fr
Copie à : panneton@iro.umontreal.ca


Just a quick answer... my time is limited:

On 9/20/2010 9:36 AM, luc.maisonobe@free.fr wrote:
> Hi,
>
> I am Luc Maisonobe, a French engineer working on an open-source mathematical library
on my spare time. I started work to implement your impressive WELL generators in this library
and have a few questions to ask.
>
> I use directly your paper for the implementation which I realized usingobject oriented
design in the Java language. This implementation is therefore completely independent from
the reference implementation you provided in C. I relied on the reference implementation only
for the sake of generating reference data and test what I did. I noticed this reference implementation
is for non-commercial use only so I did not use it for my owncode (the library I work for
is published under the Apache Software License so it cannot prevent commercial use). Is my
interpretation correct and can I publish my implementation under the ASL ? Of course, this
implementation and the associated documentation do give proper attribute with your names and
the reference of your paper. Apart from reference implementation restrictions, are their some
restrictions on the algorithm by itselflike patents or similar ?

Our code can be released under either a GPL or a commercial license.
There is also a Java implementation with multiple streams and substreams
in SSJ:
see the package rng:   http://www.iro.umontreal.ca/~simardr/ssj/indexe.html
If you reimplement the code, this is a gray zone, but we do not have a
patent on the algorithm.


> I also have a few more technical questions about the algorithm, that raised at testing
phase when I compared my results with reference results Icreated with your reference implementation.
In table I, the paper specifies that in transform M5 a positive t specifies a left shift whereas
a negative t specifies a right shift. The reference code seems to do the opposite (this transform
is used only for WELL512a with t=-T). What is the correct interpretation ensuring the properties
of the generator ? A similar problem occurs with transform T6 also for WELL512a. Table II
of the paper specifies this transform to be M3(-28) but the code uses M2(-28) (in fact under
the name M3 but the naming convention seem to be different in the paper and the code). Here
again, which transform should be used. Another discrepancy appears in the constants for transform
T6 in WELL44497a, which correspond to M6. The paper specifies a ds mask with the 14th bit
cleared and a t mask with the 5th bit set but
 the code seem to use ds withthe 26th bit cleared and t with the 17th bit set (+/- 1 depending
on thenumbering convention for the bits). Which one is the good one ?

There are some typos in the paper; see
http://www.iro.umontreal.ca/~lecuyer/myftp/papers/wellrng-errata.txt


> My last question is a more general one on these kind of generators. Theequidistribution
properties are proven for at most 32 bits blocks (l<  min(w, K/t) with w = 32 bits here).
The IEEE754 doubles have a 53 bits mantissa (52 bits stored but 1 extra implicit bit if the
number is not subnormal). If I use 53 bits by calling the generator twice and combining the
raw bits (say 26 from the first number and 27 from the second number), do I still get good
properties for such a number (of course only up to a reduced vector dimension according to
the bits pool size) ? For some simulation purposes, having a discretization bias at 2^-32
can lead to problems.

This should be ok (we do that), but there is no proof of
equidistribution for these additional bits.

> Thanks a lot for your wonderful generators and very interesting paper
> best regards,
> Luc

-- 
Pierre L'Ecuyer, Professeur Titulaire
Chaire du Canada en Simulation et Optimisation Stochastique
CIRRELT, GERAD, and DIRO, Université de Montréal, Canada
http://www.iro.umontreal.ca/~lecuyer





---------------------------------------------------------------------
To unsubscribe, e-mail: legal-discuss-unsubscribe@apache.org
For additional commands, e-mail: legal-discuss-help@apache.org


Mime
View raw message