I'm sending to Programming, but Chat might be more suitable.
In solving Euler Project problem 720 (or ! 6) I stumbled into a
difficulty with monadic A.
The problem is described here: https://projecteuler.net/problem=720
It's not too hard, once you can spot a useful feature, but you don't
need to solve it to
see what I'm addressing.
The solver is asked to provide the index of a certain permutation, to be
determined.
Their first example permutation, in origin 1 is P4 = 1 3 2 4 for which
the required index
is S(4) = 3, ie >: A. 1 3 2 4
They also provide S(8) = 2295 and assert that 1000000007 | S(32) =
641839205
Being Project Euler, they naturally want a whopper, S(2^25), mod 1
000 000 007.
I eventually found P25 =: P(2^25) . Unfortunately, and hardly
surprisingly, the session
hangs on M&|@A. P25 .
The wiki essay https://code.jsoftware.com/wiki/Essays/Permutation_Index
assures the
reader that extended integers are used. In this case, of course,
finite arithmetic,
modulo M =: <.7+1e9 would be sufficient; in this case, extended
integers lead to a huge demand
on memory!
The essay discusses adot1 =: base #. rfd where rfd =: +/@(< {.)\."1
So I tried building my own versions of rfd, reduced form from direct
form, and adot1.
Now - the length of P25 is 33554432 = 2 <.@^ 25 .
For smaller solutions we have these input sizes and time/space results:
#each P10;P15;P16;P17
+----+-----+-----+------+
|1024|32768|65536|131072|
+----+-----+-----+------+
1 ts'#rfd P10'
0.0007487 36160
1 ts'#rfd P15'
0.29119 1.11546e6
1 ts'#rfd P16'
1.17691 2.22957e6
1 ts'#rfd P17'
4.71003 4.45779e6
So the performance of rfd for 2^25 elements is likely to be poor, even
though the
elements are all << the modulus. I played with
rfdr =: (+/@(< {:)\) &.: |.
ts'#rfdr P15'
0.29926 1.18086e6
and an explicit function, "reduced" - no need to reproduce it here:
ts'#reduced P15'
0.331894 1.37952e6
So no improvements found, and it seems likely that A. would still be
prohibitively
slow even if the (base #. ]) calculation were to be re-rendered in
arithmetic modulo M,
with a naive (?) introduction of the modulus, eg
madot =: base (M&|@#.) rfd
IF we can improve performance of the reduction step, the applicaton of
the factorial base
is also problematic, needing to do finite arithmetic.
eg, defining the 2^12 permutation P12 =: Sn 12, I get:
r;1 ts'r =: M&|@A. P12'
+---------+----------------+
|664981338|0.3715 2.72441e8|
+---------+----------------+
r;1 ts'r =: madot1 P12'
+---------+----------------+
|664981338|0.0386704 525824|
+---------+----------------+
where madot1 avoids M&|@#. as follows:
base_x =: (- i.)@# NB. "_x" means " don't use extended!!! "
madot1 =: ((M&|@*)/\.@: (1,~}.@base_x)) (M&|@+/ . *) rfd NB. still in
zero origin
Here, instead of having the factorial base, eg 5 4 3 2 1 applied using
#. to the result of rfd,
the actual factorial elements are generated, followed by their dot
product modulo M with rfd Pn.
Luckily for me, I discovered a way to generate the reduced form
directly, so avoiding the need
to derive it from the permutation, which is prohibitively slow and
space-consuming for 2^25.
Using something like madot1, applied to the reduced form, my approach
solves the given
problem in 20 seconds or so on this laptop.
So it may be that my difficulty with performance of monadic A. is seen
as unrealistic;
how often do we really need to calculate a permutation index in finite
arithmetic?
Thanks for your patience if you've read this far.
Cheers,
Mike
--
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
