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
