Subtraction In Review

Thread Starter

MrAl

Joined Jun 17, 2014
8,548
I may have to edit this a few times due to the format needed to show this example or
perhaps add a pic to show the examples.

This is maybe something we dont think about too much and is more of a curiosity.
In the following examples, i am subracting the lower number from the upper number although
not showing the minus sign. I do show the 'line' under the lower number that we sometime
put there just to keep things a little neater and so the result is just under that line.
The line is simply made with dashes for illustration:
-------

Ok, so starting with this first example:
009578
001119
---------
008459

Here we can start with the 8 and subtract 9, and doing so means we have to borrow 1 from the 7,
and so the result first digit on the far left is 9. The second is 6-1 because we borrowed from
the 7 reducting it to 6, and of course 6-1 is 5. Next we do 5-1=4 and 9-1=8 as shown, and just
fill in the two zeros in keeping with the form of the two numbers.
Thus we have completed the subtraction of 9578-1119=8459 and we are done with that example.


Now the next example isnt too much different:
1009578
1001119
----------
0008459

Here we started with the 8-9 and the borrow again, and so on and so forth, and when we get to the
two zeros we write them down like we did before. Finally we get to the far left digits 1 and 1, and
subtract them and get zero, and then write that down. We thus did the subtraction as before just
with three more digits.


Ok now for the final example, we do the following:
1009578
2001119
----------
_008459

We first subtract 8-9 as before and the borrow again and so on and so forth, and we get so far the
result shown below the line except we did not do the far left digits yet.
The question is, what do we do now?

I know there are other ways of doing this, but can you figure out a way to get the right result
in total using the procedure above except for that last far left digit pair and perhaps introduce
a second algorithm that corrects the result?
Not allowed here is to swap the numbers first cause we know already that works, this is a question
about doing it a different way.
Perhaps this is a good example of non communtative.
 

MrChips

Joined Oct 2, 2009
24,609
I am no math expert but I think the problem is you do not have a definition of a negative value.

If you reverse the numbers so that you subtract the smaller value from the larger value,
2001119 - 1009578 = 0991541
So the proper answer ought to be -0991541

As @BobTPH suggests you need to do 10's complement arithmetic.

First example:
+009578
-001119
---------
+008459

becomes:
+009578
+998881
---------
+008459

Last example:
+1009578
-2001119

becomes:
+1009578
+7998881
---------
+9008459

Take 10's complement
-0991541 which is the correct answer.
 

BobTPH

Joined Jun 5, 2013
4,032
The obvious answer to the original question is that you don’t subtract a larger number
a smaller one. You reverse them and then put a minus sign in front if the answer. This is called sign magnitude form. It requires you to make multiple decisions based on the signs and relative magnitudes to do an addition or subtraction.

Complement form gets rid if all these decisions, it simply does the addition, and the signs take care if themselves. To subtract, you first complement the number, then add. In hardware, a 2’s complement subtraction is done by taking the complement of each bit in the number you are subtracting snd forcing a carry into the lowest order bit, which makes the hardware only slightly more complex than that needed to do addition.

Bob
 

Thread Starter

MrAl

Joined Jun 17, 2014
8,548
The obvious answer to the original question is that you don’t subtract a larger number
a smaller one. You reverse them and then put a minus sign in front if the answer. This is called sign magnitude form. It requires you to make multiple decisions based on the signs and relative magnitudes to do an addition or subtraction.

Complement form gets rid if all these decisions, it simply does the addition, and the signs take care if themselves. To subtract, you first complement the number, then add. In hardware, a 2’s complement subtraction is done by taking the complement of each bit in the number you are subtracting snd forcing a carry into the lowest order bit, which makes the hardware only slightly more complex than that needed to do addition.

Bob
Yes, but i said in the first post that swapping numbers was not allowed and that was said specifically to eliminate solutions that involve swapping the numbers such as when the second number is largewr than the first.

