openssl bindings can help, https://github.com/Pascal-J/BN-openssl-bindings-for-J
Slowness for your highprod verb will necessarily occur as a result of rank0 explicit definition. The definition is parsed on each invocation. is M a power of 2? A property that may be useful is that when either x or y not prime, M&|@*/ ,&q:/ M | x , y equivalent to M&|@*/ x , y ________________________________ From: 'Mike Day' via Programming <[email protected]> To: [email protected] Sent: Monday, May 8, 2017 4:44 AM Subject: [Jprogramming] Precision of modular multiplication of quite large numbers 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 ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
