Do we need to determine the lesser of two numbers before subtracting?

Question

I'm writing a computer program which represents integers as linked lists because the integers may be very large such that they won't fit the usual int type.

In my linked list representation the list start with the least significant digit and ends with the most significant one. For example, $123$ is represented as 3->2->1 ($3$ is the first node in the list).

So I'm writing a subtract function which subtract digits one by one, like in elementary school. It looks like that in order to use the basic school subtraction arithmetic I need to first determine the bigger number because:

1. When calculating $123-99$ the steps are: $13-9 = 4, 11-9=2$ so the result is $24$.

2. But to calculate $23-99$ the logic is different and I can't do $13-9, 1-9$ which would be $-84$ but really is $76$.

So I'm wondering if I really have to know in advance which number is the bigger one. Of course this means that I'd have to add another pass over both linked lists which would decrease the efficiency of the algorithm.

Answer 1

You don't have to but what you'd have to do instead would be more complicated.

$23 - 99$ who start with $13 -9 = 4$ and borrow.

$2-1 = 1$ and $1-9 = 2$ and borrow... but now there is nothing to left of $23$ to borrow from.

So you go into a negative number subroutine. You answer of $[24]$ represents a number less than zero. The $4$ must be increased by $6$ to get to zero. $6+4 = 10$ and you carry to get $2+1 = 3$. Then three must be increased by $7$ to get to $0$. You have reached $0$ (so you "drop" what you were carrying) and $[24] = -76$.

Basically if $10^{k-1} \le xy < 10^k$ then $[xy] = 10^k - xy$.

....

I'd be easier just to program in a check the larger routine.

====

Or you can put off carrying to the end.

$123 - 99$ would be $3-9 = -6$

$2-9 = -7$

$1-0 = 1$ so you end up with $1(-7)(-6)$

To convert this to a "real" number you must determine if it is bigger or less than $0$. That's simply a matter of seeing if the leftmost non-zero term is positive or negative. It is $1$ postive. This is a positive number.

to convert you borrow 10 from the left: $1(-7)(-6)\mapsto 1(-8)(10-6)=1(-8)4\mapsto 0(10-8)4=024 = 24$

But $456 - 492$ would be $6-2 =4$

$5 - 9 = -4$

$4-4 = 0$

So we end up with $0(-4)4$

We check leftmost non-zero term. It is $-4$ it is negative. So this will be a negative number. We switch the signs of every term $0(-4)(4) = -[04(-4)]$ and we cconvert by borrowing:

$-[04(-4)]\mapsto -[03(10-4)] = -[036] = -36$.

That actually might be the easiest.

Answer 2

Your $-84$ is really $(-8)(+4)$ in that the four in the ones place is positive. When we write a number with a minus sign in front we mean that all the digits are negative. Your $(-8)(+4)$ would normally be written $-76$, which is the correct answer. You can just do your subtraction normally digit by digit with the digits representing positive quantities. Then if the most significant digit is negative you need to turn everything negative by borrowing from the most significant digit. If you subtract $13792-26317$ you get $(-2)(+7475)$ which becomes $-12525$

Answer 3

I have myself once implemented the $4$ operations for large reals represented as strings, I found it simpler to deal with signs separately.

Also for multiplication it is simpler to multiply by the lower number, so you will need the comparison function at some point.

Have a look for instance at the subtraction wrapper:

https://bpaste.net/show/12a67e8ec170

I first assign a number from $0$ to $7$ depending on the signs $++,+-,-+,--$ and whether $|x|<|y|$ or the opposite.

Then I call the basic function that deals with positive integers and $y\ge x$ for the operation $y-x$.

Of course it is not mandatory to proceed like this, but it will simplify the implementation of the basic function since it has not to deal with particular cases.