rat.sa
Generated by gen_html_sa_files from ICSI. Contact gomes@icsi.berkeley.edu for details
---------------------------> Sather 1.1 source file <--------------------------
-- Copyright (C) International Computer Science Institute, 1994. COPYRIGHT --
-- NOTICE: This code is provided "AS IS" WITHOUT ANY WARRANTY and is subject --
-- to the terms of the SATHER LIBRARY GENERAL PUBLIC LICENSE contained in --
-- the file "Doc/License" of the Sather distribution. The license is also --
-- available from ICSI, 1947 Center St., Suite 600, Berkeley CA 94704, USA. --
--------> Please email comments to sather-bugs@icsi.berkeley.edu. <----------
-- Implementation of rational numbers.
immutable class RAT < $IS_LT{RAT}, $STR
immutable class RAT < $IS_LT{RAT}, $STR is
-- Rational numbers. A rational number is represented by by two
-- integers u and v (numerator and denominator) and always
-- normalized, i.e. u.gcd(v) = 1 and v > 0.
include COMPARABLE;
readonly attr u, v: INTI; -- numerator, denominator
-------------------------------------------------- object creation
create (u: INTI): SAME is
r: SAME; return r.u(u).v(#INTI(1))-- RAT::u RAT::v INTI::create
end;
create (u: INT): SAME is
return create(#INTI(u))
end;
create (u, v: INTI): SAME is
assert ~v.is_zero;-- INTI::is_zero
if u.is_zero then v := #INTI(1)-- INTI::is_zero INTI::create
else g ::= u.gcd(v);-- INTI::gcd
if v.is_neg then g := -g end;-- INTI::is_neg INTI::negate
u := u/g; v := v/g-- INTI::div INTI::div
end;
assert v.is_pos;-- INTI::is_pos
r: SAME; return r.u(u).v(v)-- RAT::u RAT::v
end;
create (u, v: INT): SAME is
return create(#INTI(u), #INTI(v))
end;
-------------------------------------------------- binary arithmetics
plus (y: SAME): SAME is return #SAME(u*y.v + v*y.u, v*y.v) end;
minus (y: SAME): SAME is return #SAME(u*y.v - v*y.u, v*y.v) end;
times (y: SAME): SAME is return #SAME(u*y.u, v*y.v) end;
div (y: SAME): SAME is assert ~y.u.is_zero; return #SAME(u*y.v, v*y.u) end;
mod (y: SAME): SAME is return self - #SAME((self/y).floor)*y end;
pow (i: INT): SAME is
-- Returns self raised to the power i. Returns 1 for i < 0.
--
x ::= self; z ::= #SAME(1);
loop while!(i > 0);
-- z * x^i = self ^ i0
if i.is_odd then z := z*x end;
x := x.square; i := i/2
end;
return z
end;
hash:INT is return u.hash.bxor(v.hash) end;-- RAT::u INTI::hash INT::bxor RAT::v INTI::hash
-------------------------------------------------- binary relations
is_eq (y: SAME): BOOL is return (u = y.u) and (v = y.v) end;-- RAT::u INTI::is_eq RAT::u RAT::v INTI::is_eq RAT::v
is_neq (y: SAME): BOOL is return (u /= y.u) or (v /= y.v) end;
is_lt (y: SAME): BOOL is return u*y.v < v*y.u end;
is_leq (y: SAME): BOOL is return u*y.v <= v*y.u end;
is_gt (y: SAME): BOOL is return u*y.v > v*y.u end;
is_geq (y: SAME): BOOL is return u*y.v >= v*y.u end;
-------------------------------------------------- unary predicates
is_pos: BOOL is return u.is_pos end;
is_neg: BOOL is return u.is_neg end;
is_zero: BOOL is return u.is_zero end;
is_int: BOOL is return v = #INTI(1) end;-- RAT::v INTI::is_eq INTI::create
-------------------------------------------------- unary functions
abs: SAME is r: SAME; return r.u(u.abs).v(v) end;
negate: SAME is r: SAME; return r.u(-u).v(v) end;-- RAT::u RAT::u INTI::negate RAT::v RAT::v
sign: INT is return u.sign end;
square: SAME is r: SAME; return r.u(u.square).v(v.square) end;
cube: SAME is r: SAME; return r.u(u.cube).v(v.cube) end;
floor: INTI is return u/v end;-- RAT::u RAT::v
ceiling: INTI is raise "RAT::ceiling not implemented" end;
-------------------------------------------------- miscellaneous
float (n, b: INT): TUP{BOOL, INTI, INT, BOOL} pre (n > 0) and (b > 1) is-- INT::is_lt INT::is_lt
-- Returns the floating point number x = s * m * b^e that is
-- closest to self. x is returned in form of a 4-tupel (s, m, e, a).
-- n specifies the length of the mantissa m in no. of digits to the
-- base b. The mantissa is either 0 (self = 0) or normalized, i.e.
-- it holds: b^(n-1) <= mantissa < b^n. The sign s indicates a
-- negative number. The flag a indicates that x is accurate
-- (i.e. x = self). Rounding to the nearest is used; ties are
-- broken by rounding to even (IEEE rounding).
--
-- The implementation is essentialy AlgorithmM described by
-- W.D. Clinger in "How to Read Floating Point Numbers
-- Accurately", PLDI 1990 proceedings, p. 92-101.
--
if u.is_zero then return #(false, #INTI(0), 0, true)-- RAT::u INTI::is_zero TUP{4}::create INTI::create
else
beta ::= #INTI(b);-- INTI::create
beta_n1 ::= beta^(n-1);-- INTI::pow INT::minus
beta_n ::= beta_n1 * beta;-- INTI::times
s ::= self.u.is_neg;-- RAT::u INTI::is_neg
u ::= self.u.abs;-- RAT::u INTI::abs
v ::= self.v; assert v.is_pos;-- RAT::v INTI::is_pos
-- u/v = |self|
-- approximation for e
e ::= u.log2 - v.log2;-- INTI::log2 INT::minus INTI::log2
if b /= 2 then e := (e.flt / b.flt.log2).round.int end;-- INT::is_eq BOOL::not INT::flt FLT::div INT::flt FLT::log2 FLT::round FLT::int
e := e-n;-- INT::minus
if e < 0 then u := u * beta^(-e)-- INT::is_lt INTI::times INTI::pow INT::negate
else v := v * beta^e-- INTI::times INTI::pow
end;
-- normalize
-- (usually 0 or 1 iteration steps required)
m: INTI;
loop
-- u/v * b^e = |self|
m := u/v;-- INTI::div
if m < beta_n1 then u := u*beta; e := e-1-- INTI::is_lt INTI::times INT::minus
elsif m >= beta_n then v := v*beta; e := e+1-- INTI::is_lt BOOL::not INTI::times INT::plus
else break!
end
end;
-- (u/v * b^e = |self|) & (b^(n-1) <= u/v < b^n)
-- conversion to float & rounding to nearest (IEEE)
r ::= u%v; v_r ::= v-r;-- INTI::mod INTI::minus
if (r > v_r) or ((r = v_r) and m.is_odd) then -- next float-- INTI::is_lt INTI::is_eq INTI::is_odd
m := m + #INTI(1);-- INTI::plus INTI::create
if m = beta_n then m := beta_n1; e := e+1 end-- INTI::is_eq INT::plus
end;
return #(s, m, e, r.is_zero)-- TUP{4}::create INTI::is_zero
end
end;
-------------------------------------------------- output
str: STR is
-- Returns a string representation of self in the form
-- u/v or u (if self.is_int).
--
if is_int then return u.str-- RAT::is_int RAT::u INTI::str
else return u.str + '/' + v.str-- RAT::u INTI::str STR::plus RAT::v INTI::str
end
end;
str (n: INT): STR pre n > 0 is-- INT::is_lt
-- Returns a string representation of self in decimal floating
-- point form [sign] digit '.' {digit} ['e' [sign] digit {digit}] where
-- n specifies the number of digits of the mantissa.
--
x ::= float(n, 10); s ::= "";-- RAT::float
if x.t1 then s := s + '-' end;-- TUP{4}::t1 STR::plus
m::=x.t2.str;-- TUP{4}::t2 INTI::str
digits::=m.length;-- STR::length
trailing_zeros:INT;
loop
trailing_zeros:=0.upto!(digits-1);-- INT::upto! INT::minus
while!(m[digits-1-trailing_zeros]='0');-- STR::aget INT::minus INT::minus CHAR::is_eq
end;
s := s + m[0] + '.';-- STR::plus STR::aget STR::plus
after_decimal::=digits-1-trailing_zeros;-- INT::minus INT::minus
if after_decimal>0 then-- INT::is_lt
s := s + m.substring(1,after_decimal); -- STR::plus STR::substring
end;
e ::= x.t3 + digits-1;-- TUP{4}::t3 INT::plus INT::minus
if e /= 0 then s := s + 'e' + e end;-- INT::is_eq BOOL::not STR::plus STR::plus
return s
end;
end