
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 nonnegative
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 ?


what's the error message you're getting?
Danny Kalev

I think he got a negative remainder.

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 .

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.
Danny Kalev

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 nonnegative"
Got it ? now anyone know why ? I think jonnin know what I mean but he hasn't gived us any comment .

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.

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..

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; 12142006 at 05:58 PM.

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.

Same problem ! , u know the set of modulo of a number n is the numbers from 0 to n1 ...
ig. the return of "x mod(n)" must be a number from 0 to n1 .
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 .

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 .

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 nonnegative , 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 ?

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 .
Similar Threads

By Matrix.net in forum ASP.NET
Replies: 5
Last Post: 10242006, 10:49 AM

By Jeff Johnson in forum .NET
Replies: 2
Last Post: 07252002, 01:57 PM

Replies: 2
Last Post: 05212002, 02:01 PM

Replies: 9
Last Post: 03312002, 11:14 AM

By John Knoop in forum .NET
Replies: 5
Last Post: 10282000, 04:38 PM
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Development Centers
 Android Development Center
 Cloud Development Project Center
 HTML5 Development Center
 Windows Mobile Development Center
