www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Preliminary submission - std.rational and std.typelist

reply "Arlen" <arlen.ng gmx.com> writes:
Greetings,

In one of my D projects a units library was needed, so I decided to port
Boost.Units to D.  I've been working on it for the past month or so (mostly on
the weekends), and It's about 90% done.  The work has also produced additional
functionality not yet available in Phobos, so I've decided to separate them
into their own modules and present them here as my preliminary submission.  At
the time I wasn't aware of the Boost submission process, otherwise I would have
done "Determine Interest" first.  Hopefully nobody has ported Boost.Units to D.

So far the completion of the units library is contingent on the finalization of
the design and implementation of the following two modules:

std.rational, which is a small module for rational numbers.
Source:  https://github.com/Arlen/phobos/blob/units/std/rational.d
Docs:  http://arlen.github.com/phobos/std_rational.html

std.typelist, which provides the TypeList type and several metafunctions.  The
metafunctions are pretty much stolen from Haskell.  
Source:  https://github.com/Arlen/phobos/blob/units/std/typelist2.d
Docs:  http://arlen.github.com/phobos/std_typelist2.html


I wasn't aware that we already had std.typelist module in Phobos until I was
ready to submit my work.  I suppose the work was abandoned or it was never
finalized?  There are differences in typelist2.d and typelist.d, though.

I would be interested to know if there is any interest in a units library.  I
certainly need it in my project, and I will make my preliminary submission
available to the community once it's complete.

Thanks,

Arlen
Oct 06 2012
next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Arlen:

Regarding units in D, here I have shown a (hopefully) nice usage 
syntax:

http://forum.dlang.org/thread/uchcycnsvykuojzhuokh forum.dlang.org#post-qnbpufluqlaxfyxzwxnq:40forum.dlang.org


 std.rational, which is a small module for rational numbers.
 Source: 
  https://github.com/Arlen/phobos/blob/units/std/rational.d
 Docs:  http://arlen.github.com/phobos/std_rational.html

I'd like a Rational in Phobos. Have you tested it (in unittests) widely with Bigints?
 std.typelist, which provides the TypeList type and several 
 metafunctions.  The metafunctions are pretty much stolen from 
 Haskell.  
 Source: 
  https://github.com/Arlen/phobos/blob/units/std/typelist2.d
 Docs:  http://arlen.github.com/phobos/std_typelist2.html

Aren't TypeTuples enough? Bye, bearophile
Oct 06 2012
next sibling parent Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:
On 10/06/2012 07:54 PM, bearophile wrote:
 I'd like a Rational in Phobos. Have you tested it (in unittests) widely with
 Bigints?

Seconded, this would be very nice to see.
Oct 06 2012
prev sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Sat, Oct 06, 2012 at 10:54:31PM +0200, Joseph Rushton Wakeling wrote:
 On 10/06/2012 07:54 PM, bearophile wrote:
I'd like a Rational in Phobos. Have you tested it (in unittests) widely with
Bigints?

Seconded, this would be very nice to see.

+1. T -- Computers are like a jungle: they have monitor lizards, rams, mice, c-moss, binary trees... and bugs.
Oct 06 2012
prev sibling next sibling parent reply "David Nadlinger" <see klickverbot.at> writes:
On Saturday, 6 October 2012 at 17:56:39 UTC, Arlen wrote:
 Hopefully nobody has ported Boost.Units to D.

I wrote a units library in D last year: http://klickverbot.at/code/units/. Before setting out, I extensively researched existing solutions in other languages, Boost.Units being on of them, and I believe that I managed to come up with a design which takes advantage of D's advanced metaprogramming capabilities, and as such is more powerful while being much less clunky. For example, in comparison to Boost.Units, I didn't introduce a notion of "dimension" separate from the concept of units, which seemed to ultimately serve no purpose besides making valid conversions easier to determine given the limitations of C++. I'd love to hear your comments on the design! There didn't seem much interest in it back then, but I know Andrei and a few others would like to see something like it in Phobos. It is pretty much finished, but needs a bit of polish here and there (many compiler improvements have been made since I wrote it). Unfortunately, I'm currently swamped in other work, though…
 std.typelist, which provides the TypeList type and several 
 metafunctions.  The metafunctions are pretty much stolen from 
 Haskell.  
 Source: 
  https://github.com/Arlen/phobos/blob/units/std/typelist2.d
 Docs:  http://arlen.github.com/phobos/std_typelist2.html

What are the real benefits of this over std.typetuple? We recently discussed what to do with std.typelist, which, as you noticed, has been bitrotting without being included in the official documentation. As far as I remember, there was consensus that having another implementation of "compile-time tuples" besides std.typetuple is not something we really want to do. David
Oct 06 2012
parent Arlen <arlen.ng gmx.com> writes:
Testing...
Oct 06 2012
prev sibling next sibling parent reply "Arlen" <arlen.ng gmx.com> writes:
I'm not sure if TypeTuples work well when doing things like dimensional
analysis.  For example, if you have two TypeTuples, A and B, what would the
signature of the metafunction to merge the two look like?

