On Thu, 24 Aug 2006 03:53:28 +0200, Peter Thomassen <info@peter-thomassen.de> wrote:
> Regan Heath schrieb am Mittwoch, 23. August 2006 02:06:
>> Depends what exactly you're trying to do, perhaps this:
>>
>> import std.stdio;
>>
>> void main()
>> {
>> char[] c = "azAZ";
>> int val;
>> val = (cast(int*)c.ptr)[0..1][0];
>> //DEBUG
>> //writef("(%02d)%08b",c[0],c[0]);
>> //writef(",(%02d)%08b",c[1],c[1]);
>> //writef(",(%02d)%08b",c[2],c[2]);
>> //writefln(",(%02d)%08b",c[3],c[3]);
>> writefln("%032b",val);
>> val >>= 1;
>> writefln("%032b",val);
>> }
>
> Thanks, this is what im looking for! But I don't understand this line:
>> val = (cast(int*)c.ptr)[0..1][0];
>
> What does [0..1][0] mean?

Ahh.. to understand the line we need to know that D allows us to slice pointers and the result is an array, lets break the line into steps.

Step1: cast(int*)c.ptr, this tells it to pretend the pointer to the char[] data is an int pointer.

Step2: [0..1], this requests a slice (AKA array) of the data referenced by the (now) int pointer. The result is an int[], in this case with only 1 item, a single int.

Step3: [0] returns the first item (only item) in the int slice (array), an int.

Because we're only after a single int, we can actually do it in a much simpler fashion, this:

  val = *(cast(int*)c.ptr);

If you have a large block of char[] data to process you might use:

char[] c = "the quick brown fox jumps over the lazy dog";
foreach(int val; cast(int[])c)
{
  ..etc..
}

or similar.

>> p.s. nobody got the ascii values backward ('A' is 65, 'a' is 97)
>> it's nobody's fault really.. nobody is to blame..
>>
>> "nobody" I love the nick.. have you read the "Deverry" novels by
>> "Katherine Kerr"?
>> http://www.math.ttu.edu/~kesinger/deverry/kerr.biblio.html
>
> The oldest example of such pun I know of is Polyphemus who is fooled by this
> name in Homer's Odyssey which I read parts of in my Latin lessons at school
> (albeit the original is Greek). --> http://en.wikipedia.org/wiki/Polyphemus

Cool.

Regan

Regan Heath schrieb am Donnerstag, 24. August 2006 04:21:
>> Thanks, this is what im looking for! But I don't understand this line:
>>> val = (cast(int*)c.ptr)[0..1][0];
>>
>> What does [0..1][0] mean?
> 
> Ahh.. to understand the line we need to know that D allows us to slice pointers and the result is an array, lets break the line into steps.
> 
> Step1: cast(int*)c.ptr, this tells it to pretend the pointer to the char[]
> data is an int pointer.
> 
> Step2: [0..1], this requests a slice (AKA array) of the data referenced by
> the (now) int pointer. The result is an int[], in this case with only 1
> item, a single int.
> 
> Step3: [0] returns the first item (only item) in the int slice (array), an
> int.

Okay, nearly understood. But doesn't [0..1] produce two items, namely [0] and [1]?

Peter

On Thu, 24 Aug 2006 04:33:53 +0200, Peter Thomassen wrote:

> 
> Okay, nearly understood. But doesn't [0..1] produce two items, namely [0] and [1]?

The semantics of a slice specification is that the slice starts with the element indexed by the first index and extends to all the elements up to, but not including, the second index. Thus [0..1] means a slice containing element[0] only, and [4..7] means element[4], element[5], and element[6] is included in the slice, but not element[7]. To get all the elements except the last element we can use [0..$-1]



-- 
Derek
(skype: derek.j.parnell)
Melbourne, Australia
"Down with mediocrity!"
24/08/2006 1:05:56 PM

Derek Parnell schrieb am Donnerstag, 24. August 2006 05:06:
>> Okay, nearly understood. But doesn't [0..1] produce two items, namely [0] and [1]?
> 
> The semantics of a slice specification is that the slice starts with the element indexed by the first index and extends to all the elements up to, but not including, the second index. Thus [0..1] means a slice containing element[0] only, and [4..7] means element[4], element[5], and element[6] is included in the slice, but not element[7]. To get all the elements except the last element we can use [0..$-1]

