www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Rational numbers in D

reply Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:
Sorry for the double-post -- I already asked this in d-learn, but this may be a 
better place to ask.

What's the current state of affairs and roadmap for inclusion of rational
number 
support in D?  I've come across David Simcha's work:
http://cis.jhu.edu/~dsimcha/d/phobos/std_rational.html

... and a feature request on the bugzilla:
http://d.puremagic.com/issues/show_bug.cgi?id=7885

... but this isn't mentioned at all in the review queue:
http://prowiki.org/wiki4d/wiki.cgi?ReviewQueue

What's the status of work/planning for this feature and is there any kind of
ETA 
for when it might land in Phobos?

Thanks and best wishes,

     -- Joe
Jun 07 2012
next sibling parent reply "Paul D. Anderson" <paul.d.removethis.anderson comcast.andthis.net> writes:
On Thursday, 7 June 2012 at 17:49:22 UTC, Joseph Rushton Wakeling 
wrote:

 Sorry for the double-post -- I already asked this in d-learn, 
 but this may be a better place to ask.

 What's the current state of affairs and roadmap for inclusion 
 of rational number support in D?  I've come across David 
 Simcha's work:
 http://cis.jhu.edu/~dsimcha/d/phobos/std_rational.html

 ... and a feature request on the bugzilla:
 http://d.puremagic.com/issues/show_bug.cgi?id=7885

 ... but this isn't mentioned at all in the review queue:
 http://prowiki.org/wiki4d/wiki.cgi?ReviewQueue

 What's the status of work/planning for this feature and is 
 there any kind of ETA for when it might land in Phobos?

 Thanks and best wishes,

     -- Joe


I don't think anyone intends to ignore your posts, it's just that 
we don't have the answer. Jonathan Davis has a new thread 
regarding the review queue. You might get answers there.

I think there is a tendency for discussions in this group to 
focus on language internals and features rather than useful but 
mundane things. As a last resort you could probably check and/or 
complete the rational number code and put it in the review queue 
yourself. Most code here is licensed to allow that.

Taking a little longer view, we definitely need a better process 
for inclusion of new modules into phobos. Maybe, as you suggest, 
a roadmap for proposed modules, with dates for implementation and 
reviews.

Paul
Jun 08 2012
parent Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:
On 08/06/12 18:06, Paul D. Anderson wrote:

 I don't think anyone intends to ignore your posts, it's just that we don't have
 the answer. Jonathan Davis has a new thread regarding the review queue. You
 might get answers there.


It wasn't really that I was feeling ignored (OK, put this as a tribute to the 
speed at which questions are usually answered:-), more that I thought the 
discussion might be more useful/suited here as it's about a module under 
development.  Again, sorry for the double post.


 I think there is a tendency for discussions in this group to focus on language
 internals and features rather than useful but mundane things. As a last resort
 you could probably check and/or complete the rational number code and put it in
 the review queue yourself. Most code here is licensed to allow that.


I'll take a look and see what I can do.


 Taking a little longer view, we definitely need a better process for inclusion
 of new modules into phobos. Maybe, as you suggest, a roadmap for proposed
 modules, with dates for implementation and reviews.


I guess it's tricky because there are only a limited number of people who can 
review the code, so it must be difficult to set definite time targets.  But it 
could be nice to have e.g. a priority wish list so that we can see what kinds
of 
contributions would be most useful/welcome.
Jun 08 2012
prev sibling next sibling parent reply Stewart Gordon <smjg_1998 yahoo.com> writes:
On 07/06/2012 18:49, Joseph Rushton Wakeling wrote:

 Sorry for the double-post -- I already asked this in d-learn, but this may be
a better
 place to ask.

 What's the current state of affairs and roadmap for inclusion of rational
number support
 in D?


Including it in D seems very unlikely.

Including it in Phobos, OTOH, is another matter.


 I've come across David Simcha's work:
 http://cis.jhu.edu/~dsimcha/d/phobos/std_rational.html

 ... and a feature request on the bugzilla:
 http://d.puremagic.com/issues/show_bug.cgi?id=7885


<snip>

Well, do these work at the moment?

If so, I suggest you use one of them for now.  If you're mainly just doing
simple 
arithmetic with them, it probably wouldn't be too much work to convert your
code to use 
the Phobos rational type when/if it gets one.

