Arithmetic/Rational

Arithmetic/Rational
You are encouraged to solve this task according to the task description, using any language you may know.

The objective of this task is to create a reasonably complete implementation of rational arithmetic in the particular language using the idioms of the language.

For example: Define an 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 then 2¹⁹ by summing the reciprocal of the factors.

See also

• Perfect Numbers

Ada

See Rational Arithmetic/Ada

ALGOL 68

Works with: ALGOL 68 version Standard - no extensions to language used

Works with: ALGOL 68G version Any - tested with release mk15-0.8b.fc9.i386

MODE FRAC = STRUCT( INT num #erator#,  den #ominator#);
FORMAT frac repr = $g(-0)"//"g(-0)$;

PROC gcd = (INT a, b) INT: # greatest common divisor #
  (a = 0 | b |: b = 0 | a |: ABS a > ABS b  | gcd(b, a MOD b) | gcd(a, b MOD a));

PROC lcm = (INT a, b)INT: # least common multiple #
  a OVER gcd(a, b) * b;

PROC raise not implemented error = ([]STRING args)VOID: (
  put(stand error, ("Not implemented error: ",args, newline));
  stop
);

PRIO // = 9; # higher then the ** operator #
OP // = (INT num, den)FRAC: ( # initialise and normalise #
  INT common = gcd(num, den);
  IF den < 0 THEN
    ( -num OVER common, -den OVER common)
  ELSE
    ( num OVER common, den OVER common)
  FI
);

OP + = (FRAC a, b)FRAC: (
  INT common = lcm(den OF a, den OF b);
  FRAC result := ( common OVER den OF a * num OF a + common OVER den OF b * num OF b, common );
  num OF result//den OF result
);

OP - = (FRAC a, b)FRAC: a + -b,
   * = (FRAC a, b)FRAC: (
  INT num = num OF a * num OF b,
      den = den OF a * den OF b;
  INT common = gcd(num, den);
  (num OVER common) // (den OVER common)
);

OP /  = (FRAC a, b)FRAC: a * FRAC(den OF b, num OF b),# real division #
   %  = (FRAC a, b)INT: ENTIER (a / b),               # integer divison #
   %* = (FRAC a, b)FRAC: a/b - FRACINIT ENTIER (a/b), # modulo division #
   ** = (FRAC a, INT exponent)FRAC: 
    IF exponent >= 0 THEN
      (num OF a ** exponent, den OF a ** exponent )
    ELSE
      (den OF a ** exponent, num OF a ** exponent )
    FI;

OP REALINIT = (FRAC frac)REAL: num OF frac / den OF frac,
   FRACINIT = (INT num)FRAC: num // 1,
   FRACINIT = (REAL num)FRAC: (
     # express real number as a fraction # # a future execise! #
     raise not implemented error(("Convert a REAL to a FRAC","!"));
     SKIP
   );

OP <  = (FRAC a, b)BOOL: num OF (a - b) <  0,
   >  = (FRAC a, b)BOOL: num OF (a - b) >  0,
   <= = (FRAC a, b)BOOL: NOT ( a > b ),
   >= = (FRAC a, b)BOOL: NOT ( a < b ),
   =  = (FRAC a, b)BOOL: (num OF a, den OF a) = (num OF b, den OF b),
   /= = (FRAC a, b)BOOL: (num OF a, den OF a) /= (num OF b, den OF b);

# Unary operators #
OP - = (FRAC frac)FRAC: (-num OF frac, den OF frac),
   ABS = (FRAC frac)FRAC: (ABS num OF frac, ABS den OF frac),
   ENTIER = (FRAC frac)INT: (num OF frac OVER den OF frac) * den OF frac;

COMMENT Operators for extended characters set, and increment/decrement "commented out" to save space. COMMENT

Example: searching for Perfect Numbers.

FRAC sum:= FRACINIT 0; 
FORMAT perfect = $b(" perfect!","")$;

