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;