As you mentioned and MrChips mentioned, 2's or 10's complement is another way to do it. I used to use 2's when i did straight up assembler but havnt had to do that in many years now.

But now it is interesting to see if there is a way to modify the ORIGINAL algorithm given in the first post, using that starter where we get part of the number. After that i wonder if there is a way to work it out from there.
 

Thread Starter

MrAl

Joined Jun 17, 2014
8,548
I am no math expert but I think the problem is you do not have a definition of a negative value.

If you reverse the numbers so that you subtract the smaller value from the larger value,
2001119 - 1009578 = 0991541
So the proper answer ought to be -0991541

As @BobTPH suggests you need to do 10's complement arithmetic.

First example:
+009578
-001119
---------
+008459

becomes:
+009578
+998881
---------
+008459

Last example:
+1009578
-2001119

becomes:
+1009578
+7998881
---------
+9008459

Take 10's complement
-0991541 which is the correct answer.
Yeah 10's complement would do it i guess.

Now i will repeat when i said in the previous post about the original algorithm...

But now it is interesting to see if there is a way to modify the ORIGINAL algorithm given in the first post, using that starter where we get part of the number. After that i wonder if there is a way to work it out from there.
I didnt actually try this yet was just thinking about if there is a way to do it because the original algorithm becomes useless unless we can swap. Probably isnt too hard to figure out.
 

Deleted member 115935

Joined Dec 31, 1969
0
Yeah 10's complement would do it i guess.

Now i will repeat when i said in the previous post about the original algorithm...

But now it is interesting to see if there is a way to modify the ORIGINAL algorithm given in the first post, using that starter where we get part of the number. After that i wonder if there is a way to work it out from there.
I didnt actually try this yet was just thinking about if there is a way to do it because the original algorithm becomes useless unless we can swap. Probably isnt too hard to figure out.
Can I just check, your trying to come up with a new routine to subtract two binary numbers ?
that sounds great,

first thing you would have to do I would suggest, is to define what the number series is your using,

i.e. is 101 in your base 5 in base 10
or is it -3 in base 10 ?
or what ?

without the numbering convention you are using, the 1 and 0 mean nothing,
 

Thread Starter

MrAl

Joined Jun 17, 2014
8,548
Can I just check, your trying to come up with a new routine to subtract two binary numbers ?
that sounds great,

first thing you would have to do I would suggest, is to define what the number series is your using,

i.e. is 101 in your base 5 in base 10
or is it -3 in base 10 ?
or what ?

without the numbering convention you are using, the 1 and 0 mean nothing,
Thanks for the reply.

Well no, i am not trying to work in any base system except maybe decimal, it is really just the algorithm we learned i think in grammar school except i am looking at subtracting a larger number from a smaller number.
Maybe this isnt that hard to do though but that was the real goal.

Example 1:
42-31=?
subtract 2-1=1 rightmost digit,
subtract 4-3=1 leftmost digit,
so the results is 11 or illustrated with brackets [1][1] (no different except the brackets)

Example 2:
41-43=?
subtracting 1-3 we borrow 10 from the first 4 so we get 11-3=8
the first 4 was reduced by 1 so it is now 3-4=-1
so now the result with brackets is
[-1][8]

Now how to modify this to get the right result, and whatever we do has to work for all problems like this.

One try might be to interpret the -1 as -10 because it is in the 10's weighted place, then add 8 which gives us -2 which is the right result. I havent actually tried this yet with other problems. But this would also mean we need an algorithm for adding a negative number to a positive number, which might defeat the purpose.
 

MrChips

Joined Oct 2, 2009
24,609
How about this?
If you end with a "borrow" this is indicative that the result is a negative number.
Therefore you have to use 10's complement.

Last example:
+1009578
-2001119
----------
[-1]9008459

10's complement:
-0991541
 

Deleted member 115935

Joined Dec 31, 1969
0
Thanks for the reply.