template Merge(A, B) { }

won't work, and neither will

template Merge(alias A, alias B) { }

and you certainly can't do something like

template Merge(AB...) { }

Arlen

 
  ----- Original Message -----
  From: Jonathan M Davis
  Sent: 10/06/12 12:52 PM
  To: digitalmars.D
  Subject: Re: Preliminary submission - std.rational and std.typelist
 
   
On Saturday, October 06, 2012 19:03:39 Arlen wrote:
 I wasn't aware that we already had std.typelist module in Phobos until I was
 ready to submit my work. I suppose the work was abandoned or it was never
 finalized? There are differences in typelist2.d and typelist.d, though.

It needs to be removed. It's not even compiled in. std.typetuple is what we use. I would suggest looking at adding further functionality to it rather than trying to create anything based on type lists. TypeTuples can do the same things and are actually more flexible. - Jonathan M Davis  
Oct 06 2012
parent "David Nadlinger" <see klickverbot.at> writes:
On Saturday, 6 October 2012 at 18:13:19 UTC, Arlen wrote:
 For example, if you have two TypeTuples, A and B, what would 
 the signature of the metafunction to merge the two look like?

In my experience, these cases occur a lot less frequently than one might think when first encountering the problem. The solution I usually go for is to just define a ConfinedTuple (or something like that) template: --- template ConfinedTuple(T...) { alias T Tuple; } template SomeAlgorithm(alias A, alias B) {} --- Then, call that one algorithm using SomeAlgorithm!(ConfinedTuple!A, ConfinedTuple!B). At least to me, it seems to be the better tradeoff compared to re-implementing all the TypeTuple functionality for another compile-time tuple type. David
Oct 06 2012
prev sibling next sibling parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 06-Oct-12 21:03, Arlen wrote:
 Greetings,

 In one of my D projects a units library was needed, so I decided to port
Boost.Units to D.  I've been working on it for the past month or so (mostly on
the weekends), and It's about 90% done.  The work has also produced additional
functionality not yet available in Phobos, so I've decided to separate them
into their own modules and present them here as my preliminary submission.  At
the time I wasn't aware of the Boost submission process, otherwise I would have
done "Determine Interest" first.  Hopefully nobody has ported Boost.Units to D.

 So far the completion of the units library is contingent on the finalization
of the design and implementation of the following two modules:

 std.rational, which is a small module for rational numbers.
 Source:  https://github.com/Arlen/phobos/blob/units/std/rational.d
 Docs:  http://arlen.github.com/phobos/std_rational.html

Cool, does it work with BigInt? Also I think there is better version of toString that has signature: void toString(scope void delegate(const(char)[]) sink) this toString just use functions like formattedWrite to write chars to sink. It thus totally avoids overhead of allocating strings. Your current code may have some bad impact on performance: return "(" ~ to!string(res.numerator) ~ "/" ~ to!string(res.denominator) ~ ")"; Allocates 4 times. ~ operator is convenient shortcut to get job done but it's unsuitable for building strings and formatted output.
 std.typelist, which provides the TypeList type and several metafunctions.  The
metafunctions are pretty much stolen from Haskell.
 Source:  https://github.com/Arlen/phobos/blob/units/std/typelist2.d
 Docs:  http://arlen.github.com/phobos/std_typelist2.html

I concur with the general idea that it needs to be folded into std.typetuple unless there is some *really* compelling reason not to.
 I wasn't aware that we already had std.typelist module in Phobos until I was
ready to submit my work.  I suppose the work was abandoned or it was never
finalized?  There are differences in typelist2.d and typelist.d, though.

Old and never finalized. Recently re-'discovered'. It never participated in the compilation of Phobos and sort of went under the radar. -- Dmitry Olshansky
Oct 06 2012
next sibling parent reply Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Sat, Oct 6, 2012 at 8:32 PM, Dmitry Olshansky <dmitry.olsh gmail.com> wrote:

 Your current code may have some bad impact on performance:
 return "(" ~ to!string(res.numerator) ~ "/" ~ to!string(res.denominator) ~
 ")";

 Allocates 4 times. ~ operator is convenient shortcut to get job done but
 it's unsuitable for building strings and formatted output.

And the solution is?
Oct 07 2012
parent reply "Jakob Ovrum" <jakobovrum gmail.com> writes:
On Sunday, 7 October 2012 at 07:36:08 UTC, Philippe Sigaud wrote:
 On Sat, Oct 6, 2012 at 8:32 PM, Dmitry Olshansky 
 <dmitry.olsh gmail.com> wrote:

 Your current code may have some bad impact on performance:
 return "(" ~ to!string(res.numerator) ~ "/" ~ 
 to!string(res.denominator) ~
 ")";

 Allocates 4 times. ~ operator is convenient shortcut to get 
 job done but
 it's unsuitable for building strings and formatted output.

