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