Arithmetic/Rational: Difference between revisions
m (→[[Rational Arithmetic#ALGOL 68]]: shorten code sample) |
(obj-c (pre 0.1...)) |
||
Line 167: | Line 167: | ||
Sum of reciprocal factors of 523776 = 2 exactly, about 2.0000000000000000000000000005 |
Sum of reciprocal factors of 523776 = 2 exactly, about 2.0000000000000000000000000005 |
||
</pre> |
</pre> |
||
=={{header|Objective-C}}== |
|||
File <tt>frac.h</tt> |
|||
<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 <tt>frac.m</tt> |
|||
<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 alloc] |
|||
initWithNumerator: 1 |
|||
andDenominator: candidate]; |
|||
int factor; |
|||
for(factor=2; factor < sqrt((double)candidate); factor++) { |
|||
if ( (candidate % factor) == 0 ) { |
|||
RCRationalNumber *tsum = [[sum add: [RCRationalNumber valueWithNumerator: 1 |
|||
andDenominator: factor]] |
|||
add: [RCRationalNumber valueWithNumerator: 1 |
|||
andDenominator: (candidate/factor)]]; |
|||
[sum release]; |
|||
sum = [RCRationalNumber valueWithRational: tsum]; |
|||
[tsum release]; // [pool drain]; |
|||
} |
|||
} |
|||
if ( [sum denominator] == 1 ) { |
|||
printf("Sum of recipr. factors of %d = %d exactly %s\n", |
|||
candidate, [sum integer], ([sum integer]==1) ? "perfect!" : ""); |
|||
} |
|||
[sum release]; |
|||
} |
|||
[pool release]; |
|||
return 0; |
|||
}</lang> |
Revision as of 21:32, 14 February 2009
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 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
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 alloc] initWithNumerator: 1 andDenominator: candidate]; int factor; for(factor=2; factor < sqrt((double)candidate); factor++) { if ( (candidate % factor) == 0 ) { RCRationalNumber *tsum = [[sum add: [RCRationalNumber valueWithNumerator: 1
andDenominator: factor]] add: [RCRationalNumber valueWithNumerator: 1 andDenominator: (candidate/factor)]]; [sum release]; sum = [RCRationalNumber valueWithRational: tsum]; [tsum release]; // [pool drain];
} } if ( [sum denominator] == 1 ) { printf("Sum of recipr. factors of %d = %d exactly %s\n",
candidate, [sum integer], ([sum integer]==1) ? "perfect!" : "");
} [sum release]; }
[pool release]; return 0;
}</lang>