Subversion Repositories ratpack

--------------------------------------------------------------------------------
-- Filename: ratpack.vhd
-- Purpose : Rational arithmetic package
-- Author  : Nikolaos Kavvadias <nikolaos.kavvadias@gmail.com>
-- Date    : 21-Feb-2014
-- Version : 0.1.0
-- Revision: 0.0.0 (2009/07/25)
--           Initial version. Added the definition of a rational number, and the
--           implementation of the "+", "-", "*", "/" operators on reduced
--           rational numbers (i.e. relative primes), the gcd(x,y) and the
--           mediant operator.
--           0.0.1 (2009/07/28)
--           Added: numerator, denominator, abs, relational operators (>, <, >=,
--           <=, =, /=, changed the int2rat to to_rational, new version of
--           int2rat (casting an integer to a rational).
--           0.0.2 (2010/11/17)
--           Added an iterative version for the gcd computation (gcditer).
--           0.0.3 (2012/02/11)
--           Added max, min.
--           0.1.0 (2014/02/21)
--           Upgraded to version 0.1.0.
-- License : Copyright (C) 2009, 2010, 2011, 2012, 2013, 2014 by Nikolaos Kavvadias
--           This program is free software. You can redistribute it and/or 
--           modify it under the terms of the GNU Lesser General Public License, 
--           either version 3 of the License, or (at your option) any later 
--           version. See COPYING.
--
--------------------------------------------------------------------------------
 
package ratpack is 
 
  -- A rational number is defined by the pair (numerator, denominator) where 
  -- both numbers. -- are in the range [-16384, 16383].
  constant numer : INTEGER := 0; -- numerator
  constant denom : INTEGER := 1; -- denominator
  type rational is array (natural range numer to denom) of 
    integer; -- range -16384 to 16383;
  constant RAT_ZERO : rational := (0, 1);
  constant RAT_ONE  : rational := (1, 1);
 
  function to_rational (a, b : integer) return rational;
  function int2rat (a : integer) return rational;
  function numerator (a : rational) return integer;
  function denominator (a : rational) return integer;
  function "+" (a, b : rational) return rational;
  function "-" (a, b : rational) return rational;
  function "*" (a, b : rational) return rational;
  function "/" (a, b : rational) return rational;
  function "abs" (a : rational)  return rational;
  function max (a, b : rational) return rational;
  function min (a, b : rational) return rational;
  function ">" (a, b : rational) return boolean;
  function "<" (a, b : rational) return boolean;
  function ">=" (a, b : rational) return boolean;
  function "<=" (a, b : rational) return boolean;
  function "=" (a, b : rational) return boolean;
  function "/=" (a, b : rational) return boolean;
  function gcd (a, b : integer)  return integer;
  function gcditer (a, b : integer)  return integer;
  function mediant (a, b : rational) return rational;
 
end ratpack;
 
 
package body ratpack is
 
  function to_rational (a, b : integer) return rational is
    variable r : rational;
  begin
    r(numer) := a;
    r(denom) := b;
    return r;
  end to_rational;
 
  function int2rat (a : integer) return rational is
    variable r : rational;
  begin
    r(numer) := a;
    r(denom) := 1;
    return r;
  end int2rat;
 
  function numerator (a : rational) return integer is
    variable n : integer;
  begin
    n := a(numer);
    return n;
  end numerator;
 
  function denominator (a : rational) return integer is
    variable d : integer;
  begin
    d := a(denom);
    return d;
  end denominator;
 
  function "+" (a, b : rational) return rational is
    variable r : rational;
    variable tn, td : integer;
  begin
    tn := a(numer)*b(denom) + a(denom)*b(numer);
    td := a(denom) * b(denom);
    if ( gcd(abs(tn), abs(td)) > 0 ) then
      r(numer) := tn / gcd(abs(tn), abs(td));
      r(denom) := td / gcd(abs(tn), abs(td));
    else
      r(numer) := tn;
      r(denom) := td;
    end if;
    return r;
  end "+";
 
  function "-" (a, b : rational) return rational is
    variable r : rational;
    variable tn, td : integer;
  begin
    tn := a(numer)*b(denom) - a(denom)*b(numer);
    td := a(denom) * b(denom);
    if ( gcd(abs(tn), abs(td)) > 0 ) then
      r(numer) := tn / gcd(abs(tn), abs(td));
      r(denom) := td / gcd(abs(tn), abs(td));
    else
      r(numer) := tn;
      r(denom) := td;
    end if;
    return r;
  end "-";
 
  function "*" (a, b : rational) return rational is
    variable r : rational;
    variable tn, td : integer;
  begin
    tn := a(numer) * b(numer);
    td := a(denom) * b(denom);
    if ( gcd(abs(tn), abs(td)) > 0 ) then
      r(numer) := tn / gcd(abs(tn), abs(td));
      r(denom) := td / gcd(abs(tn), abs(td));
    else
      r(numer) := tn;
      r(denom) := td;
    end if;
    return r;
  end "*";
 
  function "/" (a, b : rational) return rational is
    variable r : rational;
    variable tn, td : integer;
  begin
    tn := a(numer) * b(denom);
    td := a(denom) * b(numer);
    if ( gcd(abs(tn), abs(td)) > 0 ) then
      r(numer) := tn / gcd(abs(tn), abs(td));
      r(denom) := td / gcd(abs(tn), abs(td));
    else
      r(numer) := tn;
      r(denom) := td;
    end if;
    return r;
  end "/";
 
  function "abs" (a : rational) return rational is
    variable ta, tb, y : integer;
    variable r : rational;
  begin
    ta := a(numer);
    tb := a(denom);
    if (ta < 0) then
      ta := - a(numer);
    end if;
    if (tb < 0) then
      tb := - a(denom);
    end if;
    r := to_rational(ta, tb);
    return r;
  end "abs";
 
  function max (a, b : rational) return rational is
    variable w, x, y, z : integer;
    variable t1, t2 : integer;
    variable maxv : rational;
  begin
    w := numerator(a);
    x := denominator(a);
    y := numerator(b);
    z := denominator(b);
    t1 := w*z;
    t2 := x*y;
    if (t1 > t2) then
      maxv := a;
    else
      maxv := b;
    end if; 
    return maxv;
  end max;
 
  function min (a, b : rational) return rational is
    variable w, x, y, z : integer;
    variable t1, t2 : integer;
    variable minv : rational;
  begin
    w := numerator(a);
    x := denominator(a);
    y := numerator(b);
    z := denominator(b);
    t1 := w*z;
    t2 := x*y;
    if (t1 < t2) then
      minv := a;
    else
      minv := b;
    end if; 
    return minv;
  end min;  
 
  function ">" (a, b : rational) return boolean is
    variable diff : rational := a - b;
  begin
    return (((diff(numer) > 0) and (diff(denom) > 0)) or 
            ((diff(numer) < 0) and (diff(denom) < 0)));
  end ">";
 
  function "<" (a, b : rational) return boolean is
    variable diff : rational := a - b;
  begin
    return (((diff(numer) > 0) and (diff(denom) < 0)) or 
            ((diff(numer) < 0) and (diff(denom) > 0)));
  end "<";
 
  function ">=" (a, b : rational) return boolean is
    variable diff : rational := a - b;
  begin
    return (((diff(numer) >= 0) and (diff(denom) > 0)) or 
            ((diff(numer) <= 0) and (diff(denom) < 0)));
  end ">=";
 
  function "<=" (a, b : rational) return boolean is
    variable diff : rational := a - b;
  begin
    return (((diff(numer) >= 0) and (diff(denom) < 0)) or 
            ((diff(numer) <= 0) and (diff(denom) > 0)));
  end "<=";
 
  function "=" (a, b : rational) return boolean is
    variable diff : rational := a - b;
  begin
    return (diff(numer) = 0);
  end "=";
 
  function "/=" (a, b : rational) return boolean is
    variable diff : rational := a - b;
  begin
    return (diff(numer) /= 0);
  end "/=";
 
  function gcd (a, b : integer) return integer is
  begin
    if a = 0 then
      return b;
    end if;
    if b = 0 then
      return a;
    end if;
    if (a > b) then
      return gcd(b, a mod b);
    else
      return gcd(a, b mod a);
    end if;
  end gcd;
 
  function gcditer (a, b : integer) return integer is
    variable x, y : integer;
  begin
    x := a;
    y := b;
    if ((x = 0) and (y = 0)) then
      return 0;
    end if;
    while (x /= y) loop
      if (x >= y) then
        x := x - y;
      else
        y := y - x;
      end if;
    end loop;
    return x;
  end gcditer;
 
  function mediant (a, b : rational) return rational is
    variable r : rational;
    variable tn, td : integer;
  begin
    tn := a(numer) + b(numer);
    td := a(denom) + b(denom);
    if ( gcditer(abs(tn), abs(td)) > 0 ) then
      r(numer) := tn / gcditer(abs(tn), abs(td));
      r(denom) := td / gcditer(abs(tn), abs(td));
    else
      r(numer) := tn;
      r(denom) := td;
    end if;
    return r;
  end mediant;
 
end ratpack;