DevX Home Today's Headlines   Articles Archive   Tip Bank   Forums

# Thread: What's wrong with the C++ compiler ?

1. ## What's wrong with the C++ compiler ?

Hey;

Do u know the divison algorithm ?
It's used to give us the quotient, reminder, and make divisons ..
And it must be the one used in all compilers to solve normal division problems.

Ok in the algorithm the reminder (r) must be greater than or equal zero satisfy :
0 =< r < |n| , right ?

it's easy to make this division algorithm and to find it in too many books; now look in this code:

Code:
```#include<iostream.h>
#include<windows.h>

int divison_algorithm(int m, int n)
{
//~   (c) Division algorithm   ~//

//the couple <0,0> is not acceptable !
int r(m),q(0);     /*[q]uotient & [r]eminder*/

/*Details===========================================
!   m = qn + r , 0 =< r < |n| .
!   r = m - [n + n + n ... + n] (q times)
!   [m > n] or [ [m = n or m = kn] (r=0) ]
!   start with q = 1 ---> m = n or (m = 1*n + r)
!   increse q by 1 and decrese r by 1*n (=  n)
!   continue until r < 3 to be a suitabel reminder.
==================================================*/

if (n<0) n = -n; //get the absolute value of n

while( r >= n || r < 0)
{
q++;
r -= n;
}

if (r<0) { //the previous while loop hasent been accede
while( -r >= n || r < 0)
{
q--;
r +=n;
}
}

//Reminder must be positive or zero value .
cout <<"q= " <<q<<endl;
return r;
}

void main(void)
{
cout<< 10%3<<endl;                     //ok true 10 = 3*3 + 1
cout<<divison_algorithm( 10, 3)<<endl; //ok true 10 = 3*3 + 1
cout<<-10%3<<endl;                     //No the reminder must be non-negative
cout<<divison_algorithm(-10, 3)<<endl; //ok true -10 = -4*3 + 2

system("PAUSE");

}```
is the C++ compiler has a mistake or what's wrong ?  Reply With Quote

2. The proof and details are here :

http://en.wikipedia.org/wiki/Division_algorithm  Reply With Quote

3. what's the error message you're getting?  Reply With Quote

4. Senior Member
Join Date
Dec 2003
Posts
3,366
I think he got a negative remainder.  Reply With Quote

5. Yea jonnin is right , the reminder by definition must be positive or null .

I'm asking why c++ compiler make this or in general all compilers make this althought the algorithm is made for have a unique {q} subset from Z and a unique {r} subset from N .

I think it's more explained in the linke above .  Reply With Quote

6. Well, I wouldn't call it a compiler problem then;)
You have to debug the code and see what actually happens. Clearly, there's a bug in the program, but it's not the compiler's fault.  Reply With Quote

7. Anyway ignore "My listed programme" ,it was only to demonstrate the algorithme.

The originale question is about why compilers give us a negative reminder while it's not allowed , BY DEFENETION it must be positive or null .. that's what I mentioned in my code "//No the reminder must be non-negative"

Got it ? now anyone know why ? I think jonnin know what I mean but he hasn't gived us any comment .  Reply With Quote

8. Senior Member
Join Date
Dec 2003
Posts
3,366
I do not fully remember where, but I believe a negative remainder is handy in a few algorithms even if *mathematically* it is not desirable. I will see if I can jog my memory, but in the meantime just use abs on it or something.  Reply With Quote

9. Senior Member
Join Date
Dec 2003
Posts
3,366
I found this blurb on one Q&A session:

There are different ways of thinking about remainders when you deal
with negative numbers, and he is probably confusing two of them. The
mod function is defined as the amount by which a number exceeds the
largest integer multiple of the divisor that is not greater than that
number. In this case, -340 lies between -360 and -300, so -360 is the
greatest multiple LESS than -340; we subtract 60 * -6 = -360 from -340
and get 20:

-420 -360 -300 -240 -180 -120 -60 0 60 120 180 240 300 360
--+----+----+----+----+----+----+----+----+----+----+----+----+----+--
| | | |
-360| |-340 300| |340
|=| |==|
20 40

Working with a positive number like 340, the multiple we subtract is
smaller in absolute value, giving us 40; but with negative numbers, we
subtract a number with a LARGER absolute value, so that the mod
function returns a positive value. This is not always what people
expect, but it is consistent.

If you want the remainder, ignoring the sign, you have to take the
absolute value before using the mod function.

- Doctor Peterson, The Math Forum
http://mathforum.org/dr.math/

But I still can't remember why I was using them at one point... who knows..  Reply With Quote

10. ## The absolute value isn't the solution , in my example abs(-1) = 1 not equal 2 ..

Look at those few lines :
10 = 1*3 + 7 // 7 > 3 , not a remainder
10 = 2*3 + 4 // 4 > 3 , not a remainder
10 = 3*3 + 1 // 1 < 3 , the unique remainder
10 = 4*3 - 2 //-2 < 3 , also but not the remainder , why ?

Usually we need the greatest element lower than the divisor .
so -2 is lower than 3 but we have found 1 satisfy the algorithme and -2 < 1 < 3
if there is an element between 1 and 3 satisfy the algorithm we will take it but 1 is the greatest one , [we can easily show that any element lower than this greatest one will be negative (1 < 3 ==> 1 -3 < 0 ) ] it's from here where we easily say that the remainder must be positive or null (we say null not zero coz it's null if the number divide the divisor , i.e. not exist , zero exist !)