FOR i FROM 2 TO 2**19 DO 
  INT candidate := i;
  FRAC sum := 1 // candidate;
  REAL real sum := 1 / candidate;
  FOR factor FROM 2 TO ENTIER sqrt(candidate) DO
    IF candidate MOD factor = 0 THEN
      sum :=  sum + 1 // factor + 1 // ( candidate OVER factor);
      real sum +:= 1 / factor + 1 / ( candidate OVER factor)
    FI
  OD;
  IF den OF sum  = 1 THEN
    printf(($"Sum of reciprocal factors of "g(-0)" = "g(-0)" exactly, about "g(0,real width) f(perfect)l$, 
            candidate, ENTIER sum, real sum, ENTIER sum = 1))
  FI
OD

Output:

Sum of reciprocal factors of 6 = 1 exactly, about 1.0000000000000000000000000001 perfect!
Sum of reciprocal factors of 28 = 1 exactly, about 1.0000000000000000000000000001 perfect!
Sum of reciprocal factors of 120 = 2 exactly, about 2.0000000000000000000000000002
Sum of reciprocal factors of 496 = 1 exactly, about 1.0000000000000000000000000001 perfect!
Sum of reciprocal factors of 672 = 2 exactly, about 2.0000000000000000000000000001
Sum of reciprocal factors of 8128 = 1 exactly, about 1.0000000000000000000000000001 perfect!
Sum of reciprocal factors of 30240 = 3 exactly, about 3.0000000000000000000000000002
Sum of reciprocal factors of 32760 = 3 exactly, about 3.0000000000000000000000000003
Sum of reciprocal factors of 523776 = 2 exactly, about 2.0000000000000000000000000005

C

See Rational Arithmetic/C

Common Lisp

Common Lisp has rational numbers built-in and integrated with all other number types. Common Lisp's number system is not extensible so reimplementing rational arithmetic would require all-new operator names.

<lang lisp>(loop for candidate from 2 below (expt 2 19)

     for sum = (+ (/ candidate)
                  (loop for factor from 2 to (isqrt candidate)
                        when (zerop (mod candidate factor))
                          sum (+ (/ factor) (/ (floor candidate factor)))))
     when (= sum 1)
       collect candidate)</lang>

Fortran

This module currently implements only things needed for the perfect test, and few more (assignment from integer and real, the < operator...). For the GCD as function, see GCD

<lang fortran>module FractionModule

 implicit none
 
 type rational
    integer :: numerator, denominator
 end type rational

 interface assignment (=)
    module procedure assign_fraction_int, assign_fraction_float
 end interface
 interface operator (+)
    module procedure add_fraction !, &
         !float_add_fraction, int_add_fraction, &
         !fraction_add_int, fraction_add_float
 end interface
 interface operator (<)
    module procedure frac_lt_frac
 end interface
 interface int
    module procedure frac_int
 end interface int
 interface real
    module procedure frac_real
 end interface real

 real, parameter :: floatprec = 10e6
 private floatprec, lcm , gcd

