Arithmetic/Rational
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.
You are encouraged to solve this task according to the task description, using any language you may know.
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 219 by summing the reciprocal of the factors.
See also
Ada
The generic package specification: <lang ada> generic
type Number is range <>;
package Generic_Rational is
type Rational is private; function "abs" (A : Rational) return Rational; function "+" (A : Rational) return Rational; function "-" (A : Rational) return Rational; function Inverse (A : Rational) return Rational; function "+" (A : Rational; B : Rational) return Rational; function "+" (A : Rational; B : Number ) return Rational; function "+" (A : Number; B : Rational) return Rational;
function "-" (A : Rational; B : Rational) return Rational; function "-" (A : Rational; B : Number ) return Rational; function "-" (A : Number; B : Rational) return Rational;
function "*" (A : Rational; B : Rational) return Rational; function "*" (A : Rational; B : Number ) return Rational; function "*" (A : Number; B : Rational) return Rational;
function "/" (A : Rational; B : Rational) return Rational; function "/" (A : Rational; B : Number ) return Rational; function "/" (A : Number; B : Rational) return Rational; function "/" (A : Number; B : Number) return Rational; function ">" (A : Rational; B : Rational) return Boolean; function ">" (A : Number; B : Rational) return Boolean; function ">" (A : Rational; B : Number) return Boolean;
function "<" (A : Rational; B : Rational) return Boolean; function "<" (A : Number; B : Rational) return Boolean; function "<" (A : Rational; B : Number) return Boolean;
function ">=" (A : Rational; B : Rational) return Boolean; function ">=" (A : Number; B : Rational) return Boolean; function ">=" (A : Rational; B : Number) return Boolean;
function "<=" (A : Rational; B : Rational) return Boolean; function "<=" (A : Number; B : Rational) return Boolean; function "<=" (A : Rational; B : Number) return Boolean;
function "=" (A : Number; B : Rational) return Boolean; function "=" (A : Rational; B : Number) return Boolean;
function Numerator (A : Rational) return Number; function Denominator (A : Rational) return Number; Zero : constant Rational; One : constant Rational;
private
type Rational is record Numerator : Number; Denominator : Number; end record;
Zero : constant Rational := (0, 1); One : constant Rational := (1, 1);
end Generic_Rational; </lang> The package can be instantiated with any integer type. It provides rational numbers represented by a numerator and denominator cleaned from the common divisors. Mixed arithmetic of the base integer type and the rational type is supported. Division to zero raises Constraint_Error. The implementation of the specification above is as follows: <lang ada> package body Generic_Rational is
function GCD (A, B : Number) return Number 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 Inverse (A : Rational) return Rational is begin if A.Numerator > 0 then return (A.Denominator, A.Numerator); elsif A.Numerator < 0 then return (-A.Denominator, -A.Numerator); else raise Constraint_Error; end if; end Inverse;
function "abs" (A : Rational) return Rational is begin return (abs A.Numerator, A.Denominator); end "abs";
function "+" (A : Rational) return Rational is begin return A; end "+";
function "-" (A : Rational) return Rational is begin return (-A.Numerator, A.Denominator); end "-"; function "+" (A : Rational; B : Rational) return Rational is Common : constant Number := GCD (A.Denominator, B.Denominator); A_Denominator : constant Number := A.Denominator / Common; B_Denominator : constant Number := B.Denominator / Common; begin return (A.Numerator * B_Denominator + B.Numerator * A_Denominator) / (A_Denominator * B.Denominator); end "+";
function "+" (A : Rational; B : Number) return Rational is begin return (A.Numerator + B * A.Denominator) / A.Denominator; end "+";
function "+" (A : Number; B : Rational) return Rational is begin return B + A; end "+";
function "-" (A : Rational; B : Rational) return Rational is begin return A + (-B); end "-";
function "-" (A : Rational; B : Number) return Rational is begin return A + (-B); end "-";
function "-" (A : Number; B : Rational) return Rational is begin return A + (-B); end "-";
function "*" (A : Rational; B : Rational) return Rational is begin return (A.Numerator * B.Numerator) / (A.Denominator * B.Denominator); end "*";
function "*" (A : Rational; B : Number) return Rational is Common : constant Number := GCD (A.Denominator, abs B); begin return (A.Numerator * B / Common, A.Denominator / Common); end "*";
function "*" (A : Number; B : Rational) return Rational is begin return B * A; end "*";
function "/" (A : Rational; B : Rational) return Rational is begin return A * Inverse (B); end "/";
function "/" (A : Rational; B : Number) return Rational is Common : constant Number := GCD (abs A.Numerator, abs B); begin if B > 0 then return (A.Numerator / Common, A.Denominator * (B / Common)); else return ((-A.Numerator) / Common, A.Denominator * ((-B) / Common)); end if; end "/";
function "/" (A : Number; B : Rational) return Rational is begin return Inverse (B) * A; end "/";
function "/" (A : Number; B : Number) return Rational is Common : constant Number := GCD (abs A, abs B); begin if B = 0 then raise Constraint_Error; elsif A = 0 then return (0, 1); elsif A > 0 xor B > 0 then return (-(abs A / Common), abs B / Common); else return (abs A / Common, abs B / Common); end if; end "/"; function ">" (A, B : Rational) return Boolean is Diff : constant Rational := A - B; begin return Diff.Numerator > 0; end ">";
function ">" (A : Number; B : Rational) return Boolean is Diff : constant Rational := A - B; begin return Diff.Numerator > 0; end ">";
function ">" (A : Rational; B : Number) return Boolean is Diff : constant Rational := A - B; begin return Diff.Numerator > 0; end ">";
function "<" (A, B : Rational) return Boolean is Diff : constant Rational := A - B; begin return Diff.Numerator < 0; end "<";
function "<" (A : Number; B : Rational) return Boolean is Diff : constant Rational := A - B; begin return Diff.Numerator < 0; end "<"; function "<" (A : Rational; B : Number) return Boolean is Diff : constant Rational := A - B; begin return Diff.Numerator < 0; end "<";
function ">=" (A, B : Rational) return Boolean is Diff : constant Rational := A - B; begin return Diff.Numerator >= 0; end ">=";
function ">=" (A : Number; B : Rational) return Boolean is Diff : constant Rational := A - B; begin return Diff.Numerator >= 0; end ">=";
function ">=" (A : Rational; B : Number) return Boolean is Diff : constant Rational := A - B; begin return Diff.Numerator >= 0; end ">=";
function "<=" (A, B : Rational) return Boolean is Diff : constant Rational := A - B; begin return Diff.Numerator <= 0; end "<=";
function "<=" (A : Number; B : Rational) return Boolean is Diff : constant Rational := A - B; begin return Diff.Numerator <= 0; end "<=";
function "<=" (A : Rational; B : Number) return Boolean is Diff : constant Rational := A - B; begin return Diff.Numerator <= 0; end "<=";
function "=" (A : Number; B : Rational) return Boolean is Diff : constant Rational := A - B; begin return Diff.Numerator = 0; end "=";
function "=" (A : Rational; B : Number) return Boolean is Diff : constant Rational := A - B; begin return Diff.Numerator = 0; end "=";
function Numerator (A : Rational) return Number is begin return A.Numerator; end Numerator;
function Denominator (A : Rational) return Number is begin return A.Denominator; end Denominator;
end Generic_Rational; </lang> The implementation uses solution of the greatest common divisor task. Here is the implementation of the test: <lang ada> with Ada.Numerics.Elementary_Functions; use Ada.Numerics.Elementary_Functions; with Ada.Text_IO; use Ada.Text_IO; with Generic_Rational;
procedure Test_Rational is
package Integer_Rational is new Generic_Rational (Integer); use Integer_Rational;
begin
for Candidate in 2..2**15 loop declare Sum : Rational := 1 / Candidate; begin for Divisor in 2..Integer (Sqrt (Float (Candidate))) loop if Candidate mod Divisor = 0 then -- Factor is a divisor of Candidate Sum := Sum + One / Divisor + Rational'(Divisor / Candidate); end if; end loop; if Sum = 1 then Put_Line (Integer'Image (Candidate) & " is perfect"); end if; end; end loop;
end Test_Rational; </lang> The perfect numbers are searched by summing of the reciprocal of each of the divisors of a candidate except 1. This sum must be 1 for a perfect number. Sample output:
6 is perfect 28 is perfect 496 is perfect 8128 is perfect
ALGOL 68
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
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.
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
File frac.h
<lang objc>#import <Foundation/Foundation.h>
@interface RCRationalNumber : NSObject {
@private int numerator; int denominator; BOOL autoSimplify; BOOL withSign;
} +(RCRationalNumber *)valueWithNumerator:(int)num andDenominator: (int)den; +(RCRationalNumber *)valueWithDouble: (double)fnum; +(RCRationalNumber *)valueWithInteger: (int)inum; +(RCRationalNumber *)valueWithRational: (RCRationalNumber *)rnum; -(id)init; -(id)initWithNumerator: (int)num andDenominator: (int)den; -(id)initWithDouble: (double)fnum precision: (int)prec; -(id)initWithInteger: (int)inum; -(id)initWithRational: (RCRationalNumber *)rnum; -(NSComparisonResult)compare: (RCRationalNumber *)rnum; -(id)simplify: (BOOL)act; -(void)setAutoSimplify: (BOOL)v; -(void)setWithSign: (BOOL)v; -(BOOL)autoSimplify; -(BOOL)withSign; -(NSString *)description; // ops -(id)multiply: (RCRationalNumber *)rnum; -(id)divide: (RCRationalNumber *)rnum; -(id)add: (RCRationalNumber *)rnum; -(id)sub: (RCRationalNumber *)rnum; -(id)abs; -(id)neg; -(id)mod: (RCRationalNumber *)rnum; -(int)sign; -(BOOL)isNegative; -(id)reciprocal; // getter -(int)numerator; -(int)denominator; //setter -(void)setNumerator: (int)num; -(void)setDenominator: (int)num; // defraction -(double)number; -(int)integer; @end</lang>
File frac.m
<lang objc>#import <Foundation/Foundation.h>
- import <math.h>
- import "frac.h"
// gcd: Greatest common divisor#Recursive_Euclid_algorithm // if built in as "private" function, add static.
static int lcm(int a, int b) {
return a / gcd(a,b) * b;
}
@implementation RCRationalNumber // initializers -(id)init {
NSLog(@"initialized to unity"); return [self initWithInteger: 1];
}
-(id)initWithNumerator: (int)num andDenominator: (int)den {
if ((self = [super init]) != nil) { if (den == 0) { NSLog(@"denominator is zero"); return nil; } [self setNumerator: num]; [self setDenominator: den]; [self setWithSign: YES]; [self setAutoSimplify: YES]; [self simplify: YES]; } return self;
}
-(id)initWithInteger:(int)inum {
return [self initWithNumerator: inum andDenominator: 1];
}
-(id)initWithDouble: (double)fnum precision: (int)prec {
if ( prec > 9 ) prec = 9; double p = pow(10.0, (double)prec); int nd = (int)(fnum * p); return [self initWithNumerator: nd andDenominator: (int)p ];
}
-(id)initWithRational: (RCRationalNumber *)rnum {
return [self initWithNumerator: [rnum numerator] andDenominator: [rnum denominator]];
}
// comparing -(NSComparisonResult)compare: (RCRationalNumber *)rnum {
if ( [self number] > [rnum number] ) return NSOrderedDescending; if ( [self number] < [rnum number] ) return NSOrderedAscending; return NSOrderedSame;
}
// string rapresentation of the Q -(NSString *)description {
[self simplify: [self autoSimplify]]; return [NSString stringWithFormat: @"%@%d/%d", [self isNegative] ? @"-" :
( [self withSign] ? @"+" : @"" ), abs([self numerator]), [self denominator]]; }
// setter options -(void)setAutoSimplify: (BOOL)v {
autoSimplify = v; [self simplify: v];
} -(void)setWithSign: (BOOL)v {
withSign = v;
}
// getter for options -(BOOL)autoSimplify {
return autoSimplify;
}
-(BOOL)withSign {
return withSign;
}
// "simplify" the fraction ... -(id)simplify: (BOOL)act {
if ( act ) { int common = gcd([self numerator], [self denominator]); [self setNumerator: [self numerator]/common]; [self setDenominator: [self denominator]/common]; } return self;
}
// diadic operators -(id)multiply: (RCRationalNumber *)rnum {
int newnum = [self numerator] * [rnum numerator]; int newden = [self denominator] * [rnum denominator]; return [RCRationalNumber valueWithNumerator: newnum
andDenominator: newden]; }
-(id)divide: (RCRationalNumber *)rnum {
return [self multiply: [rnum reciprocal]];
}
-(id)add: (RCRationalNumber *)rnum {
int common = lcm([self denominator], [rnum denominator]); int resnum = common / [self denominator] * [self numerator] + common / [rnum denominator] * [rnum numerator]; return [RCRationalNumber valueWithNumerator: resnum andDenominator: common];
}
-(id)sub: (RCRationalNumber *)rnum {
return [self add: [rnum neg]];
}
-(id)mod: (RCRationalNumber *)rnum {
return [[self divide: rnum]
sub: [RCRationalNumber valueWithInteger: [[self divide: rnum] integer]]]; }
// unary operators -(id)neg {
return [RCRationalNumber valueWithNumerator: -1*[self numerator]
andDenominator: [self denominator]]; }
-(id)abs {
return [RCRationalNumber valueWithNumerator: abs([self numerator])
andDenominator: [self denominator]]; }
-(id)reciprocal {
return [RCRationalNumber valueWithNumerator: [self denominator]
andDenominator: [self numerator]]; }
// get the sign -(int)sign {
return ([self numerator] < 0) ? -1 : 1;
}
// or just test if negativ -(BOOL)isNegative {
return ([self numerator] < 0) ? YES : NO;
}
// Q as real floating point -(double)number {
return (double)[self numerator] / (double)[self denominator];
}
// Q as (truncated) integer -(int)integer {
return [self numerator] / [self denominator];
}
// set num and den indipendently, fixing sign accordingly -(void)setNumerator: (int)num {
numerator = num;
}
-(void)setDenominator: (int)num {
if ( num < 0 ) numerator = -numerator; denominator = abs(num);
}
// getter -(int)numerator {
return numerator;
}
-(int)denominator {
return denominator;
}
// class method +(RCRationalNumber *)valueWithNumerator:(int)num andDenominator: (int)den {
return [[[RCRationalNumber alloc] initWithNumerator: num andDenominator: den] autorelease];
}
+(RCRationalNumber *)valueWithDouble: (double)fnum {
return [[[RCRationalNumber alloc] initWithDouble: fnum] autorelease];
}
+(RCRationalNumber *)valueWithInteger: (int)inum {
return [[[RCRationalNumber alloc] initWithInteger: inum] autorelease];
}
+(RCRationalNumber *)valueWithRational: (RCRationalNumber *)rnum {
return [[[RCRationalNumber alloc] initWithRational: rnum] autorelease];
} @end</lang>
Testing it.
<lang objc>#import <Foundation/Foundation.h>
- import "frac.h"
- import <math.h>
int main() {
NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init];
int i; for(i=2; i < 0x80000; i++) { int candidate = i; RCRationalNumber *sum = [RCRationalNumber valueWithNumerator: 1 andDenominator: candidate]; int factor; for(factor=2; factor < sqrt((double)candidate); factor++) { if ( (candidate % factor) == 0 ) { sum = [[sum add: [RCRationalNumber valueWithNumerator: 1
andDenominator: factor]] add: [RCRationalNumber valueWithNumerator: 1 andDenominator: (candidate/factor)]];
} } if ( [sum denominator] == 1 ) { printf("Sum of recipr. factors of %d = %d exactly %s\n",
candidate, [sum integer], ([sum integer]==1) ? "perfect!" : "");
} }
[pool release]; return 0;
}</lang>
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
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
<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
code to find factors of a number not shown <lang tcl>namespace eval rat {}
proc rat::new {args} {
if {[llength $args] == 0} { set args {0} } lassign [split {*}$args] n d if {$d == 0} { error "divide by zero" } if {$d < 0} { set n [expr {-1 * $n}] set d [expr {abs($d)}] } return [normalize $n $d]
}
proc rat::split {args} {
if {[llength $args] == 1} { lassign [::split $args /] n d if {$d eq ""} { set d 1 } } else { lassign $args n d } return [list $n $d]
}
proc rat::join {rat} {
lassign $rat n d if {$n == 0} { return 0 } elseif {$d == 1} { return $n } else { return $n/$d }
}
proc rat::normalize {n d} {
set gcd [gcd $n $d] return [join [list [expr {$n/$gcd}] [expr {$d/$gcd}]]]
}
proc rat::gcd {a b} {
while {$b != 0} { lassign [list $b [expr {$a % $b}]] a b } return $a
}
proc rat::abs {rat} {
lassign [split $rat] n d return [join [list [expr {abs($n)}] $d]]
}
proc rat::inv {rat} {
lassign [split $rat] n d return [normalize $d $n]
}
proc rat::+ {args} {
set n 0 set d 1 foreach arg $args { lassign [split $arg] an ad set n [expr {$n*$ad + $an*$d}] set d [expr {$d * $ad}] } return [normalize $n $d]
}
proc rat::- {args} {
lassign [split [lindex $args 0]] n d if {[llength $args] == 1} { return [join [list [expr {-1 * $n}] $d]] } foreach arg [lrange $args 1 end] { lassign [split $arg] an ad set n [expr {$n*$ad - $an*$d}] set d [expr {$d * $ad}] } return [normalize $n $d]
}
proc rat::* {args} {
set n 1 set d 1 foreach arg $args { lassign [split $arg] an ad set n [expr {$n * $an}] set d [expr {$d * $ad}] } return [normalize $n $d]
}
proc rat::/ {a b} {
set r [* $a [inv $b]] if {[string match */0 $r]} { error "divide by zero" } return $r
}
proc rat::== {a b} {
return [expr {[- $a $b] == 0}]
}
proc rat::!= {a b} {
return [expr { ! [== $a $b]}]
}
proc rat::< {a b} {
lassign [split [- $a $b]] n d return [expr {$n < 0}]
}
proc rat::> {a b} {
lassign [split [- $a $b]] n d return [expr {$n > 0}]
}
proc rat::<= {a b} {
return [expr { ! [> $a $b]}]
}
proc rat::>= {a b} {
return [expr { ! [< $a $b]}]
}
proc is_perfect {num} {
set sum [rat::new 0] foreach factor [all_factors $num] { set sum [rat::+ $sum [rat::new 1/$factor]] } # note, all_factors includes 1, so sum should be 2 return [rat::== $sum 2]
}
proc get_perfect_numbers {} {
set t [clock seconds] set limit [expr 2**19] for {set num 2} {$num < $limit} {incr num} { if {[is_perfect $num]} { puts "perfect: $num" } } puts "elapsed: [expr {[clock seconds] - $t}] seconds"
set num [expr {2**12 * (2**13 - 1)}] ;# 5th perfect number if {[is_perfect $num]} { puts "perfect: $num" }
}
source primes.tcl get_perfect_numbers</lang>
perfect: 6 perfect: 28 perfect: 496 perfect: 8128 elapsed: 477 seconds perfect: 33550336