Long Num speed

[fermineutron]

Barry Schwarz wrote:
Is there a reason you did not do the work in C directly (and avoid the
time spent in malloc and copying *Ans to *C)?

I do not work in C directly to allow the caller to use the same
argument for one of the multipliers as the result. Doing calculations
in C directly will screw up the math.

Where do you free Ans? You are causing repeated memory leaks.

OOPS, it did not copy over. but i did have it in the code.

 

[Ancient_Hacker]

I am doing 3 digits at the time

Good! Then the speedup will only be by a factor of 400,000 times.

I would approach it this way:

First go to using base 2. Shouldnt be hard, just change all your 10's
to 2's.
Then get the code going as well as before, only using base 2.

Then you can try stepping up the number of digits from 3 up to whatever
will fit in your datatype. Better stop a few bits short the first time
to avoid problems with the sign bit.

Then notice that all your divides and mod's by 2^digits can be replaced
by shifts and masks. Although a good compiler will do this for you.

So by using most of the datatype width, and removing all the divs and
mods, things should get super speedy.

 

[fermineutron]

First go to using base 2. Shouldnt be hard, just change all your 10's
to 2's.
Then get the code going as well as before, only using base 2.

Then you can try stepping up the number of digits from 3 up to whatever
will fit in your datatype. Better stop a few bits short the first time
to avoid problems with the sign bit.

Then notice that all your divides and mod's by 2^digits can be replaced
by shifts and masks. Although a good compiler will do this for you.

So by using most of the datatype width, and removing all the divs and
mods, things should get super speedy.

Hmm, i forgot about super speedy shifts, going to rework the code now.

I know there are better agorithms for computing factorial then straight
up multiplication, but it is the bignum arithemetic that i am mostly
curious about so factoriial calculations is just a driver/benchmark.

 