contains

 ! gcd can be defined here as private,or must be
 ! "loaded" by a proper use statement

 function lcm(a, b)
   integer :: lcm
   integer, intent(in) :: a, b
   
   lcm = a / gcd(a, b) * b
 end function lcm

 ! int (which truncates, does not round)
 function frac_int(aratio)
   integer :: frac_int
   type(rational), intent(in) :: aratio
   frac_int = aratio%numerator / aratio%denominator
 end function frac_int

 ! get the real value of the fraction
 function frac_real(f)
   real :: frac_real
   type(rational), intent(in) :: f

   frac_real = real(f%numerator) / real(f%denominator)
 end function frac_real

 ! frac = frac + frac
 function add_fraction(f1, f2)
   type(rational) :: add_fraction
   type(rational), intent(in) :: f1, f2
   integer :: common
   
   common = lcm(f1%denominator, f2%denominator)
   add_fraction = rational(common / f1%denominator * f1%numerator + &
        common / f2%denominator * f2%numerator, common)
 end function add_fraction

 ! assignment: frac = integer
 subroutine assign_fraction_int(ass, i)
   type(rational), intent(out), volatile :: ass
   integer, intent(in) :: i

   ass = rational(i, 1)
 end subroutine assign_fraction_int

 ! assignment: frac = float(real)
 subroutine assign_fraction_float(ass, f)
   type(rational), intent(out), volatile :: ass
   real, intent(in) :: f

   ass = rational(int(f*floatprec), floatprec) 
 end subroutine assign_fraction_float

 ! simplify (must be called explicitly)
 subroutine simplify_fraction(fr)
   type(rational), intent(inout) :: fr
   integer :: d
   
   d = gcd(fr%numerator, fr%denominator)
   fr = rational(fr%numerator / d, fr%denominator / d)
 end subroutine simplify_fraction

 ! relational frac < frac
 function frac_lt_frac(f1, f2)
   logical :: frac_lt_frac
   type(rational), intent(in) :: f1, f2
   if ( real(f1) < real(f2) ) then
      frac_lt_frac = .TRUE.
   else
      frac_lt_frac = .FALSE.
   end if
 end function frac_lt_frac

end module FractionModule</lang>

Testing this core code:

<lang fortran>program RatTesting

 use fractionmodule

 implicit none

 integer :: i, candidate, factor
 type(rational) :: summa
 character(10) :: pstr

 do i = 2, 2**19
    candidate = i
    summa = rational(1, candidate)
    factor = 2
    do while ( factor < sqrt(real(candidate)) )
       if ( mod(candidate, factor) == 0 ) then
          summa = summa + rational(1, factor) + &
               rational(1, candidate/factor)
          call simplify_fraction(summa)
       end if
       factor = factor + 1
    end do
    if ( summa%denominator == 1 ) then
       if ( int(summa) == 1 ) then
          pstr = 'perfect!'
       else
          pstr = 
       end if
       write (*, '(A,1X,I7, = ,I1, 1X, A8)') 'Sum of recipr. factors of', &
            candidate, int(summa), pstr
    end if
 end do

end program RatTesting</lang>

Haskell

Haskell provides a Rational type, which is really an alias for Ratio Integer (Ratio being a polymorphic type implementing rational numbers for any Integral type of numerators and denominators). The fraction is constructed using the % operator.

<lang haskell>import Data.Ratio

-- simply prints all the perfect numbers main = mapM_ print [candidate

                  | candidate <- [2 .. 2^19],
                    getSum candidate == 1]
 where getSum candidate = 1 % candidate +
                          sum [1 % factor + 1 % (candidate `div` factor)
                              | factor <- [2 .. floor(sqrt(fromIntegral(candidate)))],
                                candidate `mod` factor == 0]</lang>

For a sample implementation of Ratio, see the Haskell 98 Report.

J

J implements rational numbers:

<lang j> 3r4*2r5 3r10</lang>

That said, note that J's floating point numbers work just fine for the stated problem: <lang j> is_perfect_rational=: 2 = (1 + i.) +/@:%@([ #~ 0 = |) ]</lang>