Thanks!
Peter

nobody wrote:
> Chad J wrote:
> 
>> nobody wrote:
>> ....
>>
>>>
>>> So you will have to do it manually. I would like to suggest that if you can pad the char[] to ensure its .length % 8 == 0 then you can cast it to a ulong and your shifting will be faster.
>>
>>
>> Sure about ulong?  In my spare time I made my own minimal Bignum implementation.  I'm not sure about shifts, but for addition with carrying it was faster to use size_t (uint in this case) rather than ulong.  I wonder if maybe the compiler could optimize it better if it didn't have to emulate 64 bit integers.  Or my benchmark was borked.
> 
> 
> I certainly could be wrong but I would be quite surprised. I would be interested to see what tests you ran that suggest addition with carry was faster.

This BigNum I made is very incomplete and probably slow.  Changing the size of it's digits shouldn't do anything besides just that, though.

I have attached 2 .d files, BigNum.d is the implementation, main.d is the benchmark.  I compiled it with dmd -O -inline -release.  At the top of BigNum.d there is an alias that I use to switch between size_t and ulong variables used in the computation.

Here are my results.  See main.d for details of the setup.

Microseconds to complete 1000000 additions using size_t:
786779
776801
793653
783896
787937
789150

Microseconds to complete 1000000 additions using ulong:
866767
860499
866921
865791
860874
858154

Chad J wrote:
> nobody wrote:
>> Chad J wrote:
>>
>>> nobody wrote:
>>> ....
>>>
>>>>
>>>> So you will have to do it manually. I would like to suggest that if you can pad the char[] to ensure its .length % 8 == 0 then you can cast it to a ulong and your shifting will be faster.
>>>
>>>
>>> Sure about ulong?  In my spare time I made my own minimal Bignum implementation.  I'm not sure about shifts, but for addition with carrying it was faster to use size_t (uint in this case) rather than ulong.  I wonder if maybe the compiler could optimize it better if it didn't have to emulate 64 bit integers.  Or my benchmark was borked.
>>
>>
>> I certainly could be wrong but I would be quite surprised. I would be interested to see what tests you ran that suggest addition with carry was faster.
> 
> This BigNum I made is very incomplete and probably slow.  Changing the size of it's digits shouldn't do anything besides just that, though.
> 
> I have attached 2 .d files, BigNum.d is the implementation, main.d is the benchmark.  I compiled it with dmd -O -inline -release.  At the top of BigNum.d there is an alias that I use to switch between size_t and ulong variables used in the computation.
> 
> Here are my results.  See main.d for details of the setup.
> 
> Microseconds to complete 1000000 additions using size_t:
> 786779
> 776801
> 793653
> 783896
> 787937
> 789150
> 
> Microseconds to complete 1000000 additions using ulong:
> 866767
> 860499
> 866921
> 865791
> 860874
> 858154

Thanks for taking the time to post this. It will be a little while before I can sit down and play with the code you sent so I thought I would give you my first impression. It looks like you have tested the time it takes to add a 20 "digit" number to an 18 "digit" number:

  BigDigit[20] test1;
  BigDigit[18] test2;

You define these numbers as one of the two:

  alias size_t BigDigit; // for optimal performance
  alias ulong BigDigit;

I think the easiest way to suggest the problem with your test is in finding how many bytes we are adding in each case:

  20 * 4 = 80 bytes
  20 * 8 = 160 bytes

What your results actually seem to be saying is that treating char[160] as a ulong takes slightly longer than treating char[80] as a uint. I am still fairly convinced that if you test again with an equal number of bytes you should find that the ulong case will be faster. If you have a chance to run the test before me I would be interested to hear the results.

