need help with C project

[Marlene Stebbins]

My hobby project is a library of routines in C that do big integer
arithmetic. I've been working on it for several weeks and it now
consists of about 1200 lines of code. I've got addition, subraction and
multiplication working, but there is a problem with division. I think my
algorithm is OK; it's nothing fancy, just grade school long division. It
crashes with a seg fault on some inputs and produces the correct result
with others. Despite putting in a great deal of time trying to find this
bug, I've been unsuccessful.

I hate to come this far and then fail in the very last phase of the
project. I'm wondering if there might be an experienced C programmer out
there who would be willing to take a look at the code (its on my web
site). I know it's asking a lot and I have nothing to offer in return
except my gratitude.

If you are interested, please email me.

saltonpepper
at
shaw
dot
ca

Marlene Stebbins

 

[Thomas Matthews]

My hobby project is a library of routines in C that do big integer
arithmetic. I've been working on it for several weeks and it now
consists of about 1200 lines of code. I've got addition, subraction and
multiplication working, but there is a problem with division. I think my
algorithm is OK; it's nothing fancy, just grade school long division. It
crashes with a seg fault on some inputs and produces the correct result
with others. Despite putting in a great deal of time trying to find this
bug, I've been unsuccessful.

I hate to come this far and then fail in the very last phase of the
project. I'm wondering if there might be an experienced C programmer out
there who would be willing to take a look at the code (its on my web
site). I know it's asking a lot and I have nothing to offer in return
except my gratitude.

If you are interested, please email me.

saltonpepper
at
shaw
dot
ca

Marlene Stebbins

Check out some of the Big Number libraries, such as:
http://www.openssl.org/docs/crypto/bn.html#

You can download the source. It should give you some
guidance.


--
Thomas Matthews

C++ newsgroup welcome message:
http://www.slack.net/~shiva/welcome.txt
C++ Faq: http://www.parashift.com/c++-faq-lite
C Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.learn.c-c++ faq:
http://www.comeaucomputing.com/learn/faq/
Other sites:
http://www.josuttis.com -- C++ STL Library book
http://www.sgi.com/tech/stl -- Standard Template Library

 

[CBFalconer]

.... snip ...

I hate to come this far and then fail in the very last phase of the
project. I'm wondering if there might be an experienced C programmer
out there who would be willing to take a look at the code (its on my
web site). I know it's asking a lot and I have nothing to offer in
return except my gratitude.

Which URL is conspicuously missing from your post.

 

[Marlene Stebbins]

Marlene Stebbins wrote:

... snip ...



Which URL is conspicuously missing from your post.

Here 'tis:

http://members.shaw.ca/bystander/bignum.html

 

[Michael Mair]

Here 'tis:

http://members.shaw.ca/bystander/bignum.html

Um, it would have been nicer to get either links to the four
source files or a .zip archive containing all of them.

Apart from that: On which inputs does your routine fail?

I just looked over your code and found some problems but I
will not go through it without knowing the right inputs:

Your low-level functions are visible everywhere; writing, say
"static void abs_add (....)" effectively prevents users from
using routines which are only yours.

bignum.h:
You need not restrict yourself to ASCII or whatever, instead
of ZERO you can always write '0', instead of NINE you always
can write '9'. If you like your defines better, then at least
#define ZERO '0' and #define NINE '9'.
Your sign control can cause problems down the road, I would
rather use
enum {NEG=-1,POS=1};
or
enum {NEG=-1,NONE,POS};
This will also simplify sign calculation for your bigints
to a.sign*b.sign

bignum.c:
bigAlloc(): You can also use realloc()
int2big(): You multiply n with -1 without checking whether
n<-INT_MAX; for 2s complement machines, INT_MIN= -INT_MAX-1,
so you will run into undefined behaviour.
BTW: If you just malloc() a large enough string, you can
sprintf() n there and just call your ordinary str2big() (or
however it is called). After return, you free() the string
buffer.
big2int(): You do not check whether the return value of strtol()
makes sense but just cast it which can invoke UB.
I'd rather do the conversion by hand (checking against
INT_MAX (or INT_MAX/10)) or use strtof() and check against
INT_MAX.
bigCmp(): I would first evaluate the signs. As far as I have
understood, .size contains strlen(.num), so you do not need
the strlen() round here.
The test could also be (for sign in NEG, NONE, POS)
switch (a.sign*b.sign) {
case NEG:
return a.sign;
case NONE:
if (a.sign) return a.sign;
else return -b.sign;
case POS:
if (a.size > b.size) return a.sign;
else if (b.size > a.size) return -b.sign;
else return strcmp(a.number, b.number);
default:
assert(0);
return 0;
}
Note the default. You have no "default" in your tests.
mul_sign(), div_sign(): with (NEG,NONE,POS), this becomes
return dvd.sign*div.sign;
or the equivalent for multiplication.
slice(): Are you sure about the first test?
You fail to check lo<=hi.
ascii2str(): You are just duplicating the string; the name
is misleading.

