dsimcha wrote:
On 3/20/2011 10:26 PM, bearophile wrote:
dsimcha:
On second thought, given the difficulty finding anything else, rational
may be the thing that's most ready. I'll offer it up for review now
It's good to have rationals in Phobos, thank you.
Is this GCD? There is already a gcd in Phobos. Is this efficient when
numbers gets very large?
CommonInteger!(I1,I2) gcf(I1, I2)(I1 num1, I2 num2);
I knew someone was going to ask this, so I probably should have answered
it pre-emptively. std.numeric.gcd doesn't work with BigInts. I'm
considering making my implementation private and eventually fixing
std.numeric rather than having duplicate public functionality.
An alternative is to give the number of binary digits of precision for
the mantissa (see std.math.feqrel):
Rational!(Int) toRational(Int)(real floatNum, real epsilon = 1e-08);
That's worth considering. The only reason I did it the way I did is
because the Maxima computer algebra system did it this way and, when in
doubt, I generally do what Maxima does in this library. I also think
absolute error is the better metric for this case. If you do:
auto foo = toRational!BigInt(1e-200);
Do we really want to return some ridiculously huge number (that possibly
overflows in the case of fixed width integers) for the denominator in
this case?
The original plan for BigInt was to have a BigRational type. Suppose
that such a thing existed -- would it affect plans for this library?
I'm not sure that it is realistic to have a single templated type that
does both BigInt rationals, together with rationals based on built-in
integral types. The algorithms are different in a few respects:
(1) copying built-ins is practically zero cost;
(2) operations on BigInts depend on the size of the number (whereas for
builtins, all operations are O(1));
(3) BigInts cannot overflow.
In particular, gcd algorithms for arbitrary precision types are quite
different to gcd for built-ins.
I guess the primary question is:
If there were a BigRational type, would you still want rational?
Ie, are there use cases for rational over built-in types (rather than it
just being a workaround for a lack of a BigRational type)?
If the answer to this question is yes, then I suspect that the semantics
for rational over built-ins are so different to the semantics for
BigRational, that the two could be relatively independent.