nobody wrote:
> Chad J wrote:
> 
>> nobody wrote:
>>
>>> Chad J wrote:
>>>
>>>> nobody wrote:
>>>> ....
>>>>
>>>>>
>>>>> So you will have to do it manually. I would like to suggest that if you can pad the char[] to ensure its .length % 8 == 0 then you can cast it to a ulong and your shifting will be faster.
>>>>
>>>>
>>>>
>>>> Sure about ulong?  In my spare time I made my own minimal Bignum implementation.  I'm not sure about shifts, but for addition with carrying it was faster to use size_t (uint in this case) rather than ulong.  I wonder if maybe the compiler could optimize it better if it didn't have to emulate 64 bit integers.  Or my benchmark was borked.
>>>
>>>
>>>
>>> I certainly could be wrong but I would be quite surprised. I would be interested to see what tests you ran that suggest addition with carry was faster.
>>
>>
>> This BigNum I made is very incomplete and probably slow.  Changing the size of it's digits shouldn't do anything besides just that, though.
>>
>> I have attached 2 .d files, BigNum.d is the implementation, main.d is the benchmark.  I compiled it with dmd -O -inline -release.  At the top of BigNum.d there is an alias that I use to switch between size_t and ulong variables used in the computation.
>>
>> Here are my results.  See main.d for details of the setup.
>>
>> Microseconds to complete 1000000 additions using size_t:
>> 786779
>> 776801
>> 793653
>> 783896
>> 787937
>> 789150
>>
>> Microseconds to complete 1000000 additions using ulong:
>> 866767
>> 860499
>> 866921
>> 865791
>> 860874
>> 858154
> 
> 
> Thanks for taking the time to post this. It will be a little while before I can sit down and play with the code you sent so I thought I would give you my first impression. It looks like you have tested the time it takes to add a 20 "digit" number to an 18 "digit" number:
> 
>   BigDigit[20] test1;
>   BigDigit[18] test2;
> 
> You define these numbers as one of the two:
> 
>   alias size_t BigDigit; // for optimal performance
>   alias ulong BigDigit;
> 
> I think the easiest way to suggest the problem with your test is in finding how many bytes we are adding in each case:
> 
>   20 * 4 = 80 bytes
>   20 * 8 = 160 bytes
> 
> What your results actually seem to be saying is that treating char[160] as a ulong takes slightly longer than treating char[80] as a uint. I am still fairly convinced that if you test again with an equal number of bytes you should find that the ulong case will be faster. If you have a chance to run the test before me I would be interested to hear the results.
> 

Ah, good catch.  That does turn the results around, now the ulong leads slightly instead of the other way around.

Changed
BigDigit[20] test1;
BigDigit[18] test2;

to

ulong[20] test1;
ulong[18] test2;


w/ size_t:
880821
905326
871996
895222
897846

w/ ulong:
849123
848298
849372
852560
895887

Another thing with the test... random numbers.  It probably won't matter much, but when using 64 bit digits, only the lo 32 bits get filled by phobo's rand() function, which means no carrying, ever.  Also, it might be interesting to do extreme cases like where the numbers always have all of the bits set, which forces carrying all the time.

