C: Arbitrary-precision can't correctly subtract

[jsmwoolf]

I finally got a basic Arbitrary-precision system up and running only on addition. I'm now doing one in subtract and the problem is that when doing the "subtracting one from the top number next to you on the left and adding ten to the top digit that is below in value of the bottom digit"(I honestly can't describe it very well, but I think you can interoperate that), it doesn't change the digit that was borrowed from even though I'm using pointers. It does, however, properly add ten if the top digit is too small.

I posted my code for subtraction:

void subtractNumbers(int space,int number[], int number2[], int *toStore)
{
    int goUp=0;
    int *p;
    int *q;
    int *r;
    r=toStore;
    for(int digit = (space-1); digit >= 0; digit--)
    {
        p = &number[digit]; //Grabs the digit
        q = &number2[digit]; //Grabs the digit
        while(*p < *q) //If the bottom digit is higher than the top digit
           {
                goUp++; //Checks one digit ahead
               p = &number[digit+goUp]; //Goes to the next digit
               if(*p!=0) //If the next digit isn't a zero
               {
                   *p-=1; //It'll then subtract one
                   while(goUp>0) //While there are possibly more digits
                   {
                       goUp--; //We'll go down one digit
                       p = &number[digit+goUp];
                       if((*p==0) && (goUp > 0)) //If the digit is zero and there are more than one digit to carry over
                       {
                           *p=9;
                       }
                       if(goUp==0) //Otherwise, add ten.
                       {
                            *p+=10;
                           break;
                       }
                   }
                   break;
               }
           }
        goUp=0;
        *r = *p - *q; //Then subtract the number the number
        *(toStore + digit) = *r; //Now store the value.
    }
}

What's wrong?

[gnasher729]

Originally Posted by jsmwoolf

I finally got a basic Arbitrary-precision system up and running only on addition. I'm now doing one in subtract and the problem is that when doing the "subtracting one from the top number next to you on the left and adding ten to the top digit that is below in value of the bottom digit"(I honestly can't describe it very well, but I think you can interoperate that), it doesn't change the digit that was borrowed from even though I'm using pointers. It does, however, properly add ten if the top digit is too small.

I posted my code for subtraction:

void subtractNumbers(int space,int number[], int number2[], int *toStore)
{
    int goUp=0;
    int *p;
    int *q;
    int *r;
    r=toStore;
    for(int digit = (space-1); digit >= 0; digit--)
    {
        p = &number[digit]; //Grabs the digit
        q = &number2[digit]; //Grabs the digit
        while(*p < *q) //If the bottom digit is higher than the top digit
           {
                goUp++; //Checks one digit ahead
               p = &number[digit+goUp]; //Goes to the next digit
               if(*p!=0) //If the next digit isn't a zero
               {
                   *p-=1; //It'll then subtract one
                   while(goUp>0) //While there are possibly more digits
                   {
                       goUp--; //We'll go down one digit
                       p = &number[digit+goUp];
                       if((*p==0) && (goUp > 0)) //If the digit is zero and there are more than one digit to carry over
                       {
                           *p=9;
                       }
                       if(goUp==0) //Otherwise, add ten.
                       {
                            *p+=10;
                           break;
                       }
                   }
                   break;
               }
           }
        goUp=0;
        *r = *p - *q; //Then subtract the number the number
        *(toStore + digit) = *r; //Now store the value.
    }
}

What's wrong?

I don't understand the code, and I wouldn't even try to understand it. It is just much, much, much too complicated. I've got six lines of code to do this, and one of them is a variable initialisation, and one just a closing brace. Write down a few subtractions by hand and see how you do it by hand. (I tend to write a little zero or one besides every number at the bottom, except that I'm old and brave enough to do it just mentally, not with a pen. )

And square brackets make array code just so much more readable.

[jiminaus]

Doing decimal math on a computer like we do on paper is really not the most efficient way to do this. The typically way to do it is with multibyte binary. You might want to study how we use add with carry and subtract with carry assembly instructions to do this at the assembler level. Once you understand these principles, it's easy to do it in C.

The exact details are different from one CPU to another, but here's an example explaination. http://www.pic-projects.net/index.ph...etic&Itemid=57

[ghellquist]

Well,
half the point of writing this kind of stuff is to learn how debug programs and rethink the way things are done.

I must admit that I find the code very difficult to follow and hence difficult to comment on. One thing that looks wrong on a quick look is one of the last lines where you do *r = *p -*q -- do check what r points at.

