Thanks to: Aai <[email protected]>
for suggesting the following to calculate <: 2x^ N
>powGB=: (**:)/@(|....@#:@]{1x,[) NB. don't know who's
brainchild
I would appreciate an explination of what powGB is doing.
thanks.
By the way, this is a lot faster method for initializing a
Mersenne prime value
NB. to caluculate running time in seconds
time =. 6!:2
NB. To calculate <: 2x^N I used:
powGB=: (**:)/@(|.@|....@#:@]{1x,[)
time ' <: 2x powGB 8191'
4.03302e_5
time ' <: 2x powGB 101'
0.00159573
time 'val =: <: 2x powGB 86243'
0.248049
time 'val =: <: 2x powGB 859433'
2815.15
----- Original Message Follows -----
From: Aai <[email protected]>
To: Programming forum <[email protected]>
Subject: Re: [Jprogramming] Mersenne Prime initialization.
Date: Wed, 08 Apr 2009 13:55:10 +0200
>Also, it's possible that:
>
> #. 110503$1x
>|out of memory
>| #.110503$1
>
>You can use a folding instead:
>
> ([++:@])/ 110503$1x
>5219283133417550597608921138394131714748003987...
>
>or ignoring the 1s:
>
> >:@+:@]/ 110503$1x
>
>or with power ^:
>
> >:@+:^: (<: 110503) 1x
>5219283133417550597608921138394131714748003987...
>
>
>but it's also very slow..
>
> ts '([++:@])/ 110503$1x'
>16.633282 788352
>
> ts '>:@+:^: (110502) 1x'
>16.738218 329344
>
>
>Using a specialized exponentiation provides some speed up:
>
>powGB=: (**:)/@(|....@#:@]{1x,[) NB. don't know who's
>brainchild, sorry
>
>.. and showing the last 31 digits:
>
> ts 'it=:_31{.": <: 2x powGB 110503'
>0.633862 296960
> it
>9131999107769951621083465515007
>
>Compared to:
>
> ts 'it=:_31{.": <: 2x ^ 110503'
>1.414242 430912
> it
>9131999107769951621083465515007
>
>I didn't try MP39 though (well, just for a while). :-)
>
>To obtain MP39 I used Haskell's interpreter GHCi (using the
>equivalence of ext. prec.: arbitrary prec. integers)
>showing the last 46 digits from a total of 4053946 digits (
>>.13466917*10^.2) :
>
>*Main> (take 9 &&& (take 9 .drop 4053937)).show . pred $
>2^13466917 ("924947738","256259071")
>(19.89 secs, 155769356 bytes)
>
>Check with: http://en.wikipedia.org/wiki/Mersenne_prime
>
>
>
>Hallo Matthew Brand, je schreef op 08-04-09 09:09:
>> You can do it like this:
>> #. N # 1x
>>
>> ... but it is *much* slower than doing <: 2x^N
>>
>> On Tue, Apr 7, 2009 at 7:39 PM,
>> <[email protected]> wrote:
>>> The following are Mersenne Primes 2, 3, 15, 29 and 39
>>>
>>> MP2 =: <:2x^3
>>> MP3 =: <: 2x^5
>>> MP5 =: <: 2x^13
>>> MP15 =: <: 2x^1279
>>> MP29 =: <: 2x^110503
>>> MP39 =: <: 2x^13466917
>>>
>>> As an example <: 2x^3 in binary is 1000 - 1 which is
>>> binary 111
>>>
>>> Any mersenne prime of the form <: 2x^N is "N binary
>>>1s"
>>> It takes a very long time to calculate MP39.
>>>
>>> How could I accomplish the same thing by noting that in
>>> the case of MP39, I need to create an
>>> extended value that is "13466917 binary 1s"
>>>
>>> thanks
>>>
>>>
>>>
>>>
>>>
>-----------------------------------------------------------
>>> ----------- For information about J forums see
>>>http://www.jsoftware.com/forums.htm
>>>
>>
>>
>>
>>
>
>--
>=@@i
>
>-----------------------------------------------------------
>----------- For information about J forums see
>http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