Further down: The
zero:;
label needs no semicolon as it is no statement.
I would mark the label by writing it at the same indentation
level as the surrounding block or at the very beginning of
the line:
zero:
pprod.sign....

After that I stopped.


Cheers
Michael

 

[Marlene Stebbins]

Um, it would have been nicer to get either links to the four
source files or a .zip archive containing all of them.

Apart from that: On which inputs does your routine fail?

I just looked over your code and found some problems but I
will not go through it without knowing the right inputs:

When tested with the rudimentary driver at the bottom of the file,
division fails with a seg fault when the divisor (argv[2]) is relatively
large (more than 8-10 digits). The size of the dividend doesn't seem to
matter; that is, if the dividend is very large and the divisor is small,
the correct result is output. Thanks for the rest of your comments. Your
points are well taken. I know the code still has lots of rough edges.
There doesn't seem to be much point in fixing them unless I can get
division working.

Marlene

 

[Michael Mair]

Um, it would have been nicer to get either links to the four
source files or a .zip archive containing all of them.

Apart from that: On which inputs does your routine fail?

I just looked over your code and found some problems but I
will not go through it without knowing the right inputs:

When tested with the rudimentary driver at the bottom of the file,
division fails with a seg fault when the divisor (argv[2]) is relatively
large (more than 8-10 digits). The size of the dividend doesn't seem to
matter; that is, if the dividend is very large and the divisor is small,
the correct result is output. Thanks for the rest of your comments. Your
points are well taken. I know the code still has lots of rough edges.
There doesn't seem to be much point in fixing them unless I can get
division working.

Understandable... but misleading.

I think I have found the _reason_ for your error:

void strip_zeroes(char *s)
{
char *stripped;
int idx, jdx, zero_count, len;

zero_count = 0;
idx = 0;
len = strlen(s) + 1;

while(s[idx] == '0')
{
zero_count++;
idx++;
}
if((stripped = malloc((len-zero_count) * sizeof(*stripped)))==NULL)
{
fprintf(stderr, "malloc failed in strip_zeroes\n");
exit(EXIT_FAILURE);
}
for(idx = zero_count, jdx = 0; idx < len; idx++, jdx++)
{
stripped[jdx] = s[idx];
}
if((s = realloc(s, (len - zero_count) * sizeof(*s)))==NULL)

My debugger burped at this statement.
One thing: This is the completely _wrong_ way to handle realloc()
See below for the right way. If realloc() returns NULL, then your
buffer which s points to still exists at the address s.
By assigning NULL to s, you throw it away. However, this should
not cause a segmentation fault.

{
fprintf(stderr, "realloc failed in strip_zeroes()\n");
exit(EXIT_FAILURE);
}

strcpy(s, stripped);
free(stripped);
return;
}

However, it made me think about what you _want_ the function to
do. You pass a string and want to have _this_ string changed.
realloc() means that the address of the storage may change.
In order to bring that back into the pointer the value of which
we passed, we need the pointer's address:

void strip_zeroes(char **s)
{
char *tmp;
size_t zero_count, len;

len = strlen(*s) + 1;

zero_count = strspn(*s, "0");
assert(zero_count < len);
memmove(*s, *s+zero_count, len-zero_count);
if((tmp = realloc(*s, (len - zero_count) * sizeof *tmp))==NULL)
{
fprintf(stderr, "realloc failed in strip_zeroes()\n");
exit(EXIT_FAILURE);
}
*s = tmp;
return;
}

Now, you have to pass &mybignum.number (and change the prototype
in the header).
Of course, as this was not the reason why the program crashed,
the pointer s we got passed was probably invalid in the first
place! So, the task is to look for a similar logical error which
happened to the argument "difference" of the function abs_sub.

Your turn
Michael