Mailing-List: contact dev-help@commons.apache.org; run by ezmlm
Precedence: bulk
Reply-To: "Commons Developers List" <dev@commons.apache.org>
Received-SPF: neutral (nike.apache.org: local policy)
Message-ID: <4C986D28.8030504@free.fr>
Date: Tue, 21 Sep 2010 10:30:32 +0200
From: Luc Maisonobe <Luc.Maisonobe@free.fr>
User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US;
 rv:1.9.1.12) Gecko/20100915 Thunderbird/3.0.8
MIME-Version: 1.0
To: Commons Developers List <dev@commons.apache.org>
Subject: Re: [math] new pseudo random number generators
References: 
 <1055228943.9208471284978648519.JavaMail.root@spooler6-g27.priv.proxad.net>
 <4C97563F.2090904@gmail.com> <4C985D3E.4050407@free.fr>
 <AANLkTimS5JLYFEfz6FTeq5_QM8Ygo=5K2TYx2b_Vqofc@mail.gmail.com>
 <4C985FED.9060302@free.fr>
 <AANLkTi==x3=4fzpJMbAT7EKKGmKgY9gtaeBULv0mybEh@mail.gmail.com>
In-Reply-To: <AANLkTi==x3=4fzpJMbAT7EKKGmKgY9gtaeBULv0mybEh@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit

Le 21/09/2010 10:08, Mikkel Meyer Andersen a �crit :
> 2010/9/21 Luc Maisonobe <Luc.Maisonobe@free.fr>:
>> Le 21/09/2010 09:26, Mikkel Meyer Andersen a �crit :
>>>> Here is an extract from the answer from Pierre L'Ecuyer:
>>>>
>>>>  Our code can be released under either a GPL or a commercial license.
>>> Well, what about the Apache License then?
>>
>> It is their code and I did not use it. The main point is we
>> reimplemented it. Of course, relying on their code that is GPLed would
>> be a clear no-go as GPL is a category X license (see
>> <http://www.apache.org/legal/resolved.html#category-x>).
> Exactly. But as I understood, you used some of their optimization
> principles - but that is not an issue or?

I finally inlined everything, yes but I doubt it would count as a
specific optimization found only in this original code. It's a common
way and especially when the code to be inlined is one or two
instructions only. The elementary transforms here are very simple
(things like "v0 ^ (v0 << 25)" or "((z2 & 0x00020000) != 0) ? (z2Prime ^
0xb729fcec) : z2Prime"). Inlining this is common sense.

>>
>> Perhaps I should give a go to still other optimizations just to make
>> more clear our code is really different ?
> I'm not sure what you mean?

Some ways to optimize further could be to process several numbers in raw
to benefit from some of the values being already in register rather than
putting them in a memory array to read them back just the next iteration
(one Well iteration uses 5 values from the bits pool array, two being
close together and the three other being spread in the array).
Basically, it would be packing two or more iterations in one call and
cache the results. Then, when the user asks for 1 million numbers, some
calls would result in simply retrieving one value from the cache and
only a few calls would mean cherry picking in the array and performing
the bits twiddling.

They do not use this kind of tricks in their implementation. By using
them in ours, it would make more clear our code is really an original
one and not derived from their GPL code.

Luc

>>
>> Luc
>>
>>>
>>>>  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.
>>>>
>>>> So as I reimplemented from the paper itself (taking the erratas in <
>>>> http://www.iro.umontreal.ca/~lecuyer/myftp/papers/wellrng-errata.txt>
>>>> into account) and use different optimization techniques (precomputed
>>>> indices tables), I would consider it is safe to publish this home-grown
>>>> code.
>>>
>>> ---------------------------------------------------------------------
>>> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
>>> For additional commands, e-mail: dev-help@commons.apache.org
>>>
>>
>>
>> ---------------------------------------------------------------------
>> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
>> For additional commands, e-mail: dev-help@commons.apache.org
>>
>>
> 
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
> 


---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org