I've converted my BigInt module from Tango to Phobos2. It's a great
test of the new operator overloading!
After 2.042 comes out, I'd like to add it to Phobos.

A couple of issues:
(1) We need somewhere in Phobos for implementation code (of which
there is a considerable amount for BigInt).

I propose std.internal.math.XXX; for all math related modules. This
would keep everything tidy and hidden.
None of this will be user-visible.

(2)  Syntax for conversion to string is undecided. Strawman:

 void toString(void delegate(const(char)[]) sink, string format);

where format is currently limited to:

d    for decimal
x    for lower case hex
X    for upper case hex

but will be extended in the future. If format is "", defaults to decimal. Sink takes a const(char)[] so that BigInt can keep reusing the same buffer.

Eventually, whatever is chosen will require some changes to std.format, but I'd just like to get a reasonable first cut for the initial release.

void toString(void delegate(const(char)[]) sink, string format) const;


That last const is important :)

-Steve


----- Original Message ----
> From: Don Clugston <dclugston at googlemail.com>
(2)  Syntax for conversion to string is undecided.
> Strawman:

void toString(void delegate(const(char)[]) sink, string
> format);

On 03/18/2010 10:46 PM, Don Clugston wrote:
> I've converted my BigInt module from Tango to Phobos2. It's a great
> test of the new operator overloading!
> After 2.042 comes out, I'd like to add it to Phobos.

Awesome! How do the operators hold?

> A couple of issues:
> (1) We need somewhere in Phobos for implementation code (of which
> there is a considerable amount for BigInt).
>
> I propose std.internal.math.XXX; for all math related modules. This
> would keep everything tidy and hidden.
> None of this will be user-visible.

Sounds good.

> (2)  Syntax for conversion to string is undecided. Strawman:
>
>   void toString(void delegate(const(char)[]) sink, string format);
>
> where format is currently limited to:
>
> d    for decimal
> x    for lower case hex
> X    for upper case hex

s or null for "whatever" for conformity.

> but will be extended in the future. If format is "", defaults to decimal. Sink takes a const(char)[] so that BigInt can keep reusing the same buffer.
>
> Eventually, whatever is chosen will require some changes to std.format, but I'd just like to get a reasonable first cut for the initial release.

That's fine; we need to look again at std.format anyway.

Speaking of which - do we have good code for parsing and writing floating point numbers? I need it for unformat().


Andrei

On 19 March 2010 07:20, Andrei Alexandrescu <andrei at erdani.com> wrote:
> On 03/18/2010 10:46 PM, Don Clugston wrote:
>>
>> I've converted my BigInt module from Tango to Phobos2. It's a great
>> test of the new operator overloading!
>> After 2.042 comes out, I'd like to add it to Phobos.
>
> Awesome! How do the operators hold?

They're looking pretty good. The code size for the operator overloading has so far shrunk to less than half what it used to be. More importantly, it's shown up some bugs in the existing code. Here's a sample:

    // BigInt op BigInt
    BigInt opBinary(string op, T)(T y)  if ( is(T: BigInt) )
    {
        BigInt x = this;
        return x.opOpAssign!( op ~ "=" )(y);
    }

    // Commutative operators
    BigInt opBinaryRight(string op, T)(T y)  if ( (op == "+" || op ==
"*" ) && ! is(T: BigInt) )
    {
        return opBinary!(op)(y);
    }


>
>> A couple of issues:
>> (1) We need somewhere in Phobos for implementation code (of which
>> there is a considerable amount for BigInt).
>>
>> I propose std.internal.math.XXX; for all math related modules. This
>> would keep everything tidy and hidden.
>> None of this will be user-visible.
>
> Sounds good.
>
>> (2) ?Syntax for conversion to string is undecided. Strawman:
>>
>> ?void toString(void delegate(const(char)[]) sink, string format);
>>
>> where format is currently limited to:
>>
>> d ? ?for decimal
>> x ? ?for lower case hex
>> X ? ?for upper case hex
>
> s or null for "whatever" for conformity.
>
>> but will be extended in the future. If format is "", defaults to decimal. Sink takes a const(char)[] so that BigInt can keep reusing the same buffer.
>>
>> Eventually, whatever is chosen will require some changes to std.format, but I'd just like to get a reasonable first cut for the initial release.
>
> That's fine; we need to look again at std.format anyway.
>
> Speaking of which - do we have good code for parsing and writing floating point numbers? I need it for unformat().

Not yet. To do floating point accurately, you need some BigInt functions... Someone (Fawzi I think) had made some good progress on it.

Don Clugston wrote:
> I've converted my BigInt module from Tango to Phobos2. It's a great
> test of the new operator overloading!
> 

Great!

> After 2.042 comes out, I'd like to add it to Phobos.
> 

Sure.

> A couple of issues:
> (1) We need somewhere in Phobos for implementation code (of which
> there is a considerable amount for BigInt).
>
> I propose std.internal.math.XXX; for all math related modules. This
> would keep everything tidy and hidden.
> None of this will be user-visible.
> 

How about a more general scheme? For internal implementation modules, just prefix an "internal" package to it, so we would have:

   internal.std.bigint
   internal.std.math

etc.

On 19 March 2010 04:46, Don Clugston <dclugston at googlemail.com> wrote:
> I've converted my BigInt module from Tango to Phobos2. It's a great
> test of the new operator overloading!
> After 2.042 comes out, I'd like to add it to Phobos.

