There is a shorter computation of y inverse mod m in the J Wiki:
http://www.jsoftware.com/jwiki/Essays/Euclidean_Algorithm .
x gcd y computes the gcd of x and y as a linear combination:
g0 =: , ,. [EMAIL PROTECTED]@2:
it =: {: ,: {. - {: * <[EMAIL PROTECTED]&{./
gcd =: ([EMAIL PROTECTED]) @ (it^:([EMAIL PROTECTED]@{:)^:_) @ g0
m=: 10^12x
y=: 372313
y gcd m
214671526377 _79925
yi=: {. y gcd m
y * yi
79925000000000001
You do have to check that the gcd is in fact 1 (i.e. check
that yi is in fact an inverse):
(y,m) +/ .* y gcd m
1
----- 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
>
>Mike
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
