a. Using the multiplicative order to compute the inverse is not an efficient way to go. (For example, even the fast implementation of mo involves factoring.) GCD should be much faster.
b. I said earlier that the obstacle to having x m&|@^ y compute multiplicative inverses mod m is that x^y already has a different meaning. On further reflection, I think it is more fitting to say that m|y is the obstacle. For example, currently 17 | 0.125 0.125 However, it is possible to interpret 0.125 as the inverse of 8 and hence 17|0.125 as the multiplicative inverse of 8 mod 17, with an answer of 15. The current defn of x^y is useful (!); the current defn of m|y for non-integer y is less so. ----- Original Message ----- From: "Mike Day" <[EMAIL PROTECTED]> To: "Programming forum" <[email protected]> Sent: Wednesday, March 01, 2006 3:44 AM Subject: Re: [Jprogramming] If Maple can, why can't J? Re-sent with missing line throw reset. Thanks for the pointer to mo. I had worked up a verb for reciprocal y modulo x, x & y coprime, some months ago and eventually found it (!) Also, as you say, mo can be used: Here's my earlier one rendered into J6... NB. reciprocal of y mod x NB. plagiarism/adaptation of J library gcd verb mrecip =: 3 : 0 ~ : b =. x: y p =. -. r =. 0 'xp yr' =.(x: x,p);y,r assert. 1 = b +. {.xp while. 0 < x: | {.yr do. NB. while. * | y do. ... enable these NB.s if scalars preferred 'xp yr' =. yr; xp - yr * <. ({.xp) % {.yr NB.'x p y r'=. y, r, (x, p) - (y, r) * <. x % y end. b | x:{:xp NB. b | p ) NB. and here's a verb using mo: NB. mo (& mopk) not listed here, NB. mo and mopk as in J Wiki for "multiplicative order" mrecip1=: dyad : 0 f =. (x:x) 1 : 'm&|@^' NB. x mo y ==> least n such that 1=y|x^n NB. so <:@mo gives least power m such that 1 = y| x * x^m y ([f <:@mo) x ) 1000000000000x(]*mrecip) 372313 79925000000000001 1000000000000x(]*mrecip1) 372313 79925000000000001 >ts each'1000000000000x(]*mrecip) 372313 ';'1000000000000x(]*mrecip1) 372313 ' 0.000485816 5504 0.00269196 29440 These timings are a bit surprising, since mrecip does several more loops than mo & mopk, at least for this example. Mike Roger Hui wrote: >The obstacle is not implementational but definitional. >The assumed requirement was that x m&|@^ y should be >equivalent to m|x^y , and therefore can not be used to >compute inverses in the group of integers mod m without >redefining the meaning of x^y for negative powers. >This assumption should perhaps be reexamined because it >seems much more useful for x m&|@^ y to compute powers >mod m rather than m|x^y . > >Note that if you use instead the phrase > x m&|@^ (y mo m)|y >where mo is the multiplicative order function posted a few >days ago, then you can compute powers mod m for all integer y >(and obtain tremendous efficiency gains for large magnitude y). > > > >----- Original Message ----- >From: "Mike Day" <[EMAIL PROTECTED]> >To: "Programming forum" <[email protected]> >Sent: Monday, February 27, 2006 2:18 AM >Subject: Re: [Jprogramming] If Maple can, why can't J? > >... > >Roger mentioned that Mathematica's PowerMod function also offers a >fast solution. I looked at its online description at > http://documents.wolfram.com/mathematica/book/section-3.2.5 >which shows that it's also implemented for negative powers: > > This gives the modular inverse of 3 modulo 7 > In[19]:= PowerMod[3, -1, 7] > Out[19]= 5 > >whereas in J: > 3(7&|@^)0 6 - 1 NB. could J have integer solutions for neg powers? >0.333333 5 ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