And the solution is?

Appender and formattedWrite can do this with a minimal amount of memory allocations. The best solution is of course the writeTo function from DIP9 [1], which hasn't been accepted yet for some reason. [1] http://www.prowiki.org/wiki4d/wiki.cgi?LanguageDevel/DIPs/DIP9
Oct 07 2012
parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 07-Oct-12 12:10, Jakob Ovrum wrote:
 On Sunday, 7 October 2012 at 07:36:08 UTC, Philippe Sigaud wrote:
 On Sat, Oct 6, 2012 at 8:32 PM, Dmitry Olshansky
 <dmitry.olsh gmail.com> wrote:

 Your current code may have some bad impact on performance:
 return "(" ~ to!string(res.numerator) ~ "/" ~
 to!string(res.denominator) ~
 ")";

 Allocates 4 times. ~ operator is convenient shortcut to get job done but
 it's unsuitable for building strings and formatted output.

And the solution is?

Appender and formattedWrite can do this with a minimal amount of memory allocations. The best solution is of course the writeTo function from DIP9 [1], which hasn't been accepted yet for some reason. [1] http://www.prowiki.org/wiki4d/wiki.cgi?LanguageDevel/DIPs/DIP9

Ehem.. I've been pushing for DIP9 a lot of time. But then I find out that it is already here (and been for some time). Like I said use a special overload of toString that is exactly writeTo. Just define method with this signature: void toString(scope void delegate(const(char)[]) sink) And bingo! It's used in all of formatting stuff like write(f)(ln), format, formattedWrite etc. e.g. before posting I played with this: import std.stdio, std.format; struct A{ int k; void toString(scope void delegate(const(char)[]) sink) { formattedWrite(sink, "[%d]", k); } } void main(){ A a = A(90); writeln(a); } -- Dmitry Olshansky
Oct 07 2012
next sibling parent reply "Jakob Ovrum" <jakobovrum gmail.com> writes:
On Sunday, 7 October 2012 at 09:27:54 UTC, Dmitry Olshansky wrote:
 Ehem.. I've been pushing for DIP9 a lot of time. But then I 
 find out that it is already here (and been for some time).

 Like I said use a special overload of toString that is exactly 
 writeTo.

 Just define method with this signature:
 void toString(scope void delegate(const(char)[]) sink)

 And bingo! It's used in all of formatting stuff like 
 write(f)(ln), format, formattedWrite etc.

 e.g. before posting I played with this:

 import std.stdio, std.format;

 struct A{
 	int k;
 	void toString(scope void delegate(const(char)[]) sink)
 	{
 		formattedWrite(sink, "[%d]", k);
 	}
 }

 void main(){
 	A a = A(90);
 	writeln(a);
 }

Nice! I didn't know that. I thought this toString signature was only used by BigInt, and not taken advantage of by other routines. To implement it fully we would still want to change toString for classes, and probably do something like providing a UFCS function in object.toString or some other relevant location for convenience and backwards compatibility.
Oct 07 2012
parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Sunday, October 07, 2012 11:37:30 Jakob Ovrum wrote:
 To implement it fully we would still want to change toString for
 classes, and probably do something like providing a UFCS function
 in object.toString or some other relevant location for
 convenience and backwards compatibility.

Well, considering that we're looking at removing toString, toHash, opCmp, and opEquals from Object entirely, that probably won't be necessary. But that particular plan hasn't gotten past the initial discussions AFAIK, so who knows exactly how it's going to go or when it's going to happen. - Jonathan M Davis
Oct 07 2012
parent "Jakob Ovrum" <jakobovrum gmail.com> writes:
On Sunday, 7 October 2012 at 09:58:54 UTC, Jonathan M Davis wrote:
 Well, considering that we're looking at removing toString, 
 toHash, opCmp, and
 opEquals from Object entirely, that probably won't be 
 necessary. But that
 particular plan hasn't gotten past the initial discussions 
 AFAIK, so who knows
 exactly how it's going to go or when it's going to happen.

 - Jonathan M Davis

This is definitely something I would like to happen.
Oct 07 2012
prev sibling next sibling parent reply Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Sun, Oct 7, 2012 at 11:15 AM, Dmitry Olshansky <dmitry.olsh gmail.com> wrote:
 import std.stdio, std.format;

 struct A{
         int k;

         void toString(scope void delegate(const(char)[]) sink)
         {
                 formattedWrite(sink, "[%d]", k);
         }
 }

