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
Mike
..............
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
