[phobos] Rational for review

[Philippe Sigaud]

On Sat, Aug 28, 2010 at 20:38, David Simcha <dsimcha at gmail.com> wrote:

>
> > Let say from nom on, I prefix everything with rational.
> Don't worry about module issues.  As Lars pointed out, the library will not
> be named rational if/when it's integrated into Phobos.  It will be
> std.rational or be included in std.numerics
>

 Yes, you're right.




>
> auto r = rational(1,2);
> r = 1; // do not work.
>
> Maybe you could add opAssign from integer numbers?
>
>
> I fixed this right after I sent out the request for comment, because I
> realized that not allowing it was a bit silly.  Unfortunately, I
> accidentally sent a link that pointed to a specific revision.  Here's a new
> link that updates will be reflected in:
> http://dsource.org/projects/scrapple/browser/trunk/rational/rational.d
>
>
Good.

line 76: isAssignable would be a good addition to std.traits.


>
> Next, 1/0. OK, it's correctly dealt with (Integer Divide By Zero Error)
> But 0/1 botches. In fact, any rational that's zero creates a DBZ error. r-=
> r, etc.
> I guess it's a pb in simplify (454-455) or gcf (638), you should test for a
> zero numerator or divisor
>
>
> I can't believe I forgot to test this edge case.  Fixed by simply testing
> for zero as a special case in simplify().
>

Put in some very basic unit tests :-)  0+0==0, 1-1==0, that kind of thing :)





>
>
> Now, for the code itself:
> line 35: Maybe you should add %, %=, they are part of what I consider
> 'integer like'. You use them in gcf anyway
>
>
> Good point.  Done.  Also added comparison.
>

Man, integer-like is beginning to be quite big.

What about adding ++ and -- ?

Btw, I'm against putting ++ and -- in Rational, but please do add
opUnary!"+", opUnary!"-".



> As an aside, isIntegerLike, the equivalent isFloatingPointLike and
> defineOperators!( some string tuple) could be interesting additions to
> std.traits.
> I don't know what FP-like would be, maybe test for values between 0 and 1,
> and test for NaN.
>
>
> You may be right, but I'd rather wait until more user defined integer and
> floating point types are around to see exactly what such templates should
> require.
>

You're right. As of now, I see three traits:
isNumeric (ie, defines + - / * and is ordered: defines < > ==),
isIntegerLike(isNumeric, and % << >> <<< ++ --),
isFPLike(isNumeric, and (0.0+1.0)/2.0 is not zero)
As I'm no specialist of floating points, I'll let other decide.

So, there is also isOrdered or isComparable for opCmp and opEqual

Hmm, asking for NaN to be FP might not be a good idea: wasn't there some
plan to build a BigDecimal type at some point? I gather BigDecimal wouldn't
have NaN.
I tried to do one 2 years ago, built on BigInt+decimal point position. I
remember it to be awfully buggy :-)

I also tried to represent 'real' real numbers with a BigInt + an infinite
range (for the part after the .), but that was a mistake :)



>
> 75: if you make it public, you should add a template constraint
> if(isIntegral!I1 && isIntegral!i2). The same for gcf at line 640
>
>
> Good point.  Fixed.
>

I wasn't sure you wanted to make this public.



>   76: why * instead of +?
>
>
> No particular reason.  Any reasonable type should return the same type for
> either one.  I can't see why it would matter either way.
>

It shouldn't. That was just curiosity on my part. I'd have use an addition.



>
> 559: could toRational be a constructor? auto r = rational(PI, 1e-8);
>
>
>
> I'd rather leave it as a free function for a few reasons:
>
> 1.  In general the convention in Phobos is that non-trivial construction
> steps for structs are done in free functions.  Even though the reasons for
> that convention don't apply here, I'd rather follow it unless there's really
> a good reason to violate it.
>
> 2.  IIRC templated constructors are generally buggy, though I can't
> remember specifically how they're buggy.
>
> 3.  Lower case names are easier to type and read.
>
> 4.  It's what I already have written and I'm lazy. :-)
>
> I don't feel very strongly about this, though.  If you really feel strongly
> that it should be a constructor, though, and can explain why, then I'm
> willing to reconsider.
>
>
I meant a factory function, not a real constructor per se. See my example:
auto r = rational(PI, 1e-8);
It takes care of point 1, 2 and 3. As for 4, maybe just an alias would be
ok?

But I see in any case, the user has to provide the integer type she wants to
use, so my example is not OK.



 * a fractional part function (ie 22/7 is ~3.14 -> 0.14) as a FP
>
>
> Ditto.
>

Thinking about it some more, maybe the fractional part should return a
typeof(this): 22/7 -> 1/7. Not a float.