I see, thanks. And if the string in formattedWrite is a complex beast, created through lots of if's and while's, I use Appender in its place?
Oct 07 2012
parent "David Nadlinger" <see klickverbot.at> writes:
On Sunday, 7 October 2012 at 15:36:52 UTC, Philippe Sigaud wrote:
 I see, thanks. And if the string in formattedWrite is a complex 
 beast,
 created through lots of if's and while's, I use Appender in its 
 place?

Ideally, you just write to the sink directly, piece by piece – but if for some reason you _need_ to have one big format string, then yes, prefer using Appender over string concatenation. David
Oct 07 2012
prev sibling next sibling parent Artur Skawina <art.08.09 gmail.com> writes:
On 10/07/12 17:24, Philippe Sigaud wrote:
 On Sun, Oct 7, 2012 at 11:15 AM, Dmitry Olshansky <dmitry.olsh gmail.com>
wrote:
 import std.stdio, std.format;

 struct A{
         int k;

         void toString(scope void delegate(const(char)[]) sink)
         {
                 formattedWrite(sink, "[%d]", k);
         }
 }

I see, thanks. And if the string in formattedWrite is a complex beast, created through lots of if's and while's, I use Appender in its place?

You can write to the sink directly, eg struct EnumBits(alias E) { E e; alias e this; void toString(DG, FT)(scope DG sink, in FT fmt) const { import std.format; sink(E.stringof ~ "{"); int wrote; foreach (member; __traits(allMembers, E)) if (__traits(getMember, E, member) & e){ if (wrote++) sink("|"); sink(member); } if (!wrote) sink("/*No " ~ E.stringof ~ "*/"); sink("}"); } } It gets a bit more tricky when you for example need to print the contents of containers w/o copying the data; but you can then just call their toString method directly: struct PTR_LIST(T, bool TAGGED=0) { c_int nr; PTR_LIST *prev; PTR_LIST *next; // ... void toString(DG, FT)(scope DG sink, in FT fmt) const { import std.format; sink(typeof(cast()this).stringof ~ "{["); formatValue(sink, nr, fmt); sink("]"); foreach (p; this) { p.toString(sink, fmt); sink(", "); } sink("}"); } static struct Anchor { PTR_LIST* list; // ... void toString(DG, FT)(scope DG sink, in FT fmt) const { import std.format; // Cannot 'formatValue(sink, *list, fmt);' as the struct is passed // by value and that messes up the list (head pointer doesn't match). list.toString(sink, fmt); } } } /* Obviously, i wasn't trying to avoid allocations, hence the presence of '~'s. */ artur
Oct 07 2012
prev sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
Artur and David:
 You can write to the sink directly, eg

(snip nice example) Ah, OK. I use the sink throughout. Thanks.
Oct 07 2012
prev sibling next sibling parent Arlen <arlen.ng gmx.com> writes:
On Sat, Oct 6, 2012 at 1:32 PM, Dmitry Olshansky <dmitry.olsh gmail.com> wrote:
 Cool, does it work with BigInt?

No it doesn't work with BigInt, but I did look into it today briefly. There are issues with BigInt that I'm not sure what to do about: 1. To convert a BigInt to floating-point one needs to convert it to the built-in integer types first. If you go beyond the limits of the built-in types (long), then what's the point? You might as well be using int or long. 2. The functions in std.math don't support BigInt, and most likely never will. Even if they did, you would still need multi-precision floating point to store the irrational numbers. If you decided to use the built-in types, then again what's the point? You might as well go with int or long.
 Also I think there is better version of toString that has signature:
 void toString(scope void delegate(const(char)[]) sink)

 this toString just use functions like formattedWrite to write chars to sink.
 It thus totally avoids overhead of allocating strings.

 Your current code may have some bad impact on performance:
 return "(" ~ to!string(res.numerator) ~ "/" ~ to!string(res.denominator) ~
 ")";

 Allocates 4 times. ~ operator is convenient shortcut to get job done but
 it's unsuitable for building strings and formatted output.

Thanks, I'll fix it.
Oct 07 2012
prev sibling next sibling parent "Simen Kjaeraas" <simen.kjaras gmail.com> writes:
On 2012-44-08 06:10, Arlen <arlen.ng gmx.com> wrote:

 On Sat, Oct 6, 2012 at 1:32 PM, Dmitry Olshansky <dmitry.olsh gmail.com>  
 wrote:
 Cool, does it work with BigInt?

No it doesn't work with BigInt, but I did look into it today briefly. There are issues with BigInt that I'm not sure what to do about: 1. To convert a BigInt to floating-point one needs to convert it to the built-in integer types first. If you go beyond the limits of the built-in types (long), then what's the point? You might as well be using int or long.

I thought (part of) the point of Rational was to use it when it would be more fitting than floating-point. If it's only there to be converted to floating-point, I don't know what it's there for. As for a workaround, right-shift num and den to reasonable values (which fit in a long), divide to get a float, and multiply by 2.0^^(log2(num)-log2(den)). Oughta work.
 2.  The functions in std.math don't support BigInt, and most likely
 never will.  Even if they did, you would still need multi-precision
 floating point to store the irrational numbers.  If you decided to use
 the built-in types, then again what's the point?  You might as well go
 with int or long.

The only function you use from std.math is abs, right? That should be fairly easy to implement for BigInt. It'd mean you'd have to specialize a bit for BigInt, though (just create your own abs function that calls the correct one). Another option: lobby for BigInt support in std.math. :p Also, irrational numbers? How'd you get those in a *Rational* library? :p -- Simen
Oct 08 2012
prev sibling next sibling parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Mon, Oct 08, 2012 at 09:08:57AM +0200, Simen Kjaeraas wrote:
 On 2012-44-08 06:10, Arlen <arlen.ng gmx.com> wrote:
 
On Sat, Oct 6, 2012 at 1:32 PM, Dmitry Olshansky
<dmitry.olsh gmail.com> wrote:
Cool, does it work with BigInt?

No it doesn't work with BigInt, but I did look into it today briefly. There are issues with BigInt that I'm not sure what to do about: 1. To convert a BigInt to floating-point one needs to convert it to the built-in integer types first. If you go beyond the limits of the built-in types (long), then what's the point? You might as well be using int or long.

I thought (part of) the point of Rational was to use it when it would be more fitting than floating-point. If it's only there to be converted to floating-point, I don't know what it's there for.

I'd like to chime in to state that I'd love to have Rational support BigInt. If necessary, use an arbitrary-width floating point format for floating point conversions (BigFloat?). [...]
 It'd mean you'd have to specialize a bit for BigInt, though (just
 create your own abs function that calls the correct one).
 
 Another option: lobby for BigInt support in std.math. :p

+1.
 Also, irrational numbers? How'd you get those in a *Rational* library? :p

[...] Ironically enough, if Rational supports BigInt, then it makes it possible to implement a representation of quadratic irrationals in a straightforward way (by storing them in the form a+b*sqrt(r) where a and b are Rationals and r is a square-free Rational). The reason BigInt is necessary is that while these things are closed under field operations, any non-trivial work with them tends to overflow built-in integer types very quickly. BigInt becomes even more necessary if you want to represent quadratic irrationals of *two* distinct square roots, which can be represented as a+b*sqrt(r)+c*sqrt(s)+d*sqrt(rs), where a,b,c,d are Rationals and r,s are square-free Rationals. Believe it or not, these little monsters are also closed under field operations. But they also overflow built-in integers *very* fast. With BigInt support, however, you can do *exact* arithmetic with these irrational numbers, something very useful for applications in computational geometry, where the lack of exact arithmetic makes many problems intractible or prone to wrong results. T -- I'm still trying to find a pun for "punishment"...
Oct 08 2012
parent reply "Aziz K." <aziz.koeksal gmail.com> writes:
On Mon, 08 Oct 2012 09:28:37 +0200, H. S. Teoh <hsteoh quickfur.ath.cx>  
wrote:

 I'd like to chime in to state that I'd love to have Rational support
 BigInt. If necessary, use an arbitrary-width floating point format for
 floating point conversions (BigFloat?).

Incidentally, I would very much need a BigFloat class/struct, written in D and independent of any C library. I'm trying to write one myself, but it seems to be rather tricky. Could this be implemented in a short amount of time by someone with more knowledge about this topic? -- My D Compiler: http://code.google.com/p/dil
Oct 08 2012
next sibling parent reply Ellery Newcomer <ellery-newcomer utulsa.edu> writes:
On 10/08/2012 07:56 AM, Aziz K. wrote:
 Incidentally, I would very much need a BigFloat class/struct, written in
 D and independent of any C library.
 I'm trying to write one myself, but it seems to be rather tricky. Could
 this be implemented in a short amount of time by someone with more
 knowledge about this topic?

Wasn't Paul D. Anderson working on a BigFloat?
Oct 08 2012
parent "Aziz K." <aziz.koeksal gmail.com> writes:
On Mon, 08 Oct 2012 23:01:42 +0200, Ellery Newcomer  
<ellery-newcomer utulsa.edu> wrote:

 Wasn't Paul D. Anderson working on a BigFloat?

Thanks for the hint. I found his project on github: https://github.com/andersonpd/decimal Seems fairly complete and usable. Hope he's going to continue to develop and maintain it.
Oct 09 2012
prev sibling parent reply "Paul D. Anderson" <paul.d.removethis.anderson comcast.andthis.net> writes:
On Monday, 8 October 2012 at 15:14:35 UTC, Aziz K. wrote:
 Incidentally, I would very much need a BigFloat class/struct, 
 written in D and independent of any C library.
 I'm trying to write one myself, but it seems to be rather 
 tricky. Could this be implemented in a short amount of time by 
 someone with more knowledge about this topic?

Not in a short amount of time!! I've got a 95% complete library that handles BigDecimal numbers as well as Decimal32, Decimal64 and Decimal128 numbers. The BigDecimal numbers are fully implemented except for math functions (exp, ln, etc.) http://www.dsource.org/projects/decimal Paul
Oct 09 2012
parent "Aziz K." <aziz.koeksal gmail.com> writes:
On Tue, 09 Oct 2012 19:32:02 +0200, Paul D. Anderson  
<paul.d.removethis.anderson comcast.andthis.net> wrote:

 Not in a short amount of time!! I've got a 95% complete library that  
 handles BigDecimal numbers as well as Decimal32, Decimal64 and  
 Decimal128 numbers. The BigDecimal numbers are fully implemented except  
 for math functions (exp, ln, etc.)

 http://www.dsource.org/projects/decimal

 Paul

So glad you're working on this. Keep up the good work! ;-)
Oct 09 2012
prev sibling parent reply Arlen <arlen.ng gmx.com> writes:
On Mon, Oct 8, 2012 at 2:08 AM, Simen Kjaeraas <simen.kjaras gmail.com> wrote:
 On 2012-44-08 06:10, Arlen <arlen.ng gmx.com> wrote:

 1.  To convert a BigInt to floating-point one needs to convert it to
 the built-in integer types first.  If you go beyond the limits of the
 built-in types (long), then what's the point?  You might as well be
 using int or long.

I thought (part of) the point of Rational was to use it when it would be more fitting than floating-point. If it's only there to be converted to floating-point, I don't know what it's there for.

Some computations with rational numbers produce irrational numbers, and to store irrational numbers you need real numbers. What do we do in those cases?
 As for a workaround, right-shift num and den to reasonable values
 (which fit in a long), divide to get a float, and multiply by
 2.0^^(log2(num)-log2(den)). Oughta work.



 2.  The functions in std.math don't support BigInt, and most likely
 never will.  Even if they did, you would still need multi-precision
 floating point to store the irrational numbers.  If you decided to use
 the built-in types, then again what's the point?  You might as well go
 with int or long.

The only function you use from std.math is abs, right? That should be fairly easy to implement for BigInt. It'd mean you'd have to specialize a bit for BigInt, though (just create your own abs function that calls the correct one).

Yes, std.math.abs and std.numeric.gcd are very easy to implement for BigInt, but I'm not talking about those. I'm talking about things like std.math.pow(), and std.math.log().
Oct 08 2012
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Arlen:

 Yes, std.math.abs and std.numeric.gcd are very easy to 
 implement for BigInt,

Don doesn't agree regarding the gcd. To compute the gcd efficiently on large numbers you need not easy algorithms. See: http://d.puremagic.com/issues/show_bug.cgi?id=7102 Bye, bearophile
Oct 08 2012
parent Arlen <arlen.ng gmx.com> writes:
On Mon, Oct 8, 2012 at 4:37 PM, bearophile <bearophileHUGS lycos.com> wrote:
 Arlen:


 Yes, std.math.abs and std.numeric.gcd are very easy to implement for
 BigInt,

Don doesn't agree regarding the gcd. To compute the gcd efficiently on large numbers you need not easy algorithms. See: http://d.puremagic.com/issues/show_bug.cgi?id=7102 Bye, bearophile

gcd() is very easy to implement: BigInt _gcd(BigInt a, BigInt b) { enforce(a >= 0 && b >=0); while (b != 0) { auto t = b; b = a % b; a = t; } return a; } It's not going to be the fastest or the most efficient, but it does produce correct results, and that's the most important thing when implementing mathematical functions IMO. You can always improve the performance later. Implementing pow(), on the other hand, is very difficult and complex.
Oct 08 2012
prev sibling next sibling parent "Arlen" <arlen.ng gmx.com> writes:
There are many unittests, but std.rational doesn't work with BigInts.  It only
works with signed integrals because I wasn't sure how to deal with the overflow
problem.

 
  ----- Original Message -----
  From: bearophile
  Sent: 10/06/12 12:54 PM
  To: digitalmars-d puremagic.com
  Subject: Re: Preliminary submission - std.rational and std.typelist
 
   
I'd like a Rational in Phobos. Have you tested it (in unittests) 
widely with Bigints?

Bye,
bearophile   
Oct 06 2012
prev sibling next sibling parent reply "Arlen" <arlen.ng gmx.com> writes:
I'll have more to say about the design in the future.  At the moment for me
porting Boost.Units to D is the fastest and the safest path to take.  Besides,
the math behind it is sound and and many years of hard work has gone into it.
 The problem with it, in my opionion, is that it's implemented in C++, :-).

I do want to mention that the distinction between dimension and unit is
important.  I rather see this:

Quantity!(length, float) a = 2 * metre;

than this:

Quantity!(metre, float) a = 2 * metre;

I'll spend more time going over you library once I have some free time.

Thanks,

Arlen

 ----- Original Message -----
 From: David Nadlinger
 Sent: 10/06/12 12:58 PM
 To: digitalmars-d puremagic.com
 Subject: Re: Preliminary submission - std.rational and std.typelist
 
 I wrote a units library in D last year: 
 http://klickverbot.at/code/units/. Before setting out, I 
 extensively researched existing solutions in other languages, 
 Boost.Units being on of them, and I believe that I managed to 
 come up with a design which takes advantage of D's advanced 
 metaprogramming capabilities, and as such is more powerful while 
 being much less clunky.
 
 For example, in comparison to Boost.Units, I didn't introduce a 
 notion of "dimension" separate from the concept of units, which 
 seemed to ultimately serve no purpose besides making valid 
 conversions easier to determine given the limitations of C++. I'd 
 love to hear your comments on the design!
 
 
 David

Oct 06 2012
parent "David Nadlinger" <see klickverbot.at> writes:
On Saturday, 6 October 2012 at 19:40:10 UTC, Arlen wrote:
 Besides, the math behind it is sound and and many years of hard 
 work has gone into it.

Also, it is extremely complicated by the fact that it somehow has to work withing the boundaries of C++ and boost::mpl and friends.
 I do want to mention that the distinction between dimension and 
 unit is important.

Why? From a theorist standpoint, there of course is a distinction between the two, yes. In practice, however, a dimension is simply a connected component in the graph of (non-composite) units, where the edges represent known conversions, i.e. a dimension is just a name for a set of units which can converted into each other. The concept of dimensions arises naturally, and no rigor is lost by not explicitly having it; there is no need to force the redundancy on the programmer. In fact, my library was also based on dimensions originally, but at some point, they became an annoyance in the code I wrote using it, and I discovered that I could do perfectly fine without them.
 I rather see this:

 Quantity!(length, float) a = 2 * metre;

 than this:

 Quantity!(metre, float) a = 2 * metre;

Really? The first has the problem that you have absolutely no idea what a is really represented like in memory – you need to have a canonical base unit all other units are automatically converted to. One consequence of that is that you are forced to do a lot of unneeded conversions if you can't completely work in that base unit, for example for interfacing with code that doesn't use your unit system. You also can't just transparently tack a unit on a quantity in places where the actual value is important, think serialization, ABI boundaries, etc. Not being able to chose your representation might also lead to precision issues if you are working with base types of limited width. In contrast, the concept of dimensions is easy to implement in terms of units. For example, you could just define 'isLength' as 'canConvert!meter' (it will accept any unit which can somehow, maybe not directly, converted into meters), and then implement a function like this: --- auto squareArea(T)(T side) if (isQuantity!T && isLength!(T.unit)) { return side * side; } --- squareArea now works transparently and without overhead with all unit types. Of course, you could also define the parameter as just Quantity!(meter, T) or Quantity!(meter, float) if for some reason you want to, for example because you are only working in meters anyway and you don't want to have a template function to avoid the (compile-time) overhead. I think the main reason why Boost.Units went with dimensions is that having a distinguished "canonical" unit for each dimension relieves the burden on the implementation in so far as you never have to synthesize code for arbitrary conversions, as your data is always stored in that canonical unit. David
Oct 06 2012
prev sibling next sibling parent reply "Arlen" <arlen.ng gmx.com> writes:
 ----- Original Message -----
 From: David Nadlinger
 Sent: 10/06/12 01:08 PM
 To: digitalmars-d puremagic.com
 Subject: Re: Preliminary submission - std.rational and std.typelist
 
 In my experience, these cases occur a lot less frequently than 
 one might think when first encountering the problem. The solution 
 I usually go for is to just define a ConfinedTuple (or something 
 like that) template:
 
 ---
 template ConfinedTuple(T...) {
  alias T Tuple;
 }
 
 template SomeAlgorithm(alias A, alias B) {}
 ---
 
 Then, call that one algorithm using 
 SomeAlgorithm!(ConfinedTuple!A, ConfinedTuple!B). At least to me, 
 it seems to be the better tradeoff compared to re-implementing 
 all the TypeTuple functionality for another compile-time tuple 
 type.
 
 David

That does solve the initial problem, but it creates problems of its own. The initial implementation of TypeList looked like this, which is same as your ConfinedTuple: template TypeList(T...) {  alias T items; } but the problem with this is that it forces you to use 'alias' in the signature, which in turn causes code duplication later on.  You need both of these if you want, for example, fold to work with n-dimensional typelists: template Foldl(alias Fun, Z, alias TL) {  } template Foldl(alias Fun, alias Z, alias TL) { } // when Z is a TypeList Thanks, Arlen
Oct 06 2012
parent reply "David Nadlinger" <see klickverbot.at> writes:
On Saturday, 6 October 2012 at 20:00:47 UTC, Arlen wrote:
 You need both of these if you want, for example, fold to work 
 with n-dimensional typelists:

 template Foldl(alias Fun, Z, alias TL) {  }
 template Foldl(alias Fun, alias Z, alias TL) { } // when Z is a 
 TypeList

I'm not quite sure what you mean, as the parameter names are not quite telling. When would the first overload be needed? Actually, I'm reasonably sure that there is a solution to whatever problem you might be encountering – if maybe not obvious unless you have already learned the ins and outs of D metaprogramming the hard way. ;) By the way, could you please fix the threading behavior of your mail client? At the moment, all of your replies create a new topic on the NG web interface (forum.dlang.org), which makes the conversation somewhat hard to follow. David
Oct 06 2012
next sibling parent Arlen <arlen.ng gmx.com> writes:
On Sat, Oct 6, 2012 at 3:53 PM, David Nadlinger <see klickverbot.at> wrote:
 On Saturday, 6 October 2012 at 20:00:47 UTC, Arlen wrote:
 You need both of these if you want, for example, fold to work with n-dim=