Well no, i am not trying to work in any base system except maybe decimal, it is really just the algorithm we learned i think in grammar school except i am looking at subtracting a larger number from a smaller number.
Maybe this isnt that hard to do though but that was the real goal.

Example 1:
42-31=?
subtract 2-1=1 rightmost digit,
subtract 4-3=1 leftmost digit,
so the results is 11 or illustrated with brackets [1][1] (no different except the brackets)

Example 2:
41-43=?
subtracting 1-3 we borrow 10 from the first 4 so we get 11-3=8
the first 4 was reduced by 1 so it is now 3-4=-1
so now the result with brackets is
[-1][8]

Now how to modify this to get the right result, and whatever we do has to work for all problems like this.

One try might be to interpret the -1 as -10 because it is in the 10's weighted place, then add 8 which gives us -2 which is the right result. I havent actually tried this yet with other problems. But this would also mean we need an algorithm for adding a negative number to a positive number, which might defeat the purpose.
If yo udo not define what your numbers mean, then you can have no algorithum, i.e. your 43, is that positive or negative number, what base is each place holder, it could be hex , base 10 , base 27 for all we knwo, and how are you planing to represent negative numbers,

Only once you have defined what your numbers mean, can you define a system,

else it says as much as pink - red = apple, ,
 

BobTPH

Joined Jun 5, 2013
4,032
If yo udo not define what your numbers mean, then you can have no algorithum, i.e. your 43, is that positive or negative number
Exactly. The TS algorithm only takes positive integers as input. If the subtracted number is larger, there is no solution within that domain. You must start with an algorithm that handles both positive and negative numbers.

Bob
 

Deleted member 115935

Joined Dec 31, 1969
0
Exactly. The TS algorithm only takes positive integers as input. If the subtracted number is larger, there is no solution within that domain. You must start with an algorithm that handles both positive and negative numbers.

Bob
I would use the word number system,
not algorithm, but yes the algorithm for the number system needs to be able to cope with-ve numbers if you have a subtraction that does not only include +ve numbers.
 

Thread Starter

MrAl

Joined Jun 17, 2014
8,548
Yes 10's complement seems to be the answer.

There seems to be no other good way to do this except maybe to cheat a little...

I was thinking along these lines:
[1][2][3]-[2][1][2]
[-1][1][1]
change signs:
[1][-1][-1]
which then represents:
100-10-1=89
change signs again:
-89
and that is correct.

But, if we are allowed to change signs then why not just do that:
123-212=?
change signs:
-123+212=?
which is the same as:
212-123=89
then change signs again:
-89
and that is correct.
So this sort of isnt swapping but we'd have to have an algorithm that can add positive and negative numbers.
 

MrChips

Joined Oct 2, 2009
24,609
I think that you are on the right track.

Last example:
1009578 - 2001119 = -0991541

1009578 = 1000000 + 000000 + 000000 + 9000 + 500 + 70 + 8
2001119 = 2000000 + 000000 + 000000 + 1000 + 100 + 10 + 9

Subtraction = (-1000000) + 000000 + 000000 + 8000 + 400 + 60 + (-1)

If the MSD is negative, multiply result with (-1)
Result = (1000000) + (-000000) + (-000000) + (-8000) + (-400) + (-60) + (1)

= 1000000 - 8459
= 991541
then append the negative sign.
 

Deleted member 115935

Joined Dec 31, 1969
0
Yes 10's complement seems to be the answer.

There seems to be no other good way to do this except maybe to cheat a little...

I was thinking along these lines:
[1][2][3]-[2][1][2]
[-1][1][1]
change signs:
[1][-1][-1]
which then represents:
100-10-1=89
change signs again:
-89
and that is correct.

But, if we are allowed to change signs then why not just do that:
123-212=?
change signs:
-123+212=?
which is the same as:
212-123=89
then change signs again:
-89
and that is correct.
So this sort of isnt swapping but we'd have to have an algorithm that can add positive and negative numbers.

