raw
ffa_ch15_gcd.kv         1 ------------------------------------------------------------------------------
ffa_ch15_gcd.kv         2 ------------------------------------------------------------------------------
ffa_ch15_gcd.kv         3 -- This file is part of 'Finite Field Arithmetic', aka 'FFA'.               --
ffa_ch15_gcd.kv         4 --                                                                          --
ffa_ch15_gcd.kv         5 -- (C) 2019 Stanislav Datskovskiy ( www.loper-os.org )                      --
ffa_ch15_gcd.kv         6 -- http://wot.deedbot.org/17215D118B7239507FAFED98B98228A001ABFFC7.html     --
ffa_ch15_gcd.kv         7 --                                                                          --
ffa_ch15_gcd.kv         8 -- You do not have, nor can you ever acquire the right to use, copy or      --
ffa_ch15_gcd.kv         9 -- distribute this software ; Should you use this software for any purpose, --
ffa_ch15_gcd.kv        10 -- or copy and distribute it to anyone or in any manner, you are breaking   --
ffa_ch15_gcd.kv        11 -- the laws of whatever soi-disant jurisdiction, and you promise to         --
ffa_ch15_gcd.kv        12 -- continue doing so for the indefinite future. In any case, please         --
ffa_ch15_gcd.kv        13 -- always : read and understand any software ; verify any PGP signatures    --
ffa_ch15_gcd.kv        14 -- that you use - for any purpose.                                          --
ffa_ch15_gcd.kv        15 --                                                                          --
ffa_ch15_gcd.kv        16 -- See also http://trilema.com/2015/a-new-software-licensing-paradigm .     --
ffa_ch15_gcd.kv        17 ------------------------------------------------------------------------------
ffa_ch15_gcd.kv        18 
ffa_ch15_gcd.kv        19 with Words;    use Words;
ffa_ch15_gcd.kv        20 with FZ_Basic; use FZ_Basic;
ffa_ch15_gcd.kv        21 with FZ_Shift; use FZ_Shift;
ffa_ch15_gcd.kv        22 with FZ_QShft; use FZ_QShft;
ffa_ch15_gcd.kv        23 with FZ_Arith; use FZ_Arith;
ffa_ch21a_bis_fix...   24 with FZ_BitOp; use FZ_BitOp;
ffa_ch15_gcd.kv        25 with FZ_Pred;  use FZ_Pred;
ffa_ch15_gcd.kv        26 
ffa_ch15_gcd.kv        27 
ffa_ch15_gcd.kv        28 package body FZ_GCD is
ffa_ch15_gcd.kv        29    
ffa_ch15_gcd.kv        30    -- Find Greatest Common Divisor (GCD) of X and Y.
ffa_ch15_gcd.kv        31    -- Note that by convention, GCD(0, 0) = 0.
ffa_ch15_gcd.kv        32    procedure FZ_Greatest_Common_Divisor(X      : in  FZ;
ffa_ch15_gcd.kv        33                                         Y      : in  FZ;
ffa_ch15_gcd.kv        34                                         Result : out FZ) is
ffa_ch15_gcd.kv        35       
ffa_ch15_gcd.kv        36       -- Widths of X, Y, and Result are equal
ffa_ch15_gcd.kv        37       subtype Width is Word_Index range X'Range;
ffa_ch15_gcd.kv        38       
ffa_ch15_gcd.kv        39       -- Working buffers for GCD computation, initially equal to the inputs
ffa_ch21a_bis_fix...   40       A      : FZ(Width) := X;
ffa_ch15_gcd.kv        41       B      : FZ(Width) := Y;
ffa_ch15_gcd.kv        42       
ffa_ch15_gcd.kv        43       -- Evenness (negation of lowest bit) of A and B respectively
ffa_ch15_gcd.kv        44       Ae, Be : WBool;
ffa_ch15_gcd.kv        45       
ffa_ch21a_bis_fix...   46       -- Common power-of-2 factor: incremented when Ae and Be are both 1
ffa_ch15_gcd.kv        47       Twos   : Word := 0;
ffa_ch15_gcd.kv        48       
ffa_ch21a_bis_fix...   49       -- This flag is set when A and B are BOTH ODD
ffa_ch21a_bis_fix...   50       OO     : WBool;
ffa_ch21a_bis_fix...   51       
ffa_ch15_gcd.kv        52       -- |A - B|
ffa_ch15_gcd.kv        53       D      : FZ(Width);
ffa_ch15_gcd.kv        54       
ffa_ch15_gcd.kv        55       -- This flag is set iff A < B
ffa_ch15_gcd.kv        56       A_lt_B : WBool;
ffa_ch15_gcd.kv        57       
ffa_ch15_gcd.kv        58    begin
ffa_ch15_gcd.kv        59       
ffa_ch21a_bis_fix...   60       -- To converge, requires number of shots equal to (2 * FZ_Bitness) - 1:
ffa_ch21a_bis_fix...   61       for i in 1 .. (2 * FZ_Bitness(X)) - 1 loop
ffa_ch21a_bis_fix...   62          
ffa_ch21a_bis_fix...   63          -- Whether A and B are currently BOTH ODD :
ffa_ch21a_bis_fix...   64          OO := FZ_OddP(A) and FZ_OddP(B);
ffa_ch21a_bis_fix...   65          
ffa_ch21a_bis_fix...   66          -- D := |A - B|
ffa_ch21a_bis_fix...   67          FZ_Sub_Abs(X => A, Y => B, Difference => D, Underflow => A_lt_B);
ffa_ch21a_bis_fix...   68          
ffa_ch21a_bis_fix...   69          -- IFF A,B both ODD, and A < B : B' := A ; otherwise no change :
ffa_ch21a_bis_fix...   70          FZ_Mux(X => B, Y => A, Result => B, Sel => OO and A_lt_B);
ffa_ch21a_bis_fix...   71          
ffa_ch21a_bis_fix...   72          -- IFF A,B both ODD: A' := |A - B| ; otherwise no change :
ffa_ch21a_bis_fix...   73          FZ_Mux(X => A, Y => D, Result => A, Sel => OO);
ffa_ch15_gcd.kv        74          
ffa_ch21a_bis_fix...   75          -- If A is now EVEN: A := A >> 1; otherwise no change
ffa_ch15_gcd.kv        76          Ae := 1 - FZ_OddP(A);
ffa_ch15_gcd.kv        77          FZ_ShiftRight(A, A, WBit_Index(Ae));
ffa_ch15_gcd.kv        78          
ffa_ch21a_bis_fix...   79          -- If B is now EVEN: B := B >> 1; otherwise no change
ffa_ch15_gcd.kv        80          Be := 1 - FZ_OddP(B);
ffa_ch15_gcd.kv        81          FZ_ShiftRight(B, B, WBit_Index(Be));
ffa_ch15_gcd.kv        82          
ffa_ch15_gcd.kv        83          -- If both A and B were even, increment the common power-of-two
ffa_ch15_gcd.kv        84          Twos := Twos + (Ae and Be);
ffa_ch15_gcd.kv        85          
ffa_ch15_gcd.kv        86       end loop;
ffa_ch15_gcd.kv        87       
ffa_ch21a_bis_fix...   88       -- Normally, B will contain the GCD, but in the (N,0) N > 0 case -- A.
ffa_ch21a_bis_fix...   89       -- The other variable will always equal 0. Hence, take Bitwise-OR(A,B):
ffa_ch21a_bis_fix...   90       FZ_Or(X => A, Y => B, Result => A);
ffa_ch21a_bis_fix...   91       
ffa_ch15_gcd.kv        92       -- Reintroduce the common power-of-2 factor stored in 'Twos'
ffa_ch15_gcd.kv        93       FZ_Quiet_ShiftLeft(N => A, ShiftedN => A, Count => Indices(Twos));
ffa_ch15_gcd.kv        94       
ffa_ch21a_bis_fix...   95       -- Output final result -- the GCD.
ffa_ch15_gcd.kv        96       Result := A;
ffa_ch15_gcd.kv        97       
ffa_ch15_gcd.kv        98    end FZ_Greatest_Common_Divisor;
ffa_ch15_gcd.kv        99    
ffa_ch15_gcd.kv       100 end FZ_GCD;