Numeric access to char[]

nobody nobody at mailinator.com
Fri Aug 25 11:39:23 PDT 2006


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.







More information about the Digitalmars-d-learn mailing list