How to resolve the algorithm Modular inverse step by step in the Quackery programming language

Published on 12 May 2024 09:40 PM
#Quackery

How to resolve the algorithm Modular inverse step by step in the Quackery programming language

Table of Contents

Problem Statement

From Wikipedia: In modular arithmetic,   the modular multiplicative inverse of an integer   a   modulo   m   is an integer   x   such that Or in other words, such that: It can be shown that such an inverse exists   if and only if   a   and   m   are coprime,   but we will ignore this for this task.

Either by implementing the algorithm, by using a dedicated library or by using a built-in function in your language,   compute the modular inverse of   42 modulo 2017.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Modular inverse step by step in the Quackery programming language

Source code in the quackery programming language

  [ dup 1 != if
      [ tuck 1 0
        [ swap temp put
          temp put
          over 1 > while
          tuck /mod swap
          temp take tuck *
          temp take swap -
          again ]
        2drop
        temp release
        temp take
        dup 0 < if
          [ over + ] ]
    nip ]                 is modinv ( n n --> n )

  42 2017 modinv echo

  [ dup 0 = iff
      [ 2drop 1 0 ]
      done
    dup unrot /mod
    dip swap recurse
    tuck 2swap *
    dip swap - ]        is egcd    ( n n --> n n )

  [ dup 0 < if negate
    over 0 < if
      [ swap negate
        over tuck mod
        - swap ]
    dup rot 2dup egcd
    2swap 2over rot *
    unrot * + 1 != iff
      [ drop 2drop -1 ]
      done
    nip swap mod ]      is modinv ( n n --> n   )

say "  42 2017 modinv --> "   42 2017 modinv echo cr ( --> 1969 )
say "  40    1 modinv --> "   40    1 modinv echo cr ( --> 0    )
say "  52 -217 modinv --> "   52 -217 modinv echo cr ( --> 96   )
say "-486  217 modinv --> " -486  217 modinv echo cr ( --> 121  )
say "  40 2018 modinv --> "   40 2018 modinv echo cr ( --> -1   )

You may also check:How to resolve the algorithm Twin primes step by step in the Ruby programming language
You may also check:How to resolve the algorithm Twelve statements step by step in the Mathematica/Wolfram Language programming language
You may also check:How to resolve the algorithm Environment variables step by step in the BASIC programming language
You may also check:How to resolve the algorithm Runge-Kutta method step by step in the R programming language
You may also check:How to resolve the algorithm Read a configuration file step by step in the Arturo programming language