[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Low hanging fruit - Accelerated random distribution functions
From: |
David Bateman |
Subject: |
Re: Low hanging fruit - Accelerated random distribution functions |
Date: |
Fri, 23 Feb 2007 15:01:37 +0100 |
User-agent: |
Thunderbird 1.5.0.7 (X11/20060921) |
Paul Kienzle wrote:
>
> On Feb 23, 2007, at 7:49 AM, Paul Kienzle wrote:
>
>>
>> On Feb 23, 2007, at 5:27 AM, David Bateman wrote:
>>
>>> Paul Kienzle wrote:
>>>>
>>>> On Feb 22, 2007, at 7:29 PM, Paul Kienzle wrote:
>>>>
>>>>>
>>>>> On Feb 22, 2007, at 11:46 AM, David Bateman wrote:
>>>>>
>>>>>> I haven't tried to convert the functions geornd,
>>>>>
>>>>> Octave uses the following; it would be hard to beat:
>>>>>
>>>>> rnd(k) = floor (log (rand (size (k))) ./ log (1 - p(k)));
>>>>
>>>> On second thought,
>>>>
>>>> rnd = floor(-rande(n)) ./ log(1-p)
>
> Oops ... misplaced parenthesis...
>
> It should be R = floor(-rande(n)./log(1-p))
>
> I'm not sure why this would affect the speed.
>
>>>>
>>>> is 2x faster.
>>>
>>> Are you sure its not the reverse
>>>
>>> octave:3> function rnd = geornd2(p,varargin), rnd =
>>> floor(-rande(varargin{:})) ./ log(1-p); endfunction
>>> octave:4> tic; b0 = geornd(3,1,1e7); toc
>>> Elapsed time is 1.643173 seconds.
>>> octave:5> tic; b1 = geornd2(3,1,1e7); toc
>>> Elapsed time is 3.176453 seconds.
>>
>> octave2.9:10> tic; y = floor(log(rand(400))./log(1-0.2)); toc
>> Elapsed time is 0.534271 seconds.
>> octave2.9:11> tic; x = floor(-rande(400)./log(1-0.2)); toc
>> Elapsed time is 0.348267 seconds.
>> octave2.9:12> [statistics(x(:)),statistics(y(:))]
>> ans =
>>
>> 0.00000 0.00000
>> 1.00000 1.00000
>> 3.00000 3.00000
>> 6.00000 6.00000
>> 55.00000 54.00000
>> 4.00524 3.99577
>> 4.49588 4.46590
>> 2.02001 1.99510
>> 5.99429 5.90314
>>
>
>
I get
octave:1> function rnd = geornd2(p, varargin), rnd =
floor(-rande(varargin{:})./
log(1-p)); endfunction
octave:2> function rnd = geornd3(p, varargin), rnd =
floor(log(rand(varargin{:}))./log(1-p)); endfunction
octave:3> tic; b0 = geornd(0.2,1,1e6); toc
Elapsed time is 0.400322 seconds.
octave:4> tic; b2 = geornd2(0.2,1,1e6); toc
Elapsed time is 0.262650 seconds.
octave:5> tic; b2 = geornd3(0.2,1,1e6); toc
Elapsed time is 0.373726 seconds.
I should have paid closer attention to the value of "p" and only the
values between 0 and 1 are valid.. My previous example just showed that
"NaN*ones(sz)" was faster than "floor(-rande(sz)./log(1-p))" which is no
surprise.. Ok the attached patch replacement patch for patch45 includes
this change as well.
Ok I think, except for the possible advantage of rearranging some of the
special case code, I think all of the distributions have been
re-examined and accelerated where possible.. Given John previous
statement I'll go ahead an commit this stuff.
Regards
David
--
David Bateman address@hidden
Motorola Labs - Paris +33 1 69 35 48 04 (Ph)
Parc Les Algorithmes, Commune de St Aubin +33 6 72 01 06 33 (Mob)
91193 Gif-Sur-Yvette FRANCE +33 1 69 35 77 01 (Fax)
The information contained in this communication has been classified as:
[x] General Business Information
[ ] Motorola Internal Use Only
[ ] Motorola Confidential Proprietary
Re: Low hanging fruit - Accelerated random distribution functions, Paul Kienzle, 2007/02/22
Re: Low hanging fruit - Accelerated random distribution functions, David Bateman, 2007/02/23