Hi, I'm also interested in Haskell. So sometimes I try to translate a
Haskell function (or algorithm) into J (and vv).
See also repeated squaring:
http://www.jsoftware.com/jwiki/Essays/Repeated Squaring
My first try to translate the Haskell Prelude exponentiation function ^
(working on arbitrary precision integer exponents) was:
pow=: 4 : 0"0
if. 0=y do. 1x return. end.
'q r'=.0 2#:y
if. r do. x * *: x pow q else. *: x pow q end.
)
>From this the more J-ish verb powGB is obtained. How does it work?
As you can see from pow's 'q r'=.0 2#:y the result is:
or (q 1) or (q 0)
In pow this is done recursively. To obtain the remainders 0 or 1 at
once, you can use:
#: 12 NB. = (2^3) + 2^2
1 1 0 0
In pow the temp. result is squared when r=0 and squared and then
multiplied by 'base' when r=1. Instead of 1s and 0s I need 'base's and
1s for multiplication. This is obtained as follows depending on the
chosen base, in this case base is 2:
(#: 12){1x, 2
2 2 1 1
I want to use this in a fold, so I'll have to reverse this to be able to
square and multiply J-wise (right to left):
1 **: 1 **: 2 **: 2
4096
or with insert:
(**:)/ |. 2 2 1 1
4096
Not a real mathematical explanation, but more or less how it works.
Hallo [email protected], je schreef op 09-04-09 18:19:
> 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
>
--
=@@i
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
