Arithmetic/Rational: Difference between revisions

Content added Content deleted
(Updated D entry)
(Improved and updated D entry)
Line 368: Line 368:


=={{header|D}}==
=={{header|D}}==
⚫
<lang d>import std.bigint, std.traits, std.conv;
Rational implementation based on BigInt. Currently this is not fast.
⚫
<lang d>import std.bigint, std.traits;


T gcd(T)(/*in*/ T a, /*in*/ T b) /*pure nothrow*/ {
T gcd(T)(/*in*/ T a, /*in*/ T b) /*pure nothrow*/ {
// std.numeric.gcd doesn't work with BigInt
// std.numeric.gcd doesn't work with BigInt.
return (b != 0) ? gcd(b, a % b) : (a < 0) ? -a : a;
return (b != 0) ? gcd(b, a % b) : (a < 0) ? -a : a;
}
}
Line 380: Line 379:
}
}


⚫
struct RationalT(T) {
BigInt toBig(T : BigInt)(/*const*/ ref T n) pure nothrow { return n; }
⚫
/*const*/ private T num, den; // Numerator & denominator.

⚫
BigInt toBig(T)(in ref T n) pure nothrow if (isIntegral!T) {
⚫
return BigInt(n);
}

⚫
struct Rational {
⚫
/*const*/ private BigInt num, den; // numerator & denominator


private enum Type { NegINF = -2,
private enum Type { NegINF = -2,
Line 395: Line 388:
PosINF = 2 };
PosINF = 2 };


this(U : Rational)(U n) pure nothrow {
this(U : RationalT)(U n) pure nothrow {
num = n.num;
num = n.num;
den = n.den;
den = n.den;
Line 401: Line 394:


this(U)(in U n) pure nothrow if (isIntegral!U) {
this(U)(in U n) pure nothrow if (isIntegral!U) {
num = toBig(n);
num = toT(n);
den = 1UL;
den = 1UL;
}
}


this(U, V)(/*in*/ U n, /*in*/ V d) /*pure nothrow*/ {
this(U, V)(/*in*/ U n, /*in*/ V d) /*pure nothrow*/ {
num = toBig(n);
num = toT(n);
den = toBig(d);
den = toT(d);
/*const*/ BigInt common = gcd(num, den);
/*const*/ T common = gcd(num, den);
if (common != 0) {
if (common != 0) {
num /= common;
num /= common;
Line 416: Line 409:
den = 0;
den = 0;
}
}
if (den < 0) { // assure den is non-negative
if (den < 0) { // Assure den is non-negative.
num = -num;
num = -num;
den = -den;
den = -den;
Line 422: Line 415:
}
}


BigInt nomerator() /*const*/ pure nothrow @property {
static T toT(U)(/*in*/ ref U n) pure nothrow if (is(U == T)) {
⚫
return n;
}

⚫
static T toT(U)(in ref U n) pure nothrow if (!is(U == T)) {
T result = n;
return result;
}

T nomerator() /*const*/ pure nothrow @property {
return num;
return num;
}
}


BigInt denominator() /*const*/ pure nothrow @property {
T denominator() /*const*/ pure nothrow @property {
return den;
return den;
}
}
Line 437: Line 439:
return ((num < 0) ? "-" : "+") ~ "infRat";
return ((num < 0) ? "-" : "+") ~ "infRat";
}
}
return toDecimalString(num) ~
return text(num) ~ (den == 1 ? "" : ("/" ~ text(den)));
(den == 1 ? "" : ("/" ~ toDecimalString(den)));
}
}


Rational opBinary(string op)(/*in*/ Rational r)
RationalT opBinary(string op)(/*in*/ RationalT r)
/*const pure nothrow*/ if (op == "+" || op == "-") {
/*const pure nothrow*/ if (op == "+" || op == "-") {
BigInt common = lcm(den, r.den);
T common = lcm(den, r.den);
BigInt n = mixin("common / den * num" ~ op ~
T n = mixin("common / den * num" ~ op ~
"common / r.den * r.num" );
"common / r.den * r.num" );
return Rational(n, common);
return RationalT(n, common);
}
}


Rational opBinary(string op)(/*in*/ Rational r)
RationalT opBinary(string op)(/*in*/ RationalT r)
/*const pure nothrow*/ if (op == "*") {
/*const pure nothrow*/ if (op == "*") {
return Rational(num * r.num, den * r.den);
return RationalT(num * r.num, den * r.den);
}
}


Rational opBinary(string op)(/*in*/ Rational r)
RationalT opBinary(string op)(/*in*/ RationalT r)
/*const pure nothrow*/ if (op == "/") {
/*const pure nothrow*/ if (op == "/") {
return Rational(num * r.den, den * r.num);
return RationalT(num * r.den, den * r.num);
}
}


Rational opBinary(string op, T)(in T r)
RationalT opBinary(string op, U)(in U r)
/*const pure nothrow*/ if (isIntegral!T && (op == "+" ||
/*const pure nothrow*/ if (isIntegral!U && (op == "+" ||
op == "-" || op == "*" || op == "/")) {
op == "-" || op == "*" || op == "/")) {
return opBinary!op(Rational(r));
return opBinary!op(RationalT(r));
}
}


Rational opBinary(string op)(in size_t p)
RationalT opBinary(string op)(in size_t p)
/*const pure nothrow*/ if (op == "^^") {
/*const pure nothrow*/ if (op == "^^") {
return Rational(num ^^ p, den ^^ p);
return RationalT(num ^^ p, den ^^ p);
}
}


Rational opBinaryRight(string op, T)(in T l)
RationalT opBinaryRight(string op, U)(in U l)
/*const pure nothrow*/ if (isIntegral!T) {
/*const pure nothrow*/ if (isIntegral!U) {
return Rational(l).opBinary!op(Rational(num, den));
return RationalT(l).opBinary!op(RationalT(num, den));
}
}


Rational opUnary(string op)()
RationalT opOpAssign(string op, U)(in U l)
/*const pure nothrow*/ {
mixin("this = this " ~ op ~ "l;");
return this;
}

RationalT opUnary(string op)()
/*const pure nothrow*/ if (op == "+" || op == "-") {
/*const pure nothrow*/ if (op == "+" || op == "-") {
return Rational(mixin(op ~ "num"), den);
return RationalT(mixin(op ~ "num"), den);
}
}


bool opCast(T)() const if (is(T == bool)) {
bool opCast(U)() const if (is(U == bool)) {
return num != 0;
return num != 0;
}
}


int opEquals(T)(/*in*/ T r) /*const pure nothrow*/ {
int opEquals(U)(/*in*/ U r) /*const pure nothrow*/ {
Rational rhs = Rational(r);
RationalT rhs = RationalT(r);
if (type() == Type.NaRAT || rhs.type() == Type.NaRAT)
if (type() == Type.NaRAT || rhs.type() == Type.NaRAT)
return false;
return false;
Line 491: Line 498:
}
}


int opCmp(T)(/*in*/ T r) /*const pure nothrow*/ {
int opCmp(U)(/*in*/ U r) /*const pure nothrow*/ {
auto rhs = Rational(r);
auto rhs = RationalT(r);
if (type() == Type.NaRAT || rhs.type() == Type.NaRAT)
if (type() == Type.NaRAT || rhs.type() == Type.NaRAT)
throw new Exception("Compare invlove an NaRAT.");
throw new Exception("Compare involve a NaRAT.");
if (type() != Type.NORMAL ||
if (type() != Type.NORMAL ||
rhs.type() != Type.NORMAL) // for infinite
rhs.type() != Type.NORMAL) // for infinite
return (type() == rhs.type()) ? 0 :
return (type() == rhs.type()) ? 0 :
((type() < rhs.type()) ? -1 : 1);
((type() < rhs.type()) ? -1 : 1);
BigInt diff = num * rhs.den - den * rhs.num;
U diff = num * rhs.den - den * rhs.num;
return (diff == 0) ? 0 : ((diff < 0) ? -1 : 1);
return (diff == 0) ? 0 : ((diff < 0) ? -1 : 1);
}
}
Line 512: Line 519:
}
}


