lambdaway :: modular

5 | list | login |load

| |

_h1 modular inverse
_ul Following [[rosettacode/Phix|https://rosettacode.org/wiki/Modular_inverse#Phix]] In modular arithmetic,   the modular multiplicative inverse of an integer   a   modulo   m   is an integer   x   such that {b ax = 1 modulo m}.

{pre
'{def mulinv
 {def mulinv.loop
  {lambda {:t :nt :r :nr}
   {if {not {= :nr 0}}
    then {mulinv.loop :nt 
                      {- :t {* {floor {/ :r :nr}} :nt}}
                      :nr 
                      {- :r {* {floor {/ :r :nr}} :nr}} }
    else {cons :t :r} }}}
 {lambda {:a :n}
  {let { {:a :a} {:n :n}
         {:cons {mulinv.loop 0 
                             1 
                             {if {< :n 0} then {- :n} else :n} 
                             {if {< :a 0} then {- :n {% {- :a} :n}} else :a}}}
       } {if {> {cdr :cons} 1}
          then not invertible
          else {if {< {car :cons} 0}
          then {+ {car :cons} :n}
          else {car :cons} }}}}}
-> {def mulinv
 {def mulinv.loop
  {lambda {:t :nt :r :nr}
   {if {not {= :nr 0}}
    then {mulinv.loop :nt 
                      {- :t {* {floor {/ :r :nr}} :nt}}
                      :nr 
                      {- :r {* {floor {/ :r :nr}} :nr}} }
    else {cons :t :r} }}}
 {lambda {:a :n}
  {let { {:a :a} {:n :n}
         {:cons {mulinv.loop 0 1 {if {< :n 0} then {- :n} else :n} 
                             {if {< :a 0} 
                              then {- :n {% {- :a} :n}} 
                              else :a}}}
       } {if {> {cdr :cons} 1}
          then not invertible
          else {if {< {car :cons} 0}
          then {+ {car :cons} :n}
          else {car :cons} }}}}}

'{mulinv 42 2017}
-> {mulinv 42 2017}
'{mulinv 40 1}
-> {mulinv 40 1}
'{mulinv 52 -217}
-> {mulinv 52 -217}
'{mulinv -486 217}
-> {mulinv -486 217}
'{mulinv 40 218}
-> {mulinv 40 218}
}

{{hide}
function mul_inv(integer a, n)
    if n<0 then n = -n end if
    if a<0 then a = n - mod(-a,n) end if
    integer t = 0,  nt = 1,
            r = n,  nr = a;   
    while nr!=0 do
        integer q = floor(r/nr)
        '{t, nt} = '{nt, t-q*nt}
        '{r, nr} = '{nr, r-q*nr}
    end while
    if r>1 then return "a is not invertible" end if
    if t<0 then t += n end if
    return t
end function

?mul_inv(42,2017)   -> 1969
?mul_inv(40, 1)     -> 0
?mul_inv(52, -217)  -> 96
?mul_inv(-486, 217) -> 121
?mul_inv(40, 2018)  -> not invertible
}