program HCFACTOR { Highest Common Factor ; BP7, D3 DCC32 -cc
  Note that relative speed depends on compiler - check as per actual use. } ;

{$I version.pas}

{$IFDEF DELPHI} uses Windows ; {$ENDIF}

type Number = integer ;
const Min : Number = 1 ; Max : Number = 1000 ;


{$IFDEF PASCAL}
function GetTickCount : longint ;
begin GetTickCount := MemL[$40:$6C] end {GetTickCount} ;
{$ENDIF}


function HCF1(const x, y : Number) : Number ;
begin if x<y then HCF1 := HCF1(y, x) else if y=0 then HCF1 := x
    else HCF1 := HCF1(x mod y, y) end {HCF1} ;


function Euc1(U, V : Number) : Number ;
{} procedure Swap ; var Temp : Number ;
{}   begin Temp := U ; U := V ; V := Temp end ;
begin repeat
    if U < V then Swap ;
    U := U - V ;
    until U = 0 ;
  Euc1 := V end {Euc1} ;


function Euc2(U, V : Number) : Number ;
{} procedure Swap ; var Temp : Number ;
{}   begin Temp := U ; U := V ; V := Temp end ;
begin repeat
    if U < V then Swap ;
    U := U mod V ;
    until U = 0 ;
  Euc2 := V end {Euc2} ;


function Euc3(U, V : Number) : Number { after Bob Lee } ;
begin while U<>V do
    if U < V then V := V-U else U := U-V ;
  Euc3 := U end {Euc3} ;


function Euc4(U, V : Number) : Number ;
begin while U<>V do
    if U < V
    then begin V := V mod U ;
    if V=0 then begin Euc4 := U ; EXIT end
    end else begin U := U mod V ;
    if U=0 then begin Euc4 := V ; EXIT end
    end ;
  Euc4 := U end {Euc4} ;


function Euc5(U, V : Number) : Number { after Duncan Murdoch } ;
{$IFNDEF DELPHI} var Result : Number ; {$ENDIF}
begin
  while U <> 0 do begin
    Result := U ;
    U := V mod U ;
    V := Result ;
    end ;
  {$IFNDEF DELPHI} Euc5 := Result ; {$ENDIF}
  end {Euc5} ;



function HCF2(U, V : Number) : Number { JRS } ;
begin repeat
    U := U mod V ; if U=0 then begin HCF2 := V ; EXIT end ;
    V := V mod U ; if V=0 then begin HCF2 := U ; EXIT end ;
    until false end {HCF2} ;


function AvZo(X, Y: Number): Number;
{ after Avatar Zondertau in borland.public.delphi.language.delphi.general
  2005-04-03   Message-ID: <424faeae@newsgroups.borland.com> }
{$IFNDEF DELPHI} var Result : Number ; {$ENDIF}
var
  Count: Integer;
begin
  Count := 0;
  while (X <> 0) and (Y <> 0) do
    if X and 1 = 0 then
      if Y and 1 = 0 then
      begin
        Inc(Count);
        X := X shr 1;
        Y := Y shr 1;
      end
      else
        X := X shr 1
    else
      if Y and 1 = 0 then
        Y := Y shr 1
      else
        if X > Y then
          X := X - Y
        else
          Y := Y - X;
  if X = 0 then
    Result := Y shl Count
  else
    Result := X shl Count;     
  {$IFNDEF DELPHI} AvZo := Result ; {$ENDIF}
end;


var J, K, L : Number ; T : longint ;


BEGIN Writeln(
  'HCFACTOR.PAS [Max [Min]]  www.merlyn.demon.co.uk   >= 2005-05-06') ;

Writeln('Checking parameters :') ;
if ParamCount>0 then begin Val(ParamStr(1), Max, J) ;
  if (J<>0) or (Max<1) then HALT ; end ;
if ParamCount>1 then begin Val(ParamStr(2), Min, J) ;
  if (J<>0) or (Min<1) or (Min>Max) then HALT ; end ;

Writeln(
  ' Timing each HCF(J, K) for all J, K in ', Min, ' .. ', Max, '; unit = ',
  {$IFDEF PASCAL} '18.2', {$ENDIF} {$IFDEF DELPHI} '1', {$ENDIF} ' ms.') ;

T := GetTickCount ;
for J := Min to Max do for K := Min to Max do L := -L ;
Writeln('  null :', GetTickCount-T:6) ;

T := GetTickCount ;
for J := Min to Max do for K := Min to Max do L := HCF1(J, K) ;
Writeln('  HCF1 :', GetTickCount-T:6) ;

T := GetTickCount ;
for J := Min to Max do for K := Min to Max do L := EUC1(J, K) ;
Writeln('  EUC1 :', GetTickCount-T:6) ;

T := GetTickCount ;
for J := Min to Max do for K := Min to Max do L := EUC2(J, K) ;
Writeln('  EUC2 :', GetTickCount-T:6) ;

T := GetTickCount ;
for J := Min to Max do for K := Min to Max do L := EUC3(J, K) ;
Writeln('  EUC3 :', GetTickCount-T:6) ;

T := GetTickCount ;
for J := Min to Max do for K := Min to Max do L := EUC4(J, K) ;
Writeln('  EUC4 :', GetTickCount-T:6) ;

T := GetTickCount ;
for J := Min to Max do for K := Min to Max do L := EUC5(J, K) ;
Writeln('  EUC5 :', GetTickCount-T:6) ;

T := GetTickCount ;
for J := Min to Max do for K := Min to Max do L := HCF2(J, K) ;
Writeln('  HCF2 :', GetTickCount-T:6) ;

T := GetTickCount ;
for J := Min to Max do for K := Min to Max do L := AvZo(J, K) ;
Writeln('  AvZo :', GetTickCount-T:6) ;

Writeln(' Comparing all HCF(J, K) for all J, K in ', Min, ' .. ', Max, '.') ;
for J := Min to Max do begin Write(#13, J:7) ;
  for K := Min to Max do begin L := HCF1(J, K) ;
    if HCF2(J, K)<>L then Writeln(' HCF2 ', J, #32, K) ;
    if Euc1(J, K)<>L then Writeln(' Euc1 ', J, #32, K) ;
    if Euc2(J, K)<>L then Writeln(' Euc2 ', J, #32, K) ;
    if Euc3(J, K)<>L then Writeln(' Euc3 ', J, #32, K) ;
    if Euc4(J, K)<>L then Writeln(' Euc4 ', J, #32, K) ;
    if Euc5(J, K)<>L then Writeln(' Euc5 ', J, #32, K) ;
    if AvZo(J, K)<>L then Writeln(' AvZo ', J, #32, K) ;
    end ;
  end ;
Write('  OK') ;
Readln ;
END.