Stewart.
Jun 08 2012
parent reply "SomeDude" <lovelydear mailmetrash.com> writes:
On Saturday, 9 June 2012 at 01:11:49 UTC, Stewart Gordon wrote:

 On 07/06/2012 18:49, Joseph Rushton Wakeling wrote:

 Sorry for the double-post -- I already asked this in d-learn, 
 but this may be a better
 place to ask.

 What's the current state of affairs and roadmap for inclusion 
 of rational number support
 in D?


 Including it in D seems very unlikely.

 Including it in Phobos, OTOH, is another matter.


 I've come across David Simcha's work:
 http://cis.jhu.edu/~dsimcha/d/phobos/std_rational.html

 ... and a feature request on the bugzilla:
 http://d.puremagic.com/issues/show_bug.cgi?id=7885


 <snip>

 Well, do these work at the moment?

 If so, I suggest you use one of them for now.  If you're mainly 
 just doing simple arithmetic with them, it probably wouldn't be 
 too much work to convert your code to use the Phobos rational 
 type when/if it gets one.

 Stewart.


I've never had any use for rational numbers as have 99% of 
developers I believe. Maybe I'm overlooking something, but I see 
only two possible usages of them: math packages and length 
quotations in the english system. Because of this, I'd rather see 
them in Deimos than in Phobos.
Jun 09 2012
next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
SomeDude:


 I've never had any use for rational numbers as have 99% of 
 developers I believe. Maybe I'm overlooking something, but I 
 see only two possible usages of them: math packages and length 
 quotations in the english system. Because of this, I'd rather 
 see them in Deimos than in Phobos.


I have had to use Rational nunbers in D two or three times (once 
during simplification of expressions that contain operations 
among integer numbers, to not lose exact precision with floating 
point numbers). I have written a rationals module for D1 and 
later I have converted it to D2. So you see two persons that have 
implemented them.

It's a small module, that uses std.bigint, it's not a binding to 
C code, so putting it in Deimos is not necessary. I'd like a 
rationals module in Phobos.

Bye,
bearophile
Jun 09 2012
parent reply Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:
On 09/06/12 16:08, bearophile wrote:

 I have had to use Rational nunbers in D two or three times (once during
 simplification of expressions that contain operations among integer numbers, to
 not lose exact precision with floating point numbers). I have written a
 rationals module for D1 and later I have converted it to D2. So you see two
 persons that have implemented them.

 It's a small module, that uses std.bigint, it's not a binding to C code, so
 putting it in Deimos is not necessary. I'd like a rationals module in Phobos.


... so, I can lend my voice to support inclusion of your module :-)  Is there 
anything more practical that I could do to assist?
Jun 09 2012
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Joseph Rushton Wakeling:


 ... so, I can lend my voice to support inclusion of your module 
 :-)


It's not fit for Phobos...

Bye,
bearophile
Jun 11 2012
parent Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:
On 11/06/12 22:43, bearophile wrote:

 It's not fit for Phobos...


What would make it fit?
Jun 12 2012
prev sibling parent reply Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:
On Saturday, 9 June 2012 at 01:11:49 UTC, Stewart Gordon wrote:

 Including it in D seems very unlikely.

 Including it in Phobos, OTOH, is another matter.


My bad phrasing.  Of course in Phobos.


On 09/06/12 08:25, SomeDude wrote:

 I've never had any use for rational numbers as have 99% of developers I
believe.
 Maybe I'm overlooking something, but I see only two possible usages of them:
 math packages and length quotations in the english system. Because of this, I'd
 rather see them in Deimos than in Phobos.


In fact the application I had in mind was for music software, where you want to 
be able to store pitch changes in fractions of a whole tone.  In that context 
it's important that adding up those changes be guaranteed to produce exact
results.

e.g. if you take middle C and raise it by 1 whole tone _exactly_ you arrive at 
the note D.  If you raise it by 0.99999999999999999999999999995 instead, how 
does your software reliably handle this?
Jun 09 2012
next sibling parent Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 09.06.2012 21:47, Joseph Rushton Wakeling wrote:

 On Saturday, 9 June 2012 at 01:11:49 UTC, Stewart Gordon wrote:

 Including it in D seems very unlikely.

 Including it in Phobos, OTOH, is another matter.


 My bad phrasing. Of course in Phobos.


 On 09/06/12 08:25, SomeDude wrote:

 I've never had any use for rational numbers as have 99% of developers
 I believe.
 Maybe I'm overlooking something, but I see only two possible usages of
 them:
 math packages and length quotations in the english system. Because of
 this, I'd
 rather see them in Deimos than in Phobos.


 In fact the application I had in mind was for music software, where you
 want to be able to store pitch changes in fractions of a whole tone. In
 that context it's important that adding up those changes be guaranteed
 to produce exact results.

 e.g. if you take middle C and raise it by 1 whole tone _exactly_ you
 arrive at the note D. If you raise it by 0.99999999999999999999999999995
 instead, how does your software reliably handle this?


Prescaling works just fine. That is use plain integer and assume it 
holds value in the smallest fraction possible. Then define functions 
that do scale and round it to tone, note etc.