Other things that I cannot really understand are things like:
- if the two numbers has different number of "numbers", ie 1234 - 123 ?
- if the result turns negative, ie 123 - 1234 ?
- if one of the numbers is negative to start with ?

Personally, I would scrap all of the code and restart from the beginning. Start with how you represent different size numbers and how you represent negative numbers.

// gunnar

----------

This line looks wrong to me, not really understanding things.
p = &number[digit+goUp]; //Goes to the next digit

Should it not be [digit - goUp] as digit starts out pointing to the last in the array ?
//Gunnar

[jsmwoolf]

Doing decimal math on a computer like we do on paper is really not the most efficient way to do this. The typically way to do it is with multibyte binary. You might want to study how we use add with carry and subtract with carry assembly instructions to do this at the assembler level. Once you understand these principles, it's easy to do it in C.

Where's the flaw in what I'm doing? Speed? Writing? Readability? All three if not more? I honestly don't know any assembly, so grasping the concept will take a while.

*r = *p -*q

My intention was to store the value of *r using the difference of *p and *q so that I can take it and store into the array. However, I think now it's redundant to have that section.

EDIT: Finally solved subtraction, but my question is how come you can't multiply pointers?

[kakusan]

EDIT: Finally solved subtraction, but my question is how come you can't multiply pointers?

My question is: why would you want to? The only two operations you can perform on a pair of pointers is to compare them or subtract them, with the further restriction that they must point to members of the same array. What meaning would multiplication have?

A pointer has the value of an address in memory. Using street addresses as an analogy, you could for example subtract your address from a neighbor's to get some idea of how far apart your houses are on the same street. However if you live on Maple and I live across town on Davis, such a comparison quickly loses meaning.

Now try multiplying your address with your neighbor's address. Could you perhaps get a value equal to another address on your street? Perhaps in rare cases. More likely than not you'll get a number that couldn't possibly be in the range of addresses on your street.

There are many restrictions on pointer arithmetic. But they are not restrictions for restrictions' sake if you think about what each individual operation means.

[jsmwoolf]

My question is: why would you want to? The only two operations you can perform on a pair of pointers is to compare them or subtract them, with the further restriction that they must point to members of the same array. What meaning would multiplication have?

I was actually referring to grabbing values from an array using pointers, not manipulating addresses. For example:
I store a value in array[1] which has a value of 1.

array[1]=1;

I then use a pointer *p and grab the address of array[1] with *p.

int *p;
p = &array[1];

Then repeating the process again with another index in the array and another pointer.

int *q;
array[2]=2;
p = &array[2];

Then declare a third pointer and then using the values of what's being held in the first two pointers and adding,subtracting, multiply,etc. them and store them in the third.

int *r;
array[3]=0;
r=&array[3];
*r=*p+*q;

Then put the value in the third index of the array using *r.

array[3]=*r;
//or
int n =3;
*(array+n) = *r;

That's why I asked why you can't multiply pointers. Of course, I could have missed the entire point.

[subsonix]

You can absolutely multiply dereferenced pointers as long as the destination points somewhere.

Edit: Having quickly looked at the first post I have to ask why you use pointers at all? It's not necessary, and will only obfuscate what you are trying to achieve and add potential for unnoticed errors.

[jsmwoolf]

Well, now I can't remove them for subtract because it's dependent on those pointers and if I remove them, I'll get the wrong result. For addition, I removed all reference of pointers and therefore the result is left unchanged.

I was using pointers because I was grabbing digits one by one in an array that was being passed into a function.

[subsonix]

Originally Posted by jsmwoolf

I was using pointers because I was grabbing digits one by one in an array that was being passed into a function.

Sure but you could just as well have used a temporary variable. But never mind you do as you see fit, hope you get it working.

Edit: actually *p, *q, *r all point to the very parameters you pass to the function, you might as well use them directly.

[Sydde]

Originally Posted by subsonix

Sure but you could just as well have used a temporary variable. But never mind you do as you see fit, hope you get it working.

Edit: actually *p, *q, *r all point to the very parameters you pass to the function, you might as well use them directly.

You are suggesting using array syntax on pointers? Where, say, *p is equivalent to p[0] ? But that would be too simple. The arguments could be passed as pointers and just indexed directly.

[subsonix]

Originally Posted by Sydde

You are suggesting using array syntax on pointers? Where, say, *p is equivalent to p[0] ? But that would be too simple. The arguments could be passed as pointers and just indexed directly.

What do you mean too simple? It's not simple to the point of not working, to quote Einstein: "everything should be made as simple as possible, but not simpler"

