Large numbers in C

[creeps]

Yes, it's yet another thread about implementing three basic operations (addition, subtraction and multiplication) on abnormally large numbers (> 100 digits).

I've stored each digit inside an array of int s, as the following piece of code illustrates

while((ch = getchar()) != EOL)
    a[len_a++] = ch - CHR;

Now, when it comes to adding them, I add the (len_number - k)th digits of both numbers, compute their reminder and their quotient, and store the reminder on the kth place of the sum array. The following piece of code works nicely for, say, 132 and 32, but when I try adding 1248 and 2, the result 1950, instead of 1350. I think I'm doing some illegal work on the arrays (at some point, I have something like b[1 - 3] ), but I've been struggling for a lot of time and I still can't figure things out, so any help would be highly appreciated.

for(i = 1; i <= len_a || i <= len_b; ++i) {

    aux = (a[len_a - i] + b[len_b - i] + qtt);
    rem = aux % 10;
    sum[i - 1] = rem;
    ++len_sum;
    qtt = aux / 10;
}

And here's the big picture

#include <stdio.h>

#define NR_DIG 100
#define EOL '\n'
#define CHR '0'

int main(void) {

    unsigned short a[NR_DIG], b[NR_DIG], sum[NR_DIG + 1];
    int ch, len_a = 0, len_b = 0, len_sum = 0, rem, qtt = 0, i, aux;

    printf("a: ");
    while((ch = getchar()) != EOL)
        a[len_a++] = ch - CHR; /* ch - CHR = input - its character part */

    printf("b: ");
    while((ch = getchar()) != EOL)
        b[len_b++] = ch - CHR;

    for(i = 1; i <= len_a || i <= len_b; ++i) {

        aux = (a[len_a - i] + b[len_b - i] + qtt);
        rem = aux % 10;
        sum[i - 1] = rem;
        ++len_sum;
        qtt = aux / 10;
    }

    printf("a + b: ");
    for(i = len_sum - 1; i >= 0; --i)
        printf("%hu", sum[i]);
    printf("\n");

    return 0;
}

[creeps]

Hmm... apparently, changing the unsigned short declaraction to int did the trick. Also, if after the loop ends the quotient is greater than 0, it should be added to the array.

When someone explains why unsigned short does not work, I'll mark the thread as solved. Thanks in advance!

Also, here's the final piece of code, should anyone be interested

#include <stdio.h>

#define NR_DIG 100
#define EOL (int) '\n'
#define CHR (int) '0'

int main(void) {

    int a[NR_DIG], b[NR_DIG], sum[NR_DIG + 1], 
        a_len = 0, b_len = 0, sum_len = 0, aux, qtt = 0, ch, i;

    printf("a: ");
    while((ch = getchar()) != EOL)
        a[a_len++] = ch - CHR;

    printf("b: ");
    while((ch = getchar()) != EOL)
        b[b_len++] = ch - CHR;

    for(i = 1; i <= a_len || i <= b_len; ++i) {
        aux = (a[a_len - i] + b[b_len - i] + qtt);
        sum[i - 1] = aux % 10;
        ++sum_len;
        qtt = aux / 10;
    }

    if(qtt > 0)
        sum[i - 1] = qtt;

    for(i = sum_len; i >= 0; --i)
        printf("%d", sum[i]);
    printf("\n");

    return 0;
}

[Adak]

It's easier if you do your addition and subtraction on these long arrays, just as you were taught to do them, in school.

Some people like to flip the numbers around, but I like just using char's, and starting with the highest element and decrementing the loop counter, as I go.

The main thing is to keep it *simple*, so you always know exactly where your carry is, if you have a carry or not, etc. Simple is fast, (enough), and simple is bug free.

[creeps]

It's easier if you do your addition and subtraction on these long arrays, just as you were taught to do them, in school.

Hmm... I thought this is what I was doing. Or are you talking about some other manner? Basically, I go to the last digits of both, add them to the previous quotient (initially 0), store the remainder of their addition into the sum array, and store their quotient in another variable for later use (next iteration).

Some people like to flip the numbers around

I've found this to be unnecessary, and taking some added time to implement.

but I like just using char's

Ok, but if I used char s, and later I wanted to, say, divide the number by two, wouldn't it require some extra work? I wanted to do the conversion on the spot, so to speak.

[Adak]

There's no real wrong way to do it, if you get accurate results. The run-time is just not a big deal, and is irrelevant if the result isn't accurate.

It's a package deal on the design - absolutely. Shorts might be as small (in range), as a char, depending on your system. That may cause overflow, all depending on your algorithm.

[Shift-Stop]

I just now compiled and ran the
"here's the final piece of code, should anyone be interested " code (above)
with the values

A:1248
B: 2
Results = "2089877600-8-130"

and again,
A:2
B: 1248
Results = "4479020590" ( btw, an INT, not a string)

so...
Am I missing something, or is there still something Very broken about the solution ?

signed - In Doubt

Shift-Stop

[creeps]

The code above was not really the finished version, I kept working on it after posting. A big source of errors might be given by the character set on one's computer. If the characters 0 to 9 are not continuous, 2 + 4 might translate into something as bad as 32947 - 20492180.

[Shift-Stop]

Creeps,
I may be wrong here- ( I thought I was wrong once, but I was mistaken)
Two questions;
(1)
"for(i = 1; i <= a_len || i <= b_len; ++i) { "

I don't think I've EVER seen a line like that before.
Are you trying to take the largest of the two?
If so, then I would determine the largest of the two -First-,
before entering into the loop.

on an HP-2000 the machine source code - I believe) in an OR situation
takes the RIGHT-SIDE value- In this case the code would evaluate
the
i <= b_len;

You may want to WATCH this see that it is working according to your
design algorithm.

(2) And perhaps a little more important,
Lets say A: = 12345678
and B: = 00000876

It "looks" to me as
A: 12345678
B: 876
---------
....99945678

Meaning, that it looks like you are going through your array elements
from A[0->100] added to B[0->100]
ie
A[0]+ B[0] plus A[1]+ B[1} plus A[2]+B[2]= sum
1 + 8 ... ................. 2 + 7 ........... 3 + 6

HOWEVER !
Rather than adding the values from RIGHT to LEFT
I thunk you are adding them from LEFT to RIGHT !

Just a thought.

Shift-Stop

ps What is the purpose of the subtracting the int "o" 'CHR' in lines 15,19 ???