Modular arithmetic: Difference between revisions

=={{header|Forth}}

\ We would normally define operators that have a suffix `m' in order

\ not be confused: +m -m *m /m **m

\ Also useful is %:m reduce a number modulo.

\ Words that may be not be present in the kernel.

\ This example loads them in ciforth.

WANT ALIAS VOCABULARY

VARIABLE _m ( Modulo number)

\ Set the modulus to m .

: set-modulus _m ! ;

\ For A B return C GCD where C*A+x*B=GCD

: XGCD 1 0 2SWAP BEGIN OVER /MOD OVER WHILE >R SWAP

2SWAP OVER R> * - SWAP 2SWAP REPEAT 2DROP NIP ;

\ Suffix n : normalized number.

: _norm_-m DUP 0< _m @ AND + ; ( x -- xn ) \ -m<xn<+m

: +m + _m @ - _norm_-m ; ( an bn -- sumn )

: -m - _norm_-m ; ( an bn -- diffn)

: *m M* _m @ SM/REM DROP ; ( an bn -- prodn)

: /m _m @ XGCD DROP _norm_-m *m ; ( a b -- quotn)

: %:m S>D _m @ SM/REM DROP _norm_-m ; ( a -- an)

\ Both steps: For A B and C: return A B en C. Invariant A*B^C.

: _reduce_1- 1- >R >R R@ *m R> R> ;

: _reduce_2/ 2/ >R DUP *m R> ;

: **m 1 ROT ROT BEGIN DUP 1 AND IF _reduce_1- THEN

_reduce_2/ DUP 0= UNTIL 2DROP ; ( a b -- apowbn )

\ The solution is

13 set-modulus

10 DUP 100 **m +m 1 +m . CR

\ In order to comply with the problem we can generate a separate namespace

\ and import the above definitions.

VOCABULARY MODULO

ALSO MODULO DEFINITIONS

' set-modulus ALIAS set-modulus

' +m ALIAS +

' -m ALIAS -

' *m ALIAS *

' /m ALIAS /

' **m ALIAS **

\ now the calculation becomes

13 set-modulus

10 DUP 100 ** + 1 + . CR