now apply this again with "-10" :
-10 = -5*3 + 5 // 5 > 3 , not a remainder
-10 = -4*3 + 2 // 2 < 3 , greatest lower than 3 , hence the unique remainder .
-10 = -3*3 - 1 // -1 < 3 , not the greatest one (negative) .

The good definition is said :
For every m,n form Z , there exist a unique q (quotient) and a unique r (remainder) form Z satisfy :
m = qn + r , in the condtion 0 =< r < n .

Now try this in cpp : -10%3 // answer is -1 which doesn't satisfy remainder conditions , or we say [2 is greater than -1 and lower than 3] or we say directly [-1 is negative !]

This usually gives us wrong answers and we want all time to return back to my sample or any similar method to correct those errors , is this an error in all compiler or ignored or what ?

P.s. : Originally I get this from someone called "Paula" (with 'a' at the end) who was asking why in cpp '%' gives us sometimes negative results which makes errors in his programming work .
Last edited by Amahdy; 12-14-2006 at 05:58 PM.  Reply With Quote

11. Senior Member
Join Date
Dec 2003
Posts
3,366
The point was the function is modulo, not remainder, and they are defined slightly differently, if that guy was correct. This seems consistent with other posts I found when I looked it up, but none of them explained it very well.  Reply With Quote

12. Same problem ! , u know the set of modulo of a number n is the numbers from 0 to n-1 ...
ig. the return of "x mod(n)" must be a number from 0 to n-1 .
example : normal Cesar Cipher text is optained by mod 26 :
30 mod 26 = 4 (D) , -3 mod 26 = -3 + 26 = 23 (W) ! [u can check this in any encryption software] .
It's commonly knowen under the equivalent class of "n" and here n must be positive which can be considered a subcase from the devision algorithm which accept negative and ZERO values also as divisors .  Reply With Quote

13. Accepting zero is the trivial method :
m = q*0 + r
Take r = m but this make some exeptions coz here r isnt less than m and q isn't unique .  Reply With Quote

14. ## New : it's still strange ! ..
Every body know the uniquness of solution or no solution , right ?

I went today morning to a great profeesor called : "Prof: Amer" , and asking him about this problem [he is an algorithms profeesor ] and he gived me a new answer :

as we know the original divison algorithm states :

(for all m)(for all n)(there is a unique q)(there is a unique r)[ m = qn + r , such that 0 =< r < n ]

And as we know it gives us the reminder and the quotient , the solution for them is unique then it's solvable everytime .
I can give you the prove of the "correctness" and the "uniqness" , moreover the "termination" of this algorithm .. two lemmas can show that ; if anybody want I can list them , they are small .

Now after many operations , the prof gived me the algorithm used in compilers which is :

(for all m)(for all n)(there is a unique q)(there is a unique r)[ m = qn + r , such that |r| < |n| ]

It seems at the first look the same , |r| is always non-negative , but this method accept "negative" values for "r" , before trying to prove this we can see clearly here r is not unique ! yes , in my previous example :
-10 % 3
|-1| < |3| and |2| < |3| , i.e. this algorithm gives more than one r which is not correct , if u ask about how it gives us a solution when it's not solvable ; clearly it "STOPS" after the first result and gives us wrong answer in many cases ..

I'm worried about that is it a general compiler "BUG" or what , regarding that it gives us wrong answers ! using incorrect algorithm !

Finally the professor told me it's easy to correct this in my [and Paula's] work , for now by adding n to the result , simply : <if(r<0) r += n;> but what after that , anybody discuss with me this I'm completly woried .. shall we tell compilers maker about that ?  Reply With Quote

15. My last news in this topic :
How to edit the C++ [or any language] algorithm :
As telling before the used algorithm is :

(for all m)(for all n)(there is a unique q)(there is a unique r)[ m = qn + r , such that |r| < |n| ]

And have prooved that it's wrong, now a small update to make it gives us correct answers :
we have ; 0 < |r| < |n|
if r < 0 then -|n| < r < 0
then 0 < r+|n| < |n|
let r' = r+|n|
now we have r' satisfy the original algorithm (0 < r' < |n|)
that's mean what we need exactly is to add |n| if we have an "r < 0"
~~~~~~~~~~~~~~~~~~~
Now the correction of q:
the new q is : (m - r')/n or by the simplest method : q' = (q - |n|/n) Indeed :
m = nq + r
m = nq + r + |n| - |n|
m = nq + (r + |n|) + (-|n|/n)n
m = n(q - |n|/n) + (r + |n|)
i.e. if we take r' = r + |n| then q must be changed to q' = q - |n|/n

Now the final correction to get true quotient and true reminder in C++ is :
Code:
```//m , n , n>0:
q = m/n;
r = m%n;
if(r<0) { r += abs(n); q -= abs(n)/n; } //Here I'm sure about the correct results which satisfy the algo.```
Please if u read this up to here just give me any comments and what's your opinion about that , compilers have wrong algorithm or i have a mistake or what .
Thank you .  Reply With Quote

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
• 