-- 
Dmitry Olshansky
Jun 09 2012
prev sibling parent reply Stewart Gordon <smjg_1998 yahoo.com> writes:
On 09/06/2012 18:47, Joseph Rushton Wakeling wrote:

 On Saturday, 9 June 2012 at 01:11:49 UTC, Stewart Gordon wrote:

 Including it in D seems very unlikely.

 Including it in Phobos, OTOH, is another matter.


 My bad phrasing.  Of course in Phobos.


 On 09/06/12 08:25, SomeDude wrote:

 I've never had any use for rational numbers as have 99% of developers I
believe.
 Maybe I'm overlooking something, but I see only two possible usages of them:
 math packages and length quotations in the english system. Because of this, I'd
 rather see them in Deimos than in Phobos.


 In fact the application I had in mind was for music software, where you want
to be able to
 store pitch changes in fractions of a whole tone.  In that context it's
important that
 adding up those changes be guaranteed to produce exact results.

 e.g. if you take middle C and raise it by 1 whole tone _exactly_ you arrive at
the note
 D.  If you raise it by 0.99999999999999999999999999995 instead, how does your
software
 reliably handle this?


By using an integer type to store pitches in such a way that the semitone is
the basic unit.

Do you compose music that makes use of demisemitones, thirds of tones, and so
on?

Stewart.
Jun 09 2012
parent reply Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:
On 10/06/12 00:52, Stewart Gordon wrote:

 By using an integer type to store pitches in such a way that the semitone is
the
 basic unit.

 Do you compose music that makes use of demisemitones, thirds of tones, and so
on?


Yes, I use quarter-tones.  Other people use other intervals (e.g. in Turkish 
music there are intervals of 1/9, 4/9, 5/9 and 8/9 of a tone; and let's not
even 
get into what Harry Partch and his compositional descendants have used).  I'd 
like to support all those options.  A straightforward rational number seems the 
easiest way to do so.
Jun 09 2012
parent Stewart Gordon <smjg_1998 yahoo.com> writes:
On 10/06/2012 02:17, Joseph Rushton Wakeling wrote:

 On 10/06/12 00:52, Stewart Gordon wrote:

 By using an integer type to store pitches in such a way that the semitone is
the
 basic unit.

 Do you compose music that makes use of demisemitones, thirds of tones, and so
on?


 Yes, I use quarter-tones.  Other people use other intervals (e.g. in Turkish
music there
 are intervals of 1/9, 4/9, 5/9 and 8/9 of a tone; and let's not even get into
what Harry
 Partch and his compositional descendants have used).


<snip>

Are you not getting into that because his system uses irrational multiples of
tones?

Supporting just intonation as well as equal temperament would be a good
long-term plan. 
One way to achieve this would be to give the user the choice of rational
numbers 
representing multiples of tones (or semitones or octaves) and rational numbers 
representing frequency ratios.  But you might be only worrying about supporting
the former 
at the moment.

Stewart.
Jun 10 2012
prev sibling parent reply dsimcha <dsimcha yahoo.com> writes:
A long time ago, this was discussed on this forum.  I wrote the current 
candidate for std.rational, and there was talk of Don Clugston 
integrating the GCD function into std.bigint to take advantage of 
knowing BigInt's internals.  According to Don, using a general algorithm 
here results in terrible performance.  As of now, that hasn't happened, 
though.

On 6/7/2012 1:49 PM, Joseph Rushton Wakeling wrote:

 Sorry for the double-post -- I already asked this in d-learn, but this
 may be a better place to ask.

 What's the current state of affairs and roadmap for inclusion of
 rational number support in D?  I've come across David Simcha's work:
 http://cis.jhu.edu/~dsimcha/d/phobos/std_rational.html

 .... and a feature request on the bugzilla:
 http://d.puremagic.com/issues/show_bug.cgi?id=7885

 .... but this isn't mentioned at all in the review queue:
 http://prowiki.org/wiki4d/wiki.cgi?ReviewQueue

 What's the status of work/planning for this feature and is there any
 kind of ETA for when it might land in Phobos?

 Thanks and best wishes,

      -- Joe
Jun 09 2012
next sibling parent Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:
On 10/06/12 03:01, dsimcha wrote:

 A long time ago, this was discussed on this forum. I wrote the current
candidate
 for std.rational, and there was talk of Don Clugston integrating the GCD
 function into std.bigint to take advantage of knowing BigInt's internals.
 According to Don, using a general algorithm here results in terrible
 performance. As of now, that hasn't happened, though.