I also noticed that I broke the unittest when I tried to free up any memory the carrying might have wasted, so I've fixed that and here's the new version.  (This really didn't have an effect on speed, just correctness)

On Fri, 25 Aug 2006, Chad J wrote:

> nobody wrote:
> > Chad J wrote:
> > 
> > > nobody wrote:
> > > 
> > > > Chad J wrote:
> > > > 
> > > > > nobody wrote:
> > > > > ....
> > > > > 
> > > > > > 
> > > > > > So you will have to do it manually. I would like to suggest that if you can pad the char[] to ensure its .length % 8 == 0 then you can cast it to a ulong and your shifting will be faster.
> > > > > 
> > > > > 
> > > > > 
> > > > > Sure about ulong?  In my spare time I made my own minimal Bignum implementation.  I'm not sure about shifts, but for addition with carrying it was faster to use size_t (uint in this case) rather than ulong.  I wonder if maybe the compiler could optimize it better if it didn't have to emulate 64 bit integers.  Or my benchmark was borked.
> > > > 
> > > > 
> > > > 
> > > > I certainly could be wrong but I would be quite surprised. I would be interested to see what tests you ran that suggest addition with carry was faster.
> > > 
> > > 
> > > This BigNum I made is very incomplete and probably slow.  Changing the size of it's digits shouldn't do anything besides just that, though.
> > > 
> > > I have attached 2 .d files, BigNum.d is the implementation, main.d is the benchmark.  I compiled it with dmd -O -inline -release.  At the top of BigNum.d there is an alias that I use to switch between size_t and ulong variables used in the computation.
> > > 
> > > Here are my results.  See main.d for details of the setup.
> > > 
> > > Microseconds to complete 1000000 additions using size_t:
> > > 786779
> > > 776801
> > > 793653
> > > 783896
> > > 787937
> > > 789150
> > > 
> > > Microseconds to complete 1000000 additions using ulong:
> > > 866767
> > > 860499
> > > 866921
> > > 865791
> > > 860874
> > > 858154
> > 
> > 
> > Thanks for taking the time to post this. It will be a little while before I can sit down and play with the code you sent so I thought I would give you my first impression. It looks like you have tested the time it takes to add a 20 "digit" number to an 18 "digit" number:
> > 
> >   BigDigit[20] test1;
> >   BigDigit[18] test2;
> > 
> > You define these numbers as one of the two:
> > 
> >   alias size_t BigDigit; // for optimal performance
> >   alias ulong BigDigit;
> > 
> > I think the easiest way to suggest the problem with your test is in finding how many bytes we are adding in each case:
> > 
> >   20 * 4 = 80 bytes
> >   20 * 8 = 160 bytes
> > 
> > What your results actually seem to be saying is that treating char[160] as a ulong takes slightly longer than treating char[80] as a uint. I am still fairly convinced that if you test again with an equal number of bytes you should find that the ulong case will be faster. If you have a chance to run the test before me I would be interested to hear the results.
> > 
> 
> Ah, good catch.  That does turn the results around, now the ulong leads slightly instead of the other way around.
> 
> Changed
> BigDigit[20] test1;
> BigDigit[18] test2;
> 
> to
> 
> ulong[20] test1;
> ulong[18] test2;
> 
> 
> w/ size_t:
> 880821
> 905326
> 871996
> 895222
> 897846
> 
> w/ ulong:
> 849123
> 848298
> 849372
> 852560
> 895887
> 
> Another thing with the test... random numbers.  It probably won't matter much, but when using 64 bit digits, only the lo 32 bits get filled by phobo's rand() function, which means no carrying, ever.  Also, it might be interesting to do extreme cases like where the numbers always have all of the bits set, which forces carrying all the time.
> 
> I also noticed that I broke the unittest when I tried to free up any memory the carrying might have wasted, so I've fixed that and here's the new version. (This really didn't have an effect on speed, just correctness)

Have any of you looked at the GMP library?  It's a highly optimized large number library.  It supports both large integers and large floats. Providing a D wrapper on top of it would be the direction I'd head in for this sort of use case.

Later,
Brad

Brad Roberts wrote:
> 
> Have any of you looked at the GMP library?  It's a highly optimized large number library.  It supports both large integers and large floats.  Providing a D wrapper on top of it would be the direction I'd head in for this sort of use case.
> 
> Later,
> Brad

Hey thanks for that info.  I didn't know that existed.

I probably won't be writing any wrapper though, as the thing I wrote here was just for fun.  Maybe I will if I ever seriously need a bignum library though.

On Fri, 25 Aug 2006 16:19:29 -0700, Chad J <gamerChad@_spamIsBad_gmail.com> wrote:

> Brad Roberts wrote:
>>  Have any of you looked at the GMP library?  It's a highly optimized large number library.  It supports both large integers and large floats.  Providing a D wrapper on top of it would be the direction I'd head in for this sort of use case.
>>  Later,
>> Brad
>
> Hey thanks for that info.  I didn't know that existed.
>
> I probably won't be writing any wrapper though, as the thing I wrote here was just for fun.  Maybe I will if I ever seriously need a bignum library though.


There's no need to make another one. :)

A GMP wrapper was written long ago by Ben Hinkle:

http://home.comcast.net/~benhinkle/gmp-d/

-JJR