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 dyadic 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 monadic operators abs and '-', with the dyadic 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.
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);
# Monadic 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
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).
<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>
It might be implemented like this:
[insert implementation here]
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 *)stringValue; // 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 {
self = [super init];
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 *)stringValue {
[self simplify: [self autoSimplify]]; return [NSString stringWithFormat: @"%@%u/%u", [self isNegative] ? @"-" :
( [self withSign] ? @"+" : @"" ), [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]]]; }
// monadic 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 ) [self neg]; 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];
}
+(RCRationalNumber *)valueWithDouble: (double)fnum {
return [[RCRationalNumber alloc] initWithDouble: fnum];
}
+(RCRationalNumber *)valueWithInteger: (int)inum {
return [[RCRationalNumber alloc] initWithInteger: inum];
}
+(RCRationalNumber *)valueWithRational: (RCRationalNumber *)rnum {
return [[RCRationalNumber alloc] initWithRational: rnum];
} @end</lang>
Testing it. Note: this test shows limits and problems of the implementation; in particular I think I have a problem with GC matter here. The outmost loop was limited to 34000, since going beyond makes my harddisk swapping annoyingly...
<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 < 34000; 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>
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:
[insert implementation here]
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]