The arguments are passed as pointers, whether they are used as arrays or not does not matter. My point was that there is not reason to have an extra set of pointers inside the function. But the question came up about multiplying pointers and while the following works, it's just ugly.

*a = *b * *c;

[gnasher729]

Originally Posted by jsmwoolf

Where's the flaw in what I'm doing? Speed? Writing? Readability? All three if not more? I honestly don't know any assembly, so grasping the concept will take a while.

The x86 processors have two instructions for adding:

"add" takes two numbers and adds their sum.
"adc" = "add with carry" takes two numbers and the carry bit, which is either 0 or 1, and adds them. If the result is too large, it produces the partial result and sets the carry flag to 1, otherwise it sets the carry flag to 0.

The x86 processors also have two instructions for subtracting:

"sub" takes two numbers and calculates the difference.
"sbb" = "subtract with borrow" takes two numbers and the "borrow" bit, which is either 0 or 1. It calculates the first number minus the second number minus the borrow bit. If the result is >= 0, it then sets the borrow bit to 0, otherwise it sets the borrow bit to 1.

Now an example: 612 - 129.
Start with borrow bit = 0. 2 - 9 - borrow 0 = -7, add 10 makes 3, borrow = 1.
1 - 2 - borrow 1 = -2, add 10 makes 8, borrow = 1.
6 minus 1 minus borrow 1 = 4, makes 4, borrow = 0.

Result = 612 - 129 = 483.

[jiminaus]

Originally Posted by jsmwoolf

Where's the flaw in what I'm doing? Speed? Writing? Readability? All three if not more?