[Arthur J. O'Dwyer]

Good! Then the speedup will only be by a factor of 400,000 times.

I would approach it this way:

First go to using base 2. Shouldnt be hard, just change all your 10's
to 2's.
Then get the code going as well as before, only using base 2.

Then you can try stepping up the number of digits from 3 up to whatever
will fit in your datatype. Better stop a few bits short the first time
to avoid problems with the sign bit.

Then notice that all your divides and mod's by 2^digits can be replaced
by shifts and masks. Although a good compiler will do this for you.

So by using most of the datatype width, and removing all the divs and
mods, things should get super speedy.

Also, there are almost certainly faster ways to multiply than O(n^2).

However, when fermineutron goes to base 2^k, he will need to invest
some time (or Google searching) in a new "AEIfprintf" routine. This
shouldn't be a big deal --- his existing routine is totally brain-dead
and should be shot on sight --- but it might take a while to get all
the new bugs out, especially since he's working in an unfamiliar language.

Followups set to comp.programming, since this thread has lost any
connection to the C programming language.

-Arthur

 

[Keith Thompson]

Ancient_Hacker wrote: [...]

Then notice that all your divides and mod's by 2^digits can be replaced
by shifts and masks. Although a good compiler will do this for you.

Hmm, i forgot about super speedy shifts, going to rework the code now.

[...]

I predict that he will ignore the "Although a good compiler will do
this for you" statement, and just manually replace all his
multiplications and divisions by shift without first checking whether
it's necessary. (I could be wrong, of course.)

 

[Keith Thompson]

I do not work in C directly to allow the caller to use the same
argument for one of the multipliers as the result. Doing calculations
in C directly will screw up the math.

For those tuning in late, "C" is the name of a variable. I suggest
that, like "a", "C" is a really bad variable name.

 

[John Smith]

For a while now i have been "playing" with a little C program to
compute the factorial of large numbers.

What's the largest factorial you've been able to compute with
your program?

 

[fermineutron]

What's the largest factorial you've been able to compute with
your program?

with old version the larges one i did in real time is 150000

after i swiched to base 1024 i have not tried yet, still stuck on
printing function, i seem to be unable to come up with algoryth to go
from base "base" to base 10 in a long array
Standard aproach such as
NumInBase10=NumInBaseB*(B/10)^N
will not work since N can be several thousand easy.

 

[fermineutron]

Here is the function i have for printing to the screen an array encoded
integer, but it does not work, would someone please fix it. I dont
usually ask people to write code for me completely but i fried my brain
trying to figure this one out today. Dont know whats wrong with me
today, but i just seem to be unable to figure this one out today.

here is the code
=====================Start paste=====================
void AEIprintf(struct AEI *p) {
int fieldLength = (int)log10(base);
long fieldbase=pow(10,fieldLength);
char format[10];
size_t j = p->digits;
long dpf, dpf1;
sprintf(format, "%%0%dd", fieldLength);
dpf = 0;
dpf1 = (p->data[j] + dpf)/fieldbase;
dpf = (p->data[j] + dpf)%fieldbase;
printf("%*d", fieldLength, dpf1);
for (; j > 0; j--) {
dpf1 = (p->data[j] + dpf)/fieldbase;
dpf = (p->data[j] + dpf)%fieldbase;
printf(format, dpf1);
}
return;
}

=====================End Paste=====================

 

[fermineutron]

can such a printing operation be done at all? I think there may be a
way if to 1st reencode the array into a decimal base and then print,
but honestly speaking i have no idea.

 

[CBFalconer]

with old version the larges one i did in real time is 150000

after i swiched to base 1024 i have not tried yet, still stuck on
printing function, i seem to be unable to come up with algoryth to go
from base "base" to base 10 in a long array
Standard aproach such as
NumInBase10=NumInBaseB*(B/10)^N
will not work since N can be several thousand easy.

I suspect this may be beyond you, but take a look at dubldabl.

<http://cbfalconer.home.att.net/download>

 

[Keith Thompson]

can such a printing operation be done at all? I think there may be a
way if to 1st reencode the array into a decimal base and then print,
but honestly speaking i have no idea.

You've been here long enough to understand the importance of
providing context in a followup, haven't you?

 

[fermineutron]

I suspect this may be beyond you, but take a look at dubldabl.

<http://cbfalconer.home.att.net/download>

Correct me if i am wrong but, I dont think that this will work, because
in my case i have array of binary coded numbers but each element in the
array corresponds to a base not equal to 2^bits per field.

That is, my data looks like this
2^70 2^60 2^50 2^40 2^30 2^20 2^10
2^0
-----------------------------------------------------------------------------------------------------
| 0-1023 | 0-1023 | 0-1023 | 0-1023 | 0-1023 | 0-1023 | 0-1023 | 0-1023
|
-----------------------------------------------------------------------------------------------------
|4 bytes |4 bytes |4 bytes |4 bytes |4 bytes |4 bytes |4 bytes |4 bytes
|
-----------------------------------------------------------------------------------------------------

theoretically the range of each field can be half the bits in the
field. This has to be so to allow for an integer datatype to be able to
hold a maximum product of 2 fields.

so if i were to setup something like:

--------------------------------------------------------------------------------------------
| ASCII Memory | Binary Memory
|
--------------------------------------------------------------------------------------------
and shift from right 2 left using algorythm you pointed me to,
shouldn't the unused 2 left bytes of each element in binary memeory
screw up the ASII memory?

Before you posted the post to which i am replying here, i tried to
print the numbers into char array, as follows:

base = 1024
===================Start Code=======================
void AEIprintf(struct AEI *p) {
int fieldLength = (int)log10(base);
long fieldbase=pow(10,fieldLength+1), N=0, carry=0, tbl=0;
char format[10], *buffer;

long j = p->digits;
long i=0;
buffer=malloc(sizeof(struct AEI)*10);
if(buffer!=NULL){
while(i<j){
N=(carry+p->data+p->data[i+1]*base)%fieldbase;
carry=(carry+p->data+p->data[i+1]*base)/fieldbase;
tbl+=sprintf(buffer+tbl,"%ld",N);
i++;
}

printf("\nprinting buffer %d\n", strlen(buffer));
printf("\n%s\n",buffer);
}else{
printf("\nCant Allocate memory\n");
}
return;
}

===================End Code========================

but because the base has integer value in it 1024 the contribution to
units decemal field of resulting number in base 10 will come from all
elements of array in base 1024 i would have to find (p->data[N])*1024^N
which is impossible to do since N is several thousand may be even 10s
of thousands.

It is also the case that even if i were to requre the field size be
half of the bits of the maximun int type, hence allowing to use all
bits in the field to store data, to not wory about separate sign field,
i casted the array as signed, i know its wastefull, but i have not
thought of the way to handle it oherwise, i guess it can be done adding
a sign field into the structure.

what would you seggest about printing function?

The more I am thinking about the more it seems that i should redo it
using unsigned ints using full field width, but i have not yet gathereg
my bravory to do that.

 

[Arthur J. O'Dwyer]

I suspect this may be beyond you, but take a look at dubldabl.

<http://cbfalconer.home.att.net/download>

Just for kicks, I implemented double-dabble from scratch based on
your description and added a description and C implementation to
Wikipedia:
http://en.wikipedia.org/wiki/Double_dabble

Any comments on the implementation from the nitpickers?

(Other than "check calloc and realloc for NULL", that is. I
consciously decided to omit the error-checking in a "reference"
implementation, because it isn't relevant to the algorithm itself
and would only distract readers who wanted to translate the algorithm
to some other language. Remember this is meant to strike a harmonious
mean between "real code" and "teaching code".)

Suggestions of a better test driver are particularly solicited.

Also, CBFalconer, do you know where the name "double-dabble" came
from originally, and how long it's been around? Curiously, some
online references use the name "double-dabble" to refer to an
"algorithm" that's little more than an observation about positional
number systems --- see the page history of "Double dabble" for that
ridiculousness.

Thanks,
-Arthur

 

[fermineutron]

Just for kicks, I implemented double-dabble from scratch based on
your description and added a description and C implementation to
Wikipedia:
http://en.wikipedia.org/wiki/Double_dabble

Any comments on the implementation from the nitpickers?

(Other than "check calloc and realloc for NULL", that is. I
consciously decided to omit the error-checking in a "reference"
implementation, because it isn't relevant to the algorithm itself
and would only distract readers who wanted to translate the algorithm
to some other language. Remember this is meant to strike a harmonious
mean between "real code" and "teaching code".)

Suggestions of a better test driver are particularly solicited.

Also, CBFalconer, do you know where the name "double-dabble" came
from originally, and how long it's been around? Curiously, some
online references use the name "double-dabble" to refer to an
"algorithm" that's little more than an observation about positional
number systems --- see the page history of "Double dabble" for that
ridiculousness.

Thanks,
-Arthur

Thanks Arthur,
Your code works great, i was able to use it with no problems. Without
YOUR help i would not have gotten it done. Good news is that the
multiplication algo that i changed earlier works correctly and your
code is what made it possible for me to check that. Thanks again.

 

[fermineutron]

Arthur,
Is there any chance you could add to the wikipedia the C code for
reverse transformation of long integers?

That is, given a null terminated string containing characters 0-9 how
would i transfer it to array of integers in base 2^16 or 2^32?

Thanks ahead.