faster version (but the problem, as stated, is still tremendously inefficient): <lang j>factors=: */&>@{@((^ i.@>:)&.>/)@q:~&__ is_perfect_rational=: 2= +/@:%@,@factors</lang>

Exhaustive testing would take forever: <lang j> I.is_perfect_rational@"0 i.2^19 6 28 496 8128

  I.is_perfect_rational@x:@"0 i.2^19x

6 28 496 8128</lang>

More limited testing takes reasonable amounts of time: <lang j> (#~ is_perfect_rational"0) (* <:@+:) 2^i.10x 6 28 496 8128</lang>

JavaScript

See Rational Arithmetic/JavaScript

Mathematica

Mathematica has full support for fractions built-in. If one divides two exact numbers it will be left as a fraction if it can't be simplified. Comparison, addition, division, product et cetera are built-in: <lang Mathematica>4/16 3/8 8/4 4Pi/2 16!/10! Sqrt[9/16] Sqrt[3/4] (23/12)^5 2 + 1/(1 + 1/(3 + 1/4))

1/2+1/3+1/5 8/Pi+Pi/8 //Together 13/17 + 7/31 Sum[1/n,{n,1,100}] (*summation of 1/1 + 1/2 + 1/3 + 1/4+ .........+ 1/99 + 1/100*)

1/2-1/3 a=1/3;a+=1/7

1/4==2/8 1/4>3/8 Pi/E >23/20 1/3!=123/370 Sin[3]/Sin[2]>3/20

Numerator[6/9] Denominator[6/9]</lang> gives back: <lang Mathematica>1/4 3/8 2 2 Pi 5765760 3/4 Sqrt[3]/2 6436343 / 248832 47/17

31/30 (64+Pi^2) / (8 Pi) 522 / 527 14466636279520351160221518043104131447711 / 2788815009188499086581352357412492142272

1/6 10/21

True False True True True

2 3</lang> As you can see, Mathematica automatically handles fraction as exact things, it doesn't evaluate the fractions to a float. It only does this when either the numerator or the denominator is not exact. I only showed integers above, but Mathematica can handle symbolic fraction in the same and complete way: <lang Mathematica>c/(2 c) (b^2 - c^2)/(b - c) // Cancel 1/2 + b/c // Together</lang> gives back: <lang Mathematica>1/2 b+c (2 b+c) / (2 c)</lang> Moreover it does simplification like Sin[x]/Cos[x] => Tan[x]. Division, addition, subtraction, powering and multiplication of a list (of any dimension) is automatically threaded over the elements: <lang Mathematica>1+2*{1,2,3}^3</lang> gives back: <lang Mathematica>{3, 17, 55}</lang> To check for perfect numbers in the range 1 to 2^25 we can use: <lang Mathematica>found={}; CheckPerfect[num_Integer]:=If[Total[1/Divisors[num]]==2,AppendTo[found,num]]; Do[CheckPerfect[i],{i,1,2^25}]; found</lang> gives back: <lang Mathematica>{6, 28, 496, 8128, 33550336}</lang> Final note; approximations of fractions to any precision can be found using the function N.

Objective-C

See Rational Arithmetic/Objective-C

OCaml

OCaml's Num library implements arbitrary-precision rational numbers:

<lang ocaml>#load "nums.cma";; open Num;;

for candidate = 2 to 1 lsl 19 do

 let sum = ref (num_of_int 1 // num_of_int candidate) in
 for factor = 2 to truncate (sqrt (float candidate)) do
   if candidate mod factor = 0 then
     sum := !sum +/ num_of_int 1 // num_of_int factor
                 +/ num_of_int 1 // num_of_int (candidate / factor)
 done;
 if is_integer_num !sum then
   Printf.printf "Sum of recipr. factors of %d = %d exactly %s\n%!"
       candidate (int_of_num !sum) (if int_of_num !sum = 1 then "perfect!" else "")

done;;</lang>

It might be implemented like this:

[insert implementation here]

Perl

Perl's Math::BigRat core module implements arbitrary-precision rational numbers. The bigrat pragma can be used to turn on transparent BigRat support:

<lang perl>use bigrat;

foreach my $candidate (2 .. 2**19) {

   my $sum = 1 / $candidate;
   foreach my $factor (2 .. sqrt($candidate)+1) {
       if ($candidate % $factor == 0) {
           $sum += 1 / $factor + 1 / ($candidate / $factor);
       }
   }
   if ($sum->denominator() == 1) {
       print "Sum of recipr. factors of $candidate = $sum exactly ", ($sum == 1 ? "perfect!" : ""), "\n";
   }

}</lang>

It might be implemented like this:

[insert implementation here]

Python

Works with: Python version 3.0

Python 3's standard library already implements a Fraction class:

<lang python>from fractions import Fraction

for candidate in range(2, 2**19):

 sum = Fraction(1, candidate)
 for factor in range(2, int(candidate**0.5)+1):
   if candidate % factor == 0:
     sum += Fraction(1, factor) + Fraction(1, candidate // factor)
 if sum.denominator == 1:
   print("Sum of recipr. factors of %d = %d exactly %s" %
          (candidate, int(sum), "perfect!" if sum == 1 else ""))</lang>

It might be implemented like this:

<lang python>def lcm(a, b):

   return a // gcd(a,b) * b

def gcd(u, v):

   return gcd(v, u%v) if v else abs(u)

class Fraction:

   def __init__(self, numerator, denominator):
       common = gcd(numerator, denominator)
       self.numerator = numerator//common
       self.denominator = denominator//common
   def __add__(self, frac):
       common = lcm(self.denominator, frac.denominator)
       n = common // self.denominator * self.numerator + common // frac.denominator * frac.numerator
       return Fraction(n, common)
   def __sub__(self, frac):
       return self.__add__(-frac)
   def __neg__(self):
       return Fraction(-self.numerator, self.denominator)
   def __abs__(self):
       return Fraction(abs(self.numerator), abs(self.denominator))
   def __mul__(self, frac):
       return Fraction(self.numerator * frac.numerator, self.denominator * frac.denominator)
   def __div__(self, frac):
       return self.__mul__(frac.reciprocal())
   def reciprocal(self):
       return Fraction(self.denominator, self.numerator)
   def __cmp__(self, n):
       return int(float(self) - float(n))
   def __float__(self):
       return float(self.numerator / self.denominator)
   def __int__(self):
       return (self.numerator // self.denominator)</lang>

Ruby

Ruby's standard library already implements a Rational class:

<lang ruby>require 'rational'

for candidate in 2 .. 2**19:

 sum = Rational(1, candidate)
 for factor in 2 ... candidate**0.5
   if candidate % factor == 0
     sum += Rational(1, factor) + Rational(1, candidate / factor)
   end
 end
 if sum.denominator == 1
   puts "Sum of recipr. factors of %d = %d exactly %s" %
          [candidate, sum.to_i, sum == 1 ? "perfect!" : ""]
 end

end</lang>

It might be implemented like this:

[insert implementation here]

Slate

Slate uses infinite-precision fractions transparently.

<lang slate>54 / 7. 20 reciprocal. (5 / 6) reciprocal. (5 / 6) as: Float.</lang>

Smalltalk

Smalltalk uses naturally and transparently fractions (through the class Fraction):

st> 54/7
54/7
st> 54/7 + 1
61/7
st> 54/7 < 50
true
st> 20 reciprocal
1/20
st> (5/6) reciprocal
6/5
st> (5/6) asFloat
0.8333333333333334

Works with: GNU Smalltalk

<lang smalltalk>| sum | 2 to: (2 raisedTo: 19) do: [ :candidate |

 sum := candidate reciprocal.
 2 to: (candidate sqrt) do: [ :factor |
    ( (candidate \\ factor) = 0 )
       ifTrue: [
          sum := sum + (factor reciprocal) + ((candidate / factor) reciprocal)
       ]
 ].
 ( (sum denominator) = 1 )
     ifTrue: [
          ('Sum of recipr. factors of %1 = %2 exactly %3' %
                    { candidate printString . 
                      (sum asInteger) printString . 
                      ( sum = 1 ) ifTrue: [ 'perfect!' ]
                                  ifFalse: [ ' ' ] }) displayNl
     ]

].</lang>

Tcl

See Rational Arithmetic/Tcl

TI-89 BASIC

While TI-89 BASIC has built-in rational and symbolic arithmetic, it does not have user-defined data types.