Speed and memory. You'll need many more bits to store a number in unpacked decimal than in binary. You'll need many more CPU cycles to calculate in decimal than in binary (assuming your target architecture doesn't directly support decimal arithmetic).

Originally Posted by jsmwoolf

I honestly don't know any assembly, so grasping the concept will take a while.

You don't need to know an assembly language, you just need to be able to understand how it works. The link I posted steps through the assembly line by line with plenty of explanation.

[SidBala]

What you need is basically a ripple-carry adder, but in software. This will allow you to perform addition and subtraction for arbitrary length numbers byte-by-byte.

If you do that then subtraction is as simple as making one of the numbers negative by 2's complement and feeding that into the adder.

[chown33]

Originally Posted by SidBala

If you do that then subtraction is as simple as making one of the numbers negative by 2's complement and feeding that into the adder.

I compliment your mention of 2's complement, and wish to complement it by mentioning 9's-complement and 10's-complement, which are complementary to the Method of complements.

I think it's also worth linking to Subtraction algorithms. I don't know how the OP learned to do subtraction in elementary school, but I would bet that the algorithm coded wasn't it.

[jsmwoolf]

Originally Posted by jiminaus

Speed and memory. You'll need many more bits to store a number in unpacked decimal than in binary. You'll need many more CPU cycles to calculate in decimal than in binary (assuming your target architecture doesn't directly support decimal arithmetic).



You don't need to know an assembly language, you just need to be able to understand how it works. The link I posted steps through the assembly line by line with plenty of explanation.

The format tends to be a command, the type of byte that your dealing with, and something else I don't know how it works

movf A0 W

As a question, what does W and F mean in the example? I was thinking of write and final, but I bet I'm not correct. Is Ax and Rx,where x = 0,1,2,etc., a type of byte? Is byte A and R defined or do you have to know what those specifically do?

       movf    A0,W
        addwf   R0,F
        movf    A1,W
        btfsc   STATUS,C
        incfsz  A1,W
        addwf   R1,F

Can the top code do any length of numbers or only three/four?

Also, if I do understand the example, do I need to go to the low-level of C and actually use binary(<<(left binary shift), >>(right binary shift), ~(switch or something), &(and), |(or), ^(XOR))?

I think it's also worth linking to Subtraction algorithms. I don't know how the OP learned to do subtraction in elementary school, but I would bet that the algorithm coded wasn't it.

You questioning my math skills? It's simple for a human to subtract ,as long as they still remember how and was able to grasp it, and letting the computer subtract for you using predefined basic variables(int, char, double, long, etc.). However, trying to code a computer to do arithmetic math like a human is very complex whether it is to overcome limitations of exactness or just coding such to learn on how it works as you must set your conditions on when certain things happen. Otherwise, you'll get the wrong results. Besides, I was good at math when I was in elementary school anyway so I learned it very quickly.

EDIT: MOVF moves the data into another bit and resets the value to zero in the template bit(the Ax), ADDWF then takes two of the argument and then stores the final value into the second argument, INCFSZ increments the value in loops. But what's btfsc? Is it your "If..." statement?

[gnasher729]

Originally Posted by jsmwoolf

You questioning my math skills? It's simple for a human to subtract ,as long as they still remember how and was able to grasp it, and letting the computer subtract for you using predefined basic variables(int, char, double, long, etc.). However, trying to code a computer to do arithmetic math like a human is very complex whether it is to overcome limitations of exactness or just coding such to learn on how it works as you must set your conditions on when certain things happen. Otherwise, you'll get the wrong results.

If you read my very first reply: No, it is _not_ difficult. _You_ made it difficult. Read the description of the "subtract with borrow" instruction that I posted. For subtracting numbers with four components, the code is: borrow = 0, subtract with borrow digit 0 from digit 0, subtract with borrow digit 1 from digit 1, subtract with borrow digit 2 from digit 2, subtract with borrow digit 3 from digit 3.

My code was three lines to implement the loop and initialize "borrow", and three lines for implementing the "subtract with borrow" operation. Code for adding would very much look the same.

[chown33]

Originally Posted by jsmwoolf

You questioning my math skills? It's simple for a human to subtract ,as long as they still remember how and was able to grasp it, and letting the computer subtract for you using predefined basic variables(int, char, double, long, etc.). However, trying to code a computer to do arithmetic math like a human is very complex whether it is to overcome limitations of exactness or just coding such to learn on how it works as you must set your conditions on when certain things happen. Otherwise, you'll get the wrong results. Besides, I was good at math when I was in elementary school anyway so I learned it very quickly.

Did you read the subtraction algorithms I linked to?

Did you read the description of "Method of complements" I linked to?

Neither of them are difficult or complex.

If I'm questioning anything, it's your design skills. You seem to frequently leap to conclusions, overcomplicate things, and not do basic research, such as searching for Subtraction Algorithms. Instead of doing the basics, and getting a firm grounding in them, you seem to start coding whatever you first think of, even if you don't know the basics. This pattern has occurred over and over, with almost every problem you've posted to the list. In short, the lack of basic research and basic design is the main cause of your coding difficulties.

And again, I would like to know what subtraction algorithm you learned in elementary school. I will bet it wasn't the algorithm in the code you wrote. If you can't describe the algorithm you learned, I suggest spending some time to do so. The ability to dissect procedures and express algorithms is a fundamental skill to all of programming. Equally, the ability to read and understand algorithms, then code them correctly, is another fundamental skill.

I would also like to see your code that results from implementing the basic grade-school algorithm described in the link already provided. If you do it, you should find that it's essentially subtract-with-borrow.

Many manual arithmetic algorithms have been refined over centuries or even millenia. If you understand the algorithm, you will often find that coding it produces simple, effective code. There's a reason for this: manual calculation is expensive, so anything that can improve it effectively will be a benefit.

[jsmwoolf]

And again, I would like to know what subtraction algorithm you learned in elementary school. I will bet it wasn't the algorithm in the code you wrote. If you can't describe the algorithm you learned, I suggest spending some time to do so. The ability to dissect procedures and express algorithms is a fundamental skill to all of programming. Equally, the ability to read and understand algorithms, then code them correctly, is another fundamental skill.

I think that was the algorithm that I learned in grade school. Now that I actually took a real close look at the method of complements, you take the complement of the subtrahend, for example, 873 and 281 which 281 is the subtrahend number and complement that to 782 but take one away which yields 781. Then add 873 and 781 which makes 1654. Then subtract the (y + nines' complement of y) + 1 or (y + tens' complement of y), which in our case is 1000 which gets us 654. Then add one and you get 655.

In binary sense, you would have to use ~ in order to get the complement. However, would you have to grab a decimal complement by converting to binary and use ~?

However, will I need to still use an array because I need to do a certain number of times in the problems that I'm doing? If I don't use an array, then how can I still follow arbitrary precision without one and manipulate data?

[chown33]

Originally Posted by jsmwoolf

I think that was the algorithm that I learned in grade school.

Then it shouldn't be hard to translate it into an English description of the procedure, which should be comprehensible to a 2nd-grader. I encourage you to try doing this, as gnasher729 did with the subtract-with-borrow algorithm. To make it easy, use exactly the same operands as gnasher729 did in his example.

Now that I actually took a real close look at the method of complements, you take the complement of the subtrahend, for example, 873 and 281 which 281 is the subtrahend number and complement that to 782 but take one away which yields 781.

The 9's-complement of 281 is not 782.

The operand in the Wikipedia example is 218. Quoting the article: "The nines' complement of y (218) is 781." It's not 782. 782 would be the 10's complement of 218. Because the 10's complement of any number is the 9's-complement + 1. For comparison, look up 2's-complement and 1's-complement in binary (base-2).

I think you need to reread the wikipedia article more carefully. Much more carefully.

However, will I need to still use an array because I need to do a certain number of times in the problems that I'm doing? If I don't use an array, then how can I still follow arbitrary precision without one and manipulate data?

Do you understand what a pointer is? Do you understand the close relationship between arrays and pointers in C? Do you know that an array parameter passed to a function is really a pointer? Do you know why it's really a pointer?

[gnasher729]

Originally Posted by jsmwoolf

However, will I need to still use an array because I need to do a certain number of times in the problems that I'm doing? If I don't use an array, then how can I still follow arbitrary precision without one and manipulate data?

The first thing you'd need to do is to define a data structure. How would you represent the number 123,456? Or the number 123,456,789? How do you represent the number -123,456? Or don't you represent negative numbers at all? You can be more or less flexible depending on your goals, but you need to make some decision.

Next you define what exactly a function like subtractNumbers is to do, and what its limitations are. Is it capable of subtracting 123 - 124? If yes, is it capable of subtracting -1 - 124? Or -1 - (-124)?

[jsmwoolf]

The operand in the Wikipedia example is 218. Quoting the article: "The nines' complement of y (218) is 781." It's not 782. 782 would be the 10's complement of 218. Because the 10's complement of any number is the 9's-complement + 1. For comparison, look up 2's-complement and 1's-complement in binary (base-2).

The 9's-complement of 281 is not 782.

That was a typo. Besides, isn't finding the 9's complement finding the 10's complement and subtracting by 1? According to the example, it looks a lot like it compared to a 9's and 10's complement.

Do you understand what a pointer is?

A pointer is a type of variable that stores an address of another variable.

Do you understand the close relationship between arrays and pointers in C?

It technically allows the pointer to access one section of an array and make changes to it. However, I find it more useful when looking at strings rather than numbers.

Do you know that an array parameter passed to a function is really a pointer?

It's handled by the compiler, I believe.

Do you know why it's really a pointer?

Practically, no I don't.

The first thing you'd need to do is to define a data structure.

I was originally using an array, but since you said that you can write a subtraction algorithm in six lines, I might have to scrap the idea and use something else.

EDIT: Using the method of complement, I was able to shorten the subtract algorithm and avoid using all of those comparisons. Yet, I still didn't shorten it to six lines.

[chown33]

Originally Posted by jsmwoolf

That was a typo. Besides, isn't finding the 9's complement finding the 10's complement and subtracting by 1? According to the example, it looks a lot like it compared to a 9's and 10's complement.

The example used 9's-complement. So why would you calculate the 10's-complement?

Consider the description you gave earlier (with typos fixed):

Now that I actually took a real close look at the method of complements, you take the complement of the subtrahend, for example, 873 and 218 which 218 is the subtrahend number and complement that to 782 but take one away which yields 781. Then add 873 and 781 which makes 1654. Then subtract the (y + nines' complement of y) + 1 or (y + tens' complement of y), which in our case is 1000 which gets us 654. Then add one and you get 655.

Where you say "complement that to 782", you're taking the 10's-complement. But why? The wikipedia example uses 9's-complement.

You then take one away to get 781, the 9's-complement. But why didn't you just calculate the 9's-complement directly, like the example shows? It's as if you read a simple example and can't simply follow it as given. You add complexity that simply isn't there in the original.


If you're going to do the subtraction using 10's-complement, then you can eliminate the "take one away" after the first complementation, and the "add one" at the end, and calculate directly with the 10's-complement:
873 + 782 = 1655
1655 - 1000 = 655
Basic algebra should prove how that works.

[gnasher729]

Originally Posted by jsmwoolf

EDIT: Using the method of complement, I was able to shorten the subtract algorithm and avoid using all of those comparisons. Yet, I still didn't shorten it to six lines.

int borrow = 0;
for (int i = space - 1; i >= 0; --i) {
    int difference = number [i] - number2 [i] - borrow; 
    toStore [i] = (difference >= 0 ? difference : difference + 10);
    borrow = (difference >= 0 ? 0 : 1);
}