Using extended integers is the obvious answer to this, but I'd like to
avoid the
memory and performance hits.
I'm using J806 (with avx if that's relevant) under Windows 10 on a
64-bit machine.
I wish to multiply integers modulo 2^48 . We can assume that inputs are
< 2^48.
Set
M =: 2 <.@^ 48
The "standard" way to do this is to define, say,
by =: M&|@*
For comparison, define a verb to multiply under x:,
byx =: by &. x: " 0
So consider these verbs applied to inputs whose product before taking
its modulus
exceeds 2^64, such as 2112345 23456789123451:
<.2^.2112345 23456789123451
21 44
For these I get:
(;datatype) 2112345 <.@(by,byx) 23456789123451
+-------------------------------+-------+
|228120645902336 228120645905603|integer|
+-------------------------------+-------+
The type of the result of by on its own on these args is floating. I
was surprised
when I spotted this. I had assumed that M&|@v forced the operation to
preserve
integer type!
Anyway, byx is slower and uses more space than by:
ts' $a by/ b' [ a =. 100#2112345 [ b =. 100#23456789123451
0.0148233 275328
ts' $a byx/ b' [ a =. 100#2112345 [ b =. 100#23456789123451
0.085672 353792
I attempted to get round this by writing my own verb, highprod.
It splits the arguments into low and high parts. In non-J notation,
x = a + b%:M, y = c + d%:M:
xy == M| (ac + M|(ad + bc)%:M) + O(M)
rtM =: 2 <.@^ 24
highprod =: 3 : 0 " 0
:
a =. rtM | x [ b =. _24 (33 b.) M|x =. <.x
c =. rtM | y [ d =. _24 (33 b.) M|y =. <.y
(a<.@*c) (M| <.@ +) 24 (33 b.) mask (17 b.) +/ (a,b)<.@*d,c
)
(;datatype) 2112345 <.@(highprod,byx) 23456789123451
+-------------------------------+-------+
|228120645905603 228120645905603|integer|
+-------------------------------+-------+
But it's even worse in terms of speed though using less space than byx:
ts' $a highprod/ b' [ a =. 100#2112345 [ b =. 100#23456789123451
0.148359 279296
No doubt "highprod" could be tweaked to make it somewhat faster,
possibly with a tacit form, but I doubt it would ever be as fast as "by"
I suppose byx or the like could be applied conditionally, testing the
size of the inputs, though the test would consume some time.
Is there a better way to do modulus multiply with largish arguments?
Thanks for any ideas,
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