ensional typelists:
 template Foldl(alias Fun, Z, alias TL) {  }
 template Foldl(alias Fun, alias Z, alias TL) { } // when Z is a TypeList

I'm not quite sure what you mean, as the parameter names are not quite te=

lling. When would the first overload be needed? Actually, I'm reasonably su= re that there is a solution to whatever problem you might be encountering = =96 if maybe not obvious unless you have already learned the ins and outs o= f D metaprogramming the hard way. ;)

#1 template Foldl(alias Fun, Z, alias TL) { } This is called when dealing with 1-dimensional typelists. For example: alias Foldl!(MyFun, char, TL) R1; // where TL is, e.g., TypeList!(int, char, double) #2 template Foldl(alias Fun, alias Z, alias TL) { } This is called when dealing with 2-dimensions or higher. For example: alias Foldl!(MyFun, TL1, TL2) R2; // where TL1 is 1-dimensional, e.g., TypeList!(int, char), and TL2 is 2-dimensional, e.g., TypeList!(TypeList!(int, char), TypeList!(float, double)). I hope that's clear. Another problem with this is that, when the time comes to implement MyFun, chances are you will need to implement two versions of it, just like the Foldl example above. Making TypeList a struct instead of a template fixed all these problem. Maybe there another solution, but that's what I could come up with.
 By the way, could you please fix the threading behavior of your mail clie=