I saw that Bearophile has contributed some code for this:
http://d.puremagic.com/issues/show_bug.cgi?id=7102#c3
Jun 10 2012
prev sibling parent reply Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:
On 10/06/12 13:17, Joseph Rushton Wakeling wrote:

 I saw that Bearophile has contributed some code for this:
 http://d.puremagic.com/issues/show_bug.cgi?id=7102#c3


Ooops, not code, just a spec.  If people are interested I'll see if I can write 
something based on this.
Jun 10 2012
parent reply "Paul D. Anderson" <paul.d.removethis.anderson comcast.andthis.net> writes:
On Sunday, 10 June 2012 at 14:34:17 UTC, Joseph Rushton Wakeling 
wrote:

 On 10/06/12 13:17, Joseph Rushton Wakeling wrote:

 I saw that Bearophile has contributed some code for this:
 http://d.puremagic.com/issues/show_bug.cgi?id=7102#c3


 Ooops, not code, just a spec.  If people are interested I'll 
 see if I can write something based on this.


This is not quite ready for prime time, but I have implemented a 
fixed-size integer module which includes a gcd algorithm. It 
limited to unsigned integers at the moment:

https://github.com/andersonpd/decimal/blob/master/decimal/unsigned.d

The gcd algorithm is base on Algorithm 1.18, BinaryGcd, p. 31, 
from Modern Computer Arithmetic, Richard Brent and Paul 
Zimmermann, Cambridge University Press, 2010.

An online PDF version is found at 
http://www.loria.fr/~zimmerma/mca/pub226.html

I don't know that it is particularly efficient but with small 
integers (< 1000 bits) it should be competitive.

Paul
Jun 10 2012
parent reply "Paul D. Anderson" <paul.d.removethis.anderson comcast.andthis.net> writes:
It seems like we ought to have rational numbers in Phobos along 
with other number types. Something like this:

std.number.rational;
std.number.decimal;
std.number.integer; (fixed-size signed and unsigned integers, 
"safe" integers that throw on overflow or rollover, like Andrei's 
CheckedInt module, etc.
std.number.complex; (I know, I know)
std.number.quaternion;
std.number.fixedpoint;
std.number.interval (Interval arithmetic on floating-point 
numbers)

We also need compatible scalar, vector, matrix, multiarray 
modules, etc.

Many of these exist, but aren't incorporated in Phobos. I think 
we need to be more aggressive in recruiting functionality for 
Phobos. There are a lot of talented coders out there.

Paul
Jun 10 2012
next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Sunday, June 10, 2012 21:05:18 Paul D. Anderson wrote:

 It seems like we ought to have rational numbers in Phobos along
 with other number types. Something like this:
 
 std.number.rational;
 std.number.decimal;
 std.number.integer; (fixed-size signed and unsigned integers,
 "safe" integers that throw on overflow or rollover, like Andrei's
 CheckedInt module, etc.
 std.number.complex; (I know, I know)
 std.number.quaternion;
 std.number.fixedpoint;
 std.number.interval (Interval arithmetic on floating-point
 numbers)
 
 We also need compatible scalar, vector, matrix, multiarray
 modules, etc.
 
 Many of these exist, but aren't incorporated in Phobos. I think
 we need to be more aggressive in recruiting functionality for
 Phobos. There are a lot of talented coders out there.


I am frequently amazed at what other programmers find useful or not. 
Personally, I don't think that I would ever have any use for _any_ of these 
modules. That's not to say that they wouldn't be worth having. I just find it 
interesting what others think would be useful (especially what they think are 
"must haves") - particularly when it's stuff that I'd never use.

- Jonathan M Davis
Jun 10 2012
prev sibling parent Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 10.06.2012 23:05, Paul D. Anderson wrote:

 It seems like we ought to have rational numbers in Phobos along with
 other number types. Something like this:

 std.number.rational;
 std.number.decimal;
 std.number.integer; (fixed-size signed and unsigned integers, "safe"
 integers that throw on overflow or rollover, like Andrei's CheckedInt
 module, etc.
 std.number.complex; (I know, I know)
 std.number.quaternion;
 std.number.fixedpoint;
 std.number.interval (Interval arithmetic on floating-point numbers)


Let's turn numeric into a package. Then
std.numeric.algorithms - existing std.numeric
std.numeric.decimal
std.numeric.integer (or even better - fixnum)
std.numeric.quaternion
...
I'd argue even std.complex should go there.


 We also need compatible scalar, vector, matrix, multiarray modules, etc.

 Many of these exist, but aren't incorporated in Phobos. I think we need
 to be more aggressive in recruiting functionality for Phobos. There are
 a lot of talented coders out there.


Right. If anything people around here lack time not talent or dedication.



-- 
Dmitry Olshansky
Jun 10 2012