Lovely. Hopefully including negative powers! How will you deal with
ill-defined results,
though?
Thanks,
Mike
Sent from my iPad
> On 4 Apr 2023, at 19:07, Henry Rich <henryhr...@gmail.com> wrote:
>
> Expect primitive support for modular inverse in an upcoming beta.
>
> Henry Rich
>
>
>> On Tue, Apr 4, 2023, 1:49 PM 'Michael Day' via Programming <
>> programm...@jsoftware.com> wrote:
>>
>> Thanks, Chris, and Cliff too.
>>
>> Yes, a mod inverse helps a lot. Once you've got an inverse, it's easy
>> to derive a modular divide, or vice
>> versa.
>>
>> inversep in primutil.ijs is well defined for a prime modulus - the name
>> "primutil" does of course imply
>> a prime modulus.
>> inversep also appears to work ok for those numbers in the ring of
>> integers modulo non-prime modulus.
>>
>> eg members of the ring modulo 10 are {1 3 7 9}
>> {{ y,:y (10 mtimes) (10&inversep)"0 y}} 1 3 7 9
>> 1 3 7 9
>> 1 1 1 1
>> {{ y,:y (10 mtimes) (10&mrecip)"0 y}} 1 3 7 9
>> 1 3 7 9
>> 1 1 1 1
>>
>> I find rather better performance with my mrecip:
>> ts =: 6!:2 , 7!:2@]
>>
>> 1 p: 1000000009
>> 1
>>
>> ts'100000009 mrecip 999999000 + >:i.1007'
>> 0.0061255 22592
>> ts'100000009 inversep"0] 999999000 + >:i.1007'
>> 0.0798054 97160
>> ts'100000009 mi"0] 999999000 + >:i.1007'
>> 0.0908823 174192
>>
>> A bit surprising as the Extended Euler Algorithm is supposed to be best
>> for getting a modular inverse.
>>
>> 1000000009 (mrecip-:inversep"0) 999999000 + >:i.1007
>> 1
>> 1000000009 ((1000000009 mi)"0 @] -:inversep"0) 999999000 + >:i.1007
>> 1
>>
>> Here's mrecip:
>>
>> mrecip =: {{
>> y (x&|@^) <: 5 p: x
>> }}"0
>>
>> As for inversep, and Cliff's mi, mrecip is well-defined for prime x,
>> and also for composite
>> x for y in x's ring, ie where 1 = x +. y
>>
>> Results are NOT reliable for arguments not coprime with the modulus.
>>
>> Thanks,
>>
>> Mike
>>
>>> On 03/04/2023 16:22, chris burke wrote:
>>> Cliff
>>>
>>> There are some mod functions in the math/misc addon, e.g. this gives
>>> Mike Day's table
>>>
>>> load 'math/misc/primutil'
>>> f=: (17 timesmod) (17&inversep)
>>> 2 3 4 f"0 table >:i.8
>>> +---+---------------------+
>>> |f"0|1 2 3 4 5 6 7 8|
>>> +---+---------------------+
>>> |2 |2 1 12 9 14 6 10 13|
>>> |3 |3 10 1 5 4 9 15 11|
>>> |4 |4 2 7 1 11 12 3 9|
>>> +---+---------------------+
>>>
>>> Any improvements welcome, thanks.
>>>
>>> Chris
>>>
>>> On Mon, Apr 3, 2023 at 5:49 AM Clifford Reiter<reit...@lafayette.edu>
>> wrote:
>>>> I dug up an old extended gcd to build an adverb for modular divide
>>>>
>>>> NB. Find the gcd of two numbers
>>>>
>>>> NB. and coef giving gcd as a linear combination of y
>>>>
>>>> gcd2x=: 3 : 0
>>>>
>>>> 'r0 r1'=.y
>>>>
>>>> 's0 s1'=.1 0x
>>>>
>>>> 't0 t1'=.0 1x
>>>>
>>>> while. r1 ~: 0 do.
>>>>
>>>> q=. r0 <.@% r1
>>>>
>>>> 'r0 r1'=. r1,r0-q*r1
>>>>
>>>> 's0 s1'=. s1,s0-q*s1
>>>>
>>>> 't0 t1'=. t1,t0-q*t1
>>>>
>>>> end.
>>>>
>>>> r0,s0,t0
>>>>
>>>> )
>>>>
>>>> gcd2x 51 119
>>>>
>>>> 17 _2 1
>>>>
>>>> _2 1 +/ . * 51 119
>>>>
>>>> 17
>>>>
>>>> NB. adverb giving divide (inverse) mod m
>>>>
>>>> mi=:1 : 0"0
>>>>
>>>> 'r0 s0 t0'=:gcd2x m,y
>>>>
>>>> if. r0=1 do. m|t0 else. 1r0 end.
>>>>
>>>> :
>>>>
>>>> m|x*m mi y
>>>>
>>>> )
>>>>
>>>> 17 mi 6
>>>>
>>>> 3
>>>>
>>>> NB. Mike Day's Table
>>>>
>>>> 2 3 4 (17 mi)table >:i.8
>>>>
>>>> +-+---------------------+
>>>>
>>>> | |1 2 3 4 5 6 7 8|
>>>>
>>>> +-+---------------------+
>>>>
>>>> |2|2 1 12 9 14 6 10 13|
>>>>
>>>> |3|3 10 1 5 4 9 15 11|
>>>>
>>>> |4|4 2 7 1 11 12 3 9|
>>>>
>>>> +-+---------------------+
>>>>
>>>>
>>>> I have some questions regarding system solving modulo m that I will
>> offer
>>>> in a new thread in a few days.
>>>>
>>>> Best, Cliff
>>>>
>>>> On Thu, Mar 30, 2023 at 12:11 PM Clifford Reiter<reit...@lafayette.edu>
>>>> wrote:
>>>>
>>>>> I think I recall a conversation, some decades ago, with Roger about
>>>>> whether specifying a modulus for system solving makes sense for J. I
>>>>> thought maybe that was a use for the fit conjunction but now think that
>>>>> would be a poor choice for such a numeric function. I have vague
>> memories
>>>>> of J essays on guass-jordan row reduction and extended gcds but didn't
>> find
>>>>> them poking around J help.
>>>>> They could be useful for what I had in mind and modular inverses would
>> be
>>>>> part of that. Perhaps someone has those handy and could offer an
>> addon? New
>>>>> adverbs giving b m %.: a and m %.: a anyone?
>>>>> Best, Cliff
>>>>>
>>>>> On Wed, Mar 29, 2023 at 5:02 PM 'Michael Day' via Programming <
>>>>> programm...@jsoftware.com> wrote:
>>>>>
>>>>>> While this primitve works nicely in an example:
>>>>>>
>>>>>> (2 3 4) (17&|@*)/ table >:i.8
>>>>>> +-------+---------------------+
>>>>>> |17&|@*/|1 2 3 4 5 6 7 8|
>>>>>> +-------+---------------------+
>>>>>> |2 |2 4 6 8 10 12 14 16|
>>>>>> |3 |3 6 9 12 15 1 4 7|
>>>>>> |4 |4 8 12 16 3 7 11 15|
>>>>>> +-------+---------------------+
>>>>>>
>>>>>> I find this less satisfying:
>>>>>> (2 3 4) (17&|@%)/ table >:i.8
>>>>>> +-------+-----------------------------------------------+
>>>>>> |17&|@%/|1 2 3 4 5 6 7 8|
>>>>>> +-------+-----------------------------------------------+
>>>>>> |2 |2 1 0.666667 0.5 0.4 0.333333 0.285714 0.25|
>>>>>> |3 |3 1.5 1 0.75 0.6 0.5 0.428571 0.375|
>>>>>> |4 |4 2 1.33333 1 0.8 0.666667 0.571429 0.5|
>>>>>> +-------+-----------------------------------------------+
>>>>>>
>>>>>> I have a function which does what one would expect. I'll rename it as
>>>>>> m17div here, details unimportant for this discussion:
>>>>>> (2 3 4) m17div/ table >:i.8
>>>>>> +-------+---------------------+
>>>>>> |m17div/|1 2 3 4 5 6 7 8|
>>>>>> +-------+---------------------+
>>>>>> |2 |2 1 12 9 14 6 10 13|
>>>>>> |3 |3 10 1 5 4 9 15 11|
>>>>>> |4 |4 2 7 1 11 12 3 9|
>>>>>> +-------+---------------------+
>>>>>> ( eg 3 % 2 == 10 mod 17 because 3 = 17 | 2 * 10 )
>>>>>>
>>>>>> Would anyone else find this return of integer results useful or is it
>>>>>> better
>>>>>> to force a floating output?
>>>>>>
>>>>>> (Henry tells me that m&|@^ returns integer results, working ok when
>> m^2
>>>>>> can be represented as a non-extended integer.)
>>>>>>
>>>>>> Thanks,
>>>>>>
>>>>>> Mike
>>>>>>
>>>>>> ----------------------------------------------------------------------
>>>>>> For information about J forums seehttp://www.jsoftware.com/forums.htm
>>>>>>
>>>> ----------------------------------------------------------------------
>>>> For information about J forums seehttp://www.jsoftware.com/forums.htm
>>> ----------------------------------------------------------------------
>>> For information about J forums seehttp://www.jsoftware.com/forums.htm
>>
>> ----------------------------------------------------------------------
>> For information about J forums see http://www.jsoftware.com/forums.htm
>>
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
