[Jprogramming] Closed form of Perrin sequence?

[Aai]

timings on my (old) 32 bit/3Ghz computer

2 ppp 271500

J: 23.5 sec

PARI prog: 26.6 sec

2 ppp 1e6

J: 90 sec

PARI prog: 2 min.


I didn't test up-to 1e8 ;-)



PARI rep. sq.: no doubt is does

For a (more sophisticated?) algorithm description look at another CAS  
YACAS: they have a book of algorithms

    http://yacas.sourceforge.net/homepage.html     para. 5.1 Powers

tab 'Manual'

On 10-01-14 22:03, mike_liz.day at tiscali.co.uk wrote:
> Thanks.
>
> Yes,  you're right about the precision. I'd been using an
> extended integer form of the matrix when using modulus 4 p: 1e8 .
>
>
> It's reassuring to see that if
>     datatype MAT
> boolean
>
> then
>     
> datatype MAT(100000000 mMpower)100000000
> integer
>
>
> Your ppp is about
> three times faster than my "mission" on my laptop:
>      timer'0-.~,ppp"0
> }.>:i.271500'  NB. about half a minute
>
> +-------+------+
> |28.
> 5181|271441|
> +-------+------+
>
>     timer'mission 271500'    NB. about
> one and a third minutes
> 100000
> 200000
> +---------+------+
> |1 16.2891
> |271441|
> +---------+------+
>
> The code-golf mission is to do 100 million
> numbers,  so I won't go further with
> this time test!
>
> However,  both
> our (essentially equivalent) approaches appear to be far better
> than
> Devon's 5 hours, using a different method!
>
> FWIW,  here's the Pari_GP
> result for the full 100 million:
> (22:14) gp > mission(100000000)  \\
> run for 100 million at 20:14pm yesterday
> time = 4h, 43min, 26,609
> ms.
> %27 = [271441, 904631, 16532714, 24658561, 27422714,
> 27664033, 46672291]
>
> So its (Pari-GP's) built-in power over a residue
> does quite well here;  that is,
> the nub of the Pari-GP approach is
> to express the nth power of the
> matrix M modulo n as    Mod(M,n)^n
>
> I
> don't know whether Pari-GP uses the repeated squaring trick for powers
>
> internally.  I suppose it might even use an even more sophisticated
> partition
> of the power.
>
> Mike
> (sorry - history deleted previous to
> your (Aai's) post)
>
> On 08/01/2014 14:30, Aai wrote:
>> If still of any
> use:
>> 1. A reasonable speed up is obtained by not using st. prec.
> for matrix mat. because you are calculating modulo.
>> 2. further
> speed up by 'condensing' your code to:
>> isPPP=: 3 :'0 = y| +/ (<0 1)
> |: y&|@(+/ .*)/ (|+/ .*~)^:(I.@|.@#:@]`((3 3 $0 1 0 0 0 1 1 1 0)"_))
> ~y'"0
>> ppp =: (#~isPPP)@(#~[:-. 1&p:)@([+i.@>:@-~)
>>
>>
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm

-- 
Met vriendelijke groet,
@@i = Arie Groeneveld