ALGOL 68/prelude

The following summarises the useful and various ALGOL 68 prelude templates. These are used in several ALGOL 68 code samples.

pow_mod.a68

Used in: Miller-Rabin test and Multiplicative order. Could be used in Trial factoring of a Mersenne number.

COMMENT
  This routine is used in more than one place, and is essentially a
  template that can by used for many different types, eg INT, LONG INT...
USAGE
  MODE POWMODSTRUCT = INT, LONG INT, COMPL, FRAC, MODULAS, MATRIX etc
  PR READ "prelude/pow_mod.a68" PR
END COMMENT

PROC pow mod = (POWMODSTRUCT b,in e, mod)POWMODSTRUCT: (
  POWMODSTRUCT sq := b, e := in e;
  POWMODSTRUCT out:= IF ODD e THEN b ELSE 1 FI;
  e:=e OVER 2;
  WHILE e /= 0 DO
    sq := sq * sq %* mod;
    IF ODD e THEN out := out * sq %* mod FI ;
    e:=e OVER 2
  OD;
  out
)

sort.a68

Used in: Multiplicative order and Sort most popular programming languages.

COMMENT
  This routine is used in more then one place, and is essentially a
  template that can by used for many different types, eg INT, LONG INT...
USAGE
  MODE SORTSTRUCT = INT, LONG INT, STRUCT(STRING name, addr) etc
  OP < = (SORTSTRUCT a,b)BOOL: ~;

  PR READ "prelude/sort.a68" PR;
  [3]SORTSTRUCT list := (a,b,c);
  print((in place shell sort(list), new line))
END COMMENT

 PROC in place shell sort = (REF FLEX []SORTSTRUCT seq)REF[]SORTSTRUCT:(
     INT inc := ( UPB seq + LWB seq + 1 ) OVER 2;
     WHILE inc NE 0 DO
         FOR index FROM LWB seq TO UPB seq DO
             INT i := index;
             SORTSTRUCT el = seq[i];
             WHILE ( i  - LWB seq >= inc | NOT(seq[i - inc] < el) | FALSE ) DO
                 seq[i] := seq[i - inc];
                 i -:= inc
             OD;
             seq[i] := el
         OD;
         inc := IF inc = 2 THEN 1 ELSE ENTIER(inc * 5 / 11) FI
     OD;
     seq
 );

 PROC in place shell sort reverse = (REF FLEX []SORTSTRUCT seq)REF[]SORTSTRUCT:(
     INT inc := ( UPB seq + LWB seq + 1 ) OVER 2;
     WHILE inc NE 0 DO
         FOR index FROM LWB seq TO UPB seq DO
             INT i := index;
             SORTSTRUCT el = seq[i];
             WHILE ( i  - LWB seq >= inc | seq[i - inc] < el | FALSE ) DO
                 seq[i] := seq[i - inc];
                 i -:= inc
             OD;
             seq[i] := el
         OD;
         inc := IF inc = 2 THEN 1 ELSE ENTIER(inc * 5 / 11) FI
     OD;
     seq
 );
 SKIP