>
>  * Accordingly,  floor/ceil functions could be interesting, unless you
> think the user should use std.math.floor(cast(real)rat), which I could
> understand.
>
>
> Again, good idea.  Using std.math sucks because a major point of Rational
> is that it's supposed to work with arbitrary precision, and reals aren't
> arbitrary precision.
>


I could argue that floor or ceil are exactly when you get rid of this
arbitrary precision, but to answer the question in your next post, I think
these should be part of the rational module and be free functions: it makes
the module self-supported. And having rational support in std math means it
must in turn import the rational module. I'm against this.

In any case, people will probably import both at the same time...

I'm not clear on the subtle nuances between the integer part, the floor and
the ceil for positive and negative Rationals, though.

See std.math: ceil, floor, nearbyInt, round, trunc! Awww.

The next question would be: what other free function? I'll add abs(), but
not much more. Maybe pow or opBinary!"^^" ?
I wouldn't add any trigonometric function.
sqrt is on the fence for me. Is there an algorithm to calculate the square
root of a rational apart from the Babylonian method?


>
>   * Addendum (probably not a good idea): you can have infinity and
> NaN-like values with 1/0, -1/0 and 0/0...
>
>
> Probably not.  I really despise NaNs in floating point code because they
> break fundamental mathematical axioms that appear to be common sense (such
> as x == x, x * 0 == 0, if !(x <= y) then x > y, and x < y || x == y || x >
> y).  For example, try making a sorting algorithm or a binary tree with
> floating point numbers if they may be NaNs.  I'd rather just leave it the
> way it is, where it throws if the denominator is zero.
>

So it's ditched then.

We might at one point need an integer-like type adding negative and positive
infinity, if only to cleanly represent slices on infinite ranges.



>
> ***
>  2.  I couldn't figure out how to handle the case of user-defined
> fixed-width integer types in the decimal conversion (opCast) function, so it
> just assumes non-builtin integer types are arbitrary precision.  The biggest
> problem is lack of a way of introspecting whether the integer is fixed or
> arbitrary width and what its fixed width might be if it is, in fact, fixed.
>  The secondary problem is that I don't know of a good algorithm (though I'm
> sure I could find one if I tried) for converting fixed-width integers to
> floating point numbers in software.  Arbitrary precision is much easier.
> ***
>
> About converting fixed-width integer-like types, maybe these should provide
> .min and .max properties?
> That way you know the range of possible values and maybe it's then possible
> to convert (I didn't think this through so I may be completly mistaken)
>
>
> I think what I'm going to do here is just throw an exception iff the
> denominator has both the highest and lowest order bit set.  This is enough
> of a corner case in that it will only happen close to the limit of the
> largest denominator value that can be represented that I don't consider it a
> major limitation.  It's easily detectable because the numerator will never
> become bigger than the denominator by bit shifting iff either the numerator
> is zero or the denominator has its highest order bit set.  If the
> denominator's lowest order bit isn't set then I can shift the denominator
> right to make it not have its highest order bit set.
>

What's the pb with having a numerator bigger than the denominator? Sorry, I
didn't read the conversion function carefully.



>
> If anyone has any better ideas, or considers this too severe a limitation,
> let me know.
>

Do that and we'll see how it goes.



>
>
>
> Good work David. My only pb is that you write code faster that I can read
> it, and don't let me any time to write some myself! It took me a week to
> read the recent additions in Phobos!
>
>
> This code has been around in some form for almost a year.  It's just that
> the proposal for a units library made me remember that I've been meaning to
> clean up all the bit rot, improve it and submit it for inclusion.
>

Seeing that you have time, talent and energy, I'll order a BigDecimal module
:-)



>
>
>
> *goes back to cleaning his algebraic data types and type mimicry code*
>
>
> Great.  I look forward to when this code is ready.
>

No you don't :) It's full of string mixins, variadic templates, CT type
witchery, typetuples, objects hierarchies generated by CTFE and such. All in
all, it's a smorgasbord of D possibilities :)
But it's slowly coming together and the use is very easy.  I can already
imitate std.Tuple and std.Algebraic, make recursive types: lists and trees,
cyclic types (graphs?), imitate Haskell's Either and Maybe types, do
statically checked pattern matching on them, and create map/reduce
functions. So I'm not far from ADT in other languages that have them with
compiler support (Scala, Haskell, ML, F#...)
I still have to automate this last point (automatically generating a reduce
function on any recursive algebraic type), add variadic arguments (which
AFAICT no other language provide) and then code generalized algebraic
datatypes, the flagship of the most powerful functional languages: CAML and
Haskell :-)  Strangely, I see no difficulty *for now* in the last part.
In any case, even if I'm not sure this should be part of D standard library,
I'd be fun and good for PR to have them in a library somewhere.

As for type mimic it's nothing fancy but I'll try to post something soon, to
restart the discussion on typedef once more.

Philippe
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.puremagic.com/pipermail/phobos/attachments/20100828/6777b74d/attachment-0001.html>