alias Rational = RationalT!BigInt;
⚫
version (arithmetic_rational_main) { // test part
⚫
void main() {
⚫
import std.stdio, std.math;


⚫
version (arithmetic_rational_main) { // Test.
⚫
foreach (p; 2 .. 2 ^^ 19) {
⚫
void main() {
auto sum = Rational(1, p);
⚫
import std.stdio, std.math;
immutable limit = 1 + cast(uint)sqrt(cast(real)p);
foreach (factor; 2 .. limit)
alias RatL = RationalT!long;

⚫
if (p % factor == 0)
⚫
foreach (immutable p; 2 .. 2 ^^ 19) {
⚫
sum = sum + Rational(1, factor) + Rational(factor, p);
if (sum.denominator == 1)
auto sum = RatL(1, p);
writefln("Sum of recipr. factors of %6s = %s exactly%s",
immutable limit = 1 + cast(uint)sqrt(cast(real)p);
p, sum, (sum == 1) ? ", perfect." : ".");
foreach (immutable factor; 2 .. limit)
⚫
if (p % factor == 0)
⚫
sum += RatL(1, factor) + RatL(factor, p);
if (sum.denominator == 1)
⚫
writefln("Sum of recipr. factors of %6s = %s exactly%s",
p, sum, (sum == 1) ? ", perfect." : ".");
}
}
}
}
}</lang>
}</lang>
Use the <code>-version=rational_arithmetic_main</code> compiler switch to run the test code.
Use the <code>-version=rational_arithmetic_main</code> compiler switch to run the test code.
{{out}}
{{out}}
<pre>Sum of recipr. factors of 6 = 1 exactly, perfect.
Sum of recipr. factors of 28 = 1 exactly, perfect.
⚫
Sum of recipr. factors of 120 = 2 exactly.
Sum of recipr. factors of 496 = 1 exactly, perfect.
Sum of recipr. factors of 672 = 2 exactly.
Sum of recipr. factors of 8128 = 1 exactly, perfect.
Sum of recipr. factors of 30240 = 3 exactly.
Sum of recipr. factors of 32760 = 3 exactly.</pre>
Run-time is about 9.5 seconds. It's quite slow because in DMD v.2.060 BigInts have no memory optimizations.

Output using p up to 2^^19, as requested by the task:
<pre>Sum of recipr. factors of 6 = 1 exactly, perfect.
<pre>Sum of recipr. factors of 6 = 1 exactly, perfect.
Sum of recipr. factors of 28 = 1 exactly, perfect.
Sum of recipr. factors of 28 = 1 exactly, perfect.
Line 550: Line 549:
Sum of recipr. factors of 32760 = 3 exactly.
Sum of recipr. factors of 32760 = 3 exactly.
Sum of recipr. factors of 523776 = 2 exactly.</pre>
Sum of recipr. factors of 523776 = 2 exactly.</pre>
Currently RationalT!BigInt is not fast.


=={{header|Elisa}}==
=={{header|Elisa}}==
Retrieved from "https://rosettacode.org/wiki/Arithmetic/Rational"