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, [email protected] 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
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