that works,

The algorithm is ,
subtract smallest form largest,
and twiddle sign depending which order the largest / smallest is in the question.

might be good for humans,

but for machines, you would have to do a compare before hand, to work out which is bigger than the other,

which is typically implemented by a subtraction ( as machines are good at subtraction ) and check for -ve answer flag.
 

Thread Starter

MrAl

Joined Jun 17, 2014
8,548
Some good ideas came up here thanks for that.

Next up is division, and this is a bit harder to do but all i am looking for is an algorithm that isnt too hard to implement. The assumption is that we already have add, subtract, and multiply, of signed floating point numbers although with many digits like 100, 500, 1000 perhaps. I had implemented a library like this several years ago and even as far bask as 1990-ish but thought i would revisit this after we discussed the subtraction.

The division algorithm i had used in the past was something like where you find a function that provides a zero when the variable of interest equals the reciprocal of the number you input. So a reduction to a reciprocal algorithm is good enough as a following multiplication leads directly to the entire division.
So if we have a number like '5' and we want 1/5 which is 0.2, that's good enough.
The algorithm i think i used in the past was something like:
x[n+1]=x*(2-N*x)
and when N=5 we get a '1' in the second part when x=1/5 or 0.2 so the next x is 1/5 or 0.2 .
It turns out however that this has some starting problems. We have to 'guess' the first value for x, and if we choose wrong the solution diverges. So perhaps there is a better algorithm out there?
I was thinking of maybe a 'hunt and peck' type algorithm but that comes out somewhat long. The one above gets better and better with each iteration, in fact i think it gets double the digits with each iteration which is pretty good i think. If i could find something like that it would be really nice.
Maybe we could allow the use of regular floating point to give us the first guess, then convert that to the longer internal form of the numbers.
But really a better algorithm would be nicer.
 
Last edited:

MrChips

Joined Oct 2, 2009
24,609
In all of the above discussion are you asking for computer algorithms or procedures to be performed manually by humans?
 

Thread Starter

MrAl

Joined Jun 17, 2014
8,548
In all of the above discussion are you asking for computer algorithms or procedures to be performed manually by humans?
Well for the subtraction it was really to see how a human could do it, but for the division (or really just the reciprocal) it would be for a computer algorithm using floating point with a large number of digits.
 

MrChips

Joined Oct 2, 2009
24,609
The way humans do arithmetic is somewhat different from the computer algorithm.
Computers do addition and subtraction in the same way. Similarly, multiplication and division algorithms are similar. Hence we should start with multiplication.

Humans don't do floating point arithmetic. They do fixed point arithmetic.

On a computer, floating point representation consists of three parts, sign, exponent, and mantissa.

1624618492224.png

To multiply two FP values we add the exponent and multiply the mantissa.

For division, we subtract the exponent and divide the mantissa.

Reference: https://en.wikibooks.org/wiki/Microprocessor_Design/FPU
 

Thread Starter

MrAl

Joined Jun 17, 2014
8,548
The way humans do arithmetic is somewhat different from the computer algorithm.
Computers do addition and subtraction in the same way. Similarly, multiplication and division algorithms are similar. Hence we should start with multiplication.

Humans don't do floating point arithmetic. They do fixed point arithmetic.

On a computer, floating point representation consists of three parts, sign, exponent, and mantissa.

View attachment 242116

To multiply two FP values we add the exponent and multiply the mantissa.

For division, we subtract the exponent and divide the mantissa.

Reference: https://en.wikibooks.org/wiki/Microprocessor_Design/FPU
Yes, so now what i was looking for next is a computer algorithm that could be done in say the C language.
The division part i was looking for would be for the mantissa, although that mantissa could have 200 digits for example. I gave an example of one such way to do this but it would be nice to look at other methods too.
 
Top