OK, it's now in. There are still some obvious things wrong with it (not all of the formatting options are supported, for example), and the internal stuff doesn't take full advantage of D2 yet. Nonetheless it works.

The modules
	std\internal\math\biguintcore.d
	std\internal\math\biguintnoasm.d std\internal\math\biguintx86.d

will need to be added to the Linux and OSX makefiles.

I've done some timing tests to compare the new BigInt implementation
with the old one.
For the changelog:
--
Multiplication is now 5 times faster, division is 300 times faster,
and squaring is 10 times faster.
For large numbers  (~5000 machine words), the speedup is 5 times
larger than this.

============

On 24 March 2010 22:24, Don Clugston <dclugston at googlemail.com> wrote:
> On 19 March 2010 04:46, Don Clugston <dclugston at googlemail.com> wrote:
>> I've converted my BigInt module from Tango to Phobos2. It's a great
>> test of the new operator overloading!
>> After 2.042 comes out, I'd like to add it to Phobos.
>
> OK, it's now in. There are still some obvious things wrong with it (not all of the formatting options are supported, for example), and the internal stuff doesn't take full advantage of D2 yet. Nonetheless it works.
>
> The modules
> ? ? ? ?std\internal\math\biguintcore.d
> ? ? ? ?std\internal\math\biguintnoasm.d std\internal\math\biguintx86.d
>
> will need to be added to the Linux and OSX makefiles.
>

Wow. That's very impressive!

-Lars


Don Clugston wrote:
> I've done some timing tests to compare the new BigInt implementation
> with the old one.
> For the changelog:
> --
> Multiplication is now 5 times faster, division is 300 times faster,
> and squaring is 10 times faster.
> For large numbers  (~5000 machine words), the speedup is 5 times
> larger than this.
> 
> ============
> 
> On 24 March 2010 22:24, Don Clugston <dclugston at googlemail.com> wrote:
>> On 19 March 2010 04:46, Don Clugston <dclugston at googlemail.com> wrote:
>>> I've converted my BigInt module from Tango to Phobos2. It's a great
>>> test of the new operator overloading!
>>> After 2.042 comes out, I'd like to add it to Phobos.
>> OK, it's now in. There are still some obvious things wrong with it (not all of the formatting options are supported, for example), and the internal stuff doesn't take full advantage of D2 yet. Nonetheless it works.
>>
>> The modules
>>        std\internal\math\biguintcore.d
>>        std\internal\math\biguintnoasm.d std\internal\math\biguintx86.d
>>
>> will need to be added to the Linux and OSX makefiles.
>>
> _______________________________________________
> phobos mailing list
> phobos at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/phobos


-- 
Lars Tandle Kyllingstad
@: lars at kyllingen.net
#: 40233221
w: http://www.kyllingen.net

That may say a few things about the old implementation, but I'm sure it says a lot more about the new one!

Great work, Don!


Andrei

On 03/25/2010 08:28 AM, Don Clugston wrote:
> I've done some timing tests to compare the new BigInt implementation
> with the old one.
> For the changelog:
> --
> Multiplication is now 5 times faster, division is 300 times faster,
> and squaring is 10 times faster.
> For large numbers  (~5000 machine words), the speedup is 5 times
> larger than this.
>
> ============
>
> On 24 March 2010 22:24, Don Clugston<dclugston at googlemail.com>  wrote:
>> On 19 March 2010 04:46, Don Clugston<dclugston at googlemail.com>  wrote:
>>> I've converted my BigInt module from Tango to Phobos2. It's a great
>>> test of the new operator overloading!
>>> After 2.042 comes out, I'd like to add it to Phobos.
>>
>> OK, it's now in. There are still some obvious things wrong with it (not all of the formatting options are supported, for example), and the internal stuff doesn't take full advantage of D2 yet. Nonetheless it works.
>>
>> The modules
>>         std\internal\math\biguintcore.d
>>         std\internal\math\biguintnoasm.d std\internal\math\biguintx86.d
>>
>> will need to be added to the Linux and OSX makefiles.
>>
> _______________________________________________
> phobos mailing list
> phobos at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/phobos

How's it compare to gmp?

On 3/25/2010 6:28 AM, Don Clugston wrote:
> I've done some timing tests to compare the new BigInt implementation
> with the old one.
> For the changelog:
> --
> Multiplication is now 5 times faster, division is 300 times faster,
> and squaring is 10 times faster.
> For large numbers  (~5000 machine words), the speedup is 5 times
> larger than this.
> 
> ============
> 
> On 24 March 2010 22:24, Don Clugston <dclugston at googlemail.com> wrote:
>> On 19 March 2010 04:46, Don Clugston <dclugston at googlemail.com> wrote:
>>> I've converted my BigInt module from Tango to Phobos2. It's a great
>>> test of the new operator overloading!
>>> After 2.042 comes out, I'd like to add it to Phobos.
>>
>> OK, it's now in. There are still some obvious things wrong with it (not all of the formatting options are supported, for example), and the internal stuff doesn't take full advantage of D2 yet. Nonetheless it works.
>>
>> The modules
>>        std\internal\math\biguintcore.d
>>        std\internal\math\biguintnoasm.d std\internal\math\biguintx86.d
>>
>> will need to be added to the Linux and OSX makefiles.
>>
> _______________________________________________
> phobos mailing list
> phobos at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/phobos