(48G) 48G, 49G & 50G: Multiplicative Inverse of a Bint Modulo 2^20

[Gerald H]

The title says it.

If you have a faster algorithm please say.

Code:


::
  CK1&Dispatch
  # 1F
  ::
    BINT1
    BINT19
    ZERO_DO
    OVER
    #*
    SWAPDUP
    #*
    SWAPLOOP
    SWAPDROP
  ;
;

[Gerald H]

Carmichael

https://en.wikipedia.org/wiki/Carmichael_function

says we can simplify the algorithm to:

Code:


::
  CK1&Dispatch
  # 1F
  ::
    BINT1
    BINT18
    ZERO_DO
    OVER
    #*
    SWAPDUP
    #*
    SWAPLOOP
    SWAPDROP
  ;
;