nt? At the moment, all of your replies create a new topic on the NG web int= erface (forum.dlang.org), which makes the conversation somewhat hard to fol= low.

Sorry about that. I think it's fixed now.
 David

Oct 06 2012
prev sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Sat, Oct 6, 2012 at 11:52 PM, Arlen <arlen.ng gmx.com> wrote:

 #1
 template Foldl(alias Fun, Z, alias TL) {  }

 This is called when dealing with 1-dimensional typelists.  For example:

 alias Foldl!(MyFun, char, TL) R1;  // where TL is, e.g.,
 TypeList!(int, char, double)

 #2
 template Foldl(alias Fun, alias Z, alias TL) { }

 This is called when dealing with 2-dimensions or higher.  For example:

I had a similar project a few years ago. Here it is: https://github.com/PhilippeSigaud/dranges/blob/master/typetuple.d and, somewhat related, to show what can be done with type tuples in D (regular expressions on types) https://github.com/PhilippeSigaud/dranges/blob/master/typepattern.d
Oct 07 2012
prev sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Sun, Oct 07, 2012 at 01:15:50PM +0400, Dmitry Olshansky wrote:
[...]
 Just define method with this signature:
 void toString(scope void delegate(const(char)[]) sink)
 
 And bingo! It's used in all of formatting stuff like write(f)(ln),
 format, formattedWrite etc.
 
 e.g. before posting I played with this:
 
 import std.stdio, std.format;
 
 struct A{
 	int k;
 	void toString(scope void delegate(const(char)[]) sink)
 	{
 		formattedWrite(sink, "[%d]", k);
 	}
 }
 
 void main(){
 	A a = A(90);
 	writeln(a);
 }

[...] +1. This is much more powerful and useful, not to mention more efficient in many cases (by avoiding the need to create multiple string buffers), than the current toString(). I like this. T -- We are in class, we are supposed to be learning, we have a teacher... Is it too much that I expect him to teach me??? -- RL
Oct 08 2012