Task

Create a reasonably complete implementation of rational arithmetic in the particular language using the idioms of the language.



Example

Define a new type called frac with binary operator "//" of two integers that returns a structure made up of the numerator and the denominator (as per a rational number).

Further define the appropriate rational unary operators abs and '-', with the binary operators for addition '+', subtraction '-', multiplication '×', division '/', integer division '÷', modulo division, the comparison operators (e.g. '<', '≤', '>', & '≥') and equality operators (e.g. '=' & '≠').

Define standard coercion operators for casting int to frac etc.

If space allows, define standard increment and decrement operators (e.g. '+:=' & '-:=' etc.).

Finally test the operators:
Use the new type frac to find all perfect numbers less than 219 by summing the reciprocal of the factors.



Related task

   Perfect Numbers


# a and b are assumed to be non-zero integers 
def gcd(a; b):
  # subfunction expects [a,b] as input
  # i.e. a ~ .[0] and b ~ .[1]
  def rgcd: if .[1] == 0 then .[0]
         else [.[1], .[0] % .[1]] | rgcd
         end;
  [a,b] | rgcd;
 
# To take advantage of gojq's support for accurate integer division:
def idivide($j):
  . as $i
  | ($i % $j) as $mod
  | ($i - $mod) / $j ;
 
# To take advantage of gojq's arbitrary-precision integer arithmetic:
def power($b): . as $in | reduce range(0;$b) as $i (1; . * $in);
 
# $p should be an integer or a rational
# $q should be a non-zero integer or a rational
# Output:  a Rational: $p // $q
def r($p;$q):
  def r: if type == "number" then {n: ., d: 1} else . end;
  # The remaining subfunctions assume all args are Rational
  def n: if .d < 0 then {n: -.n, d: -.d} else . end;
  def rdiv($a;$b):
    ($a.d * $b.n) as $denom
    | if $denom==0 then "r: division by 0" | error
    else r($a.n * $b.d; $denom)
    end;
  if $q == 1 and ($p|type) == "number" then {n: $p, d: 1}
  elif $q == 0 then "r: denominator cannot be 0" | error
  else if ($p|type == "number") and ($q|type == "number")
       then gcd($p;$q) as $g
       | {n: ($p/$g), d: ($q/$g)} | n
       else rdiv($p|r; $q|r)
       end
  end;
 
# Polymorphic (integers and rationals in general)
def requal($a; $b):
  if $a | type == "number" and $b | type == "number" then $a == $b
  else r($a;1) == r($b;1)
  end;
 
# Input: a Rational
# Output: a Rational with a denominator that has no more than $digits digits
# and such that |rBefore - rAfter| < 1/(10|power($digits)
# where $digits should be a positive integer.
def rround($digits):
  if .d | length > $digits 
  then (10|power($digits)) as $p
  | .d as $d
  | r($p * .n | idivide($d); $p)
  else . end;
 
# Polymorphic; see also radd/0
def radd($a; $b):
  def r: if type == "number" then {n: ., d: 1} else . end;
    ($a|r) as {n: $na, d: $da}
  | ($b|r) as {n: $nb, d: $db}
  | r( ($na * $db) + ($nb * $da); $da * $db );
 
# Polymorphic; see also rmult/0
def rmult($a; $b):
  def r: if type == "number" then {n: ., d: 1} else . end;
    ($a|r) as {n: $na, d: $da}
  | ($b|r) as {n: $nb, d: $db}
  | r( $na * $nb; $da * $db ) ;
 
# Input: an array of rationals (integers and/or Rationals)
# Output: a Rational computed using left-associativity
def rmult:
  if length == 0 then r(1;1)
  elif length == 1 then r(.[0]; 1)  # ensure the result is Rational
  else .[0] as $first
  | reduce .[1:][] as $x ($first; rmult(.; $x))
  end;
 
# Input: an array of rationals (integers and/or Rationals)
# Output: a Rational computed using left-associativity
def radd:
  if length == 0 then r(0;1)
  elif length == 1 then r(.[0]; 1) # ensure the result is Rational
  else .[0] as $first
  | reduce .[1:][] as $x ($first; radd(. ; $x))
  end;
 
def rabs: r(.;1) | r(.n|length; .d|length);
 
def rminus: r(-1 * .n; .d);
 
def rminus($a; $b): radd($a; rmult(-1; $b));
 
# Note that rinv does not check for division by 0
def rinv: r(1; .);
 
def rdiv($a; $b): r($a; $b);
 
# Input: an integer or a Rational, $p
# Output: $p < $q
def rlessthan($q):
  # lt($b) assumes . and $b have the same sign 
  def lt($b):
    . as $a
    | ($a.n * $b.d) < ($b.n * $a.d);
 
  if $q|type == "number" then rlessthan(r($q;1))
  else if type == "number" then r(.;1) else . end
  | if .n < 0
    then if ($q.n >= 0) then true
         else . as $p | ($q|rminus | rlessthan($p|rminus))
         end
    else lt($q)
    end
  end;
 
def rgreaterthan($q):
  . as $p | $q | rlessthan($p);
 
def rlessthanOrEqual($q): requal(.;$q) or rlessthan($q);
def rgreaterthanOrEqual($q): requal(.;$q) or rgreaterthan($q);
 
# Input: non-negative integer or Rational
def rsqrt(precision):
  r(.;1) as $n
  | (precision + 1) as $digits
  | def update: rmult( r(1;2); radd(.x; rdiv($n; .x))) | rround($digits);
 
  | def update: rmult( r(1;2); radd(.x; rdiv($n; .x)));
 
  r(1; 10|power(precision)) as $p
  | { x: .}
  | .root = update
  | until( rminus(.root; .x) | rabs | rlessthan($p);
      .x = .root
      | .root = update )
  | .root ;
 
# Use native floats
# q.v. r_to_decimal(precision)
def r_to_decimal: .n / .d;
 
# Input: a Rational, or {n, d} in general, or an integer.
# Output: a string representation of the input as a decimal number.
# If the input is a number, it is simply converted to a string.
# Otherwise, $precision determines the number of digits after the decimal point,
# obtained by truncating, but trailing 0s are omitted.
# Examples assuming $digits is 5:
#  -0//1 => "0"
#   2//1 => "2"
#   1//2 => "0.5"
#   1//3 => "0.33333"
#   7//9 => "0.77777"
#   1//100 => "0.01"
#  -1//10 => "-0.1"
#   1//1000000 => "0."
def r_to_decimal($digits):
  if .n == 0 # captures the annoying case of -0
  then "0"
  elif type == "number" then tostring
  elif .d < 0 then {n: -.n, d: -.d}|r_to_decimal($digits)
  elif .n < 0
  then "-" + ((.n = -.n) | r_to_decimal($digits))
  else (10|power($digits)) as $p
  | .d as $d
  | if $d == 1 then .n|tostring
    else ($p * .n | idivide($d) | tostring) as $n
    | ($n|length) as $nlength
    | (if $nlength > $digits then $n[0:$nlength-$digits] + "." + $n[$nlength-$digits:]
       else "0." + ("0"*($digits - $nlength) + $n)
       end) | sub("0+$";"")
    end
  end;
 
# pretty print ala Julia
def rpp: "\(.n) // \(.d)";