std.rational?

[Joseph Rushton Wakeling]

On 01/10/13 10:35, ilya-stromberg wrote:
> It's from a mathematics:
> http://ru.wikipedia.org/wiki/%D0%94%D1%80%D0%BE%D0%B1%D1%8C_%28%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0%29
>
> Numerator must be integer (..., -2, -1, 0, 1, 2, ...):
> http://en.wikipedia.org/wiki/Integer
> Denumerator must be natural number (1, 2, 3, ...):
> http://en.wikipedia.org/wiki/Natural_number

I'm fully aware of the maths of it.  However, bear in mind that

   (i) m/(-n) is also a rational number, and that std.rational needs to support
       that case -- it's just that by convention in maths when we have m/(-n) we
       rewrite that as -m/n.

  (ii) enforcing that the denominator is an unsigned type doesn't actually make
       anything simpler internally because you still have to check that the
       denominator is > 0, and now you have to deal with the hassle of
       considering _two_ internal integer types with all the consequent issues
       of conversion, arithmetic etc.

> Note that english wikipedia says that denumerator is integer not equal to zero:
> http://en.wikipedia.org/wiki/Rational_number
> It's interesting: have we got 2 different mathematics, or it's just mistake in
> wikipedia? I didn't read any english mathematics books, but the GMP library
> agree with me:
> "All rational arithmetic functions assume operands have a canonical form, and
> canonicalize their result. The canonical from means that the denominator and the
> numerator have no common factors, and that the denominator is positive. Zero has
> the unique representation 0/1."
> http://gmplib.org/manual/Rational-Number-Functions.html#Rational-Number-Functions
>
> May be you are rigth and store numerator and denumerator type is too complex,
> but it have some benefits. For example, we can save some memory with BigUint
> type because it doesn't store unnecessary sign.

We don't have any mathematical disagreement, it's merely that using two 
different types for numerator and denominator leads to unnecessary complexity 
for no meaningful gain.

Re: BigInt -- how much memory do you think you're saving by eliminating 
signed-ness, compared to the typical anticipated size of a BigInt?  BigInt 
itself is just a BigUInt plus a bool :-)

> I don't know, I just found it in source code:
> https://github.com/D-Programming-Language/phobos/blob/master/std/bigint.d

It's because to implement a big integer you need to store 2 things:

    (i) the magnitude (absolute value) of the number, which is what BigUInt is
        there for;

   (ii) the sign of the number, which is just a boolean true/false == +/-.

Because the type has (theoretically) no limits to its range, there's no point in 
making public the "unsigned" type, because you don't gain anything by this.  For 
built-in integer types it matters because each unique value in the memory 
corresponds to a unique integer value, so you have constrained range and having 
an unsigned type doubles the upper range of the type.

Compare to floating-point numbers where again the signed-ness is a single bit 
and so there's no gain to having an unsigned floating-point type.