DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Page 1 of 2 12 LastLast
Results 1 to 15 of 29

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

  1. #1
    Join Date
    Oct 2005
    Location
    Maady
    Posts
    1,819

    Arrow 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 ?
    Programmer&Cracker CS
    MyBlog:Blog.Amahdy.com
    MyWebsite:www.Amahdy.com

  2. #2
    Join Date
    Oct 2005
    Location
    Maady
    Posts
    1,819
    The proof and details are here :

    http://en.wikipedia.org/wiki/Division_algorithm
    Programmer&Cracker CS
    MyBlog:Blog.Amahdy.com
    MyWebsite:www.Amahdy.com

  3. #3
    Join Date
    Nov 2003
    Posts
    4,118
    what's the error message you're getting?
    Danny Kalev

  4. #4
    Join Date
    Dec 2003
    Posts
    3,366
    I think he got a negative remainder.

  5. #5
    Join Date
    Oct 2005
    Location
    Maady
    Posts
    1,819
    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 .
    Programmer&Cracker CS
    MyBlog:Blog.Amahdy.com
    MyWebsite:www.Amahdy.com

  6. #6
    Join Date
    Nov 2003
    Posts
    4,118
    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

  7. #7
    Join Date
    Oct 2005
    Location
    Maady
    Posts
    1,819
    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 .
    Programmer&Cracker CS
    MyBlog:Blog.Amahdy.com
    MyWebsite:www.Amahdy.com

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

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

  10. #10
    Join Date
    Oct 2005
    Location
    Maady
    Posts
    1,819

    Arrow

    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.
    Programmer&Cracker CS
    MyBlog:Blog.Amahdy.com
    MyWebsite:www.Amahdy.com

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

  12. #12
    Join Date
    Oct 2005
    Location
    Maady
    Posts
    1,819
    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 .
    Programmer&Cracker CS
    MyBlog:Blog.Amahdy.com
    MyWebsite:www.Amahdy.com

  13. #13
    Join Date
    Oct 2005
    Location
    Maady
    Posts
    1,819
    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 .

  14. #14
    Join Date
    Oct 2005
    Location
    Maady
    Posts
    1,819

    Arrow

    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 ?
    Programmer&Cracker CS
    MyBlog:Blog.Amahdy.com
    MyWebsite:www.Amahdy.com

  15. #15
    Join Date
    Oct 2005
    Location
    Maady
    Posts
    1,819
    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 .
    Programmer&Cracker CS
    MyBlog:Blog.Amahdy.com
    MyWebsite:www.Amahdy.com

Similar Threads

  1. Replies: 5
    Last Post: 10-24-2006, 10:49 AM
  2. c# compiler and c++
    By Jeff Johnson in forum .NET
    Replies: 2
    Last Post: 07-25-2002, 01:57 PM
  3. Replies: 2
    Last Post: 05-21-2002, 02:01 PM
  4. please tell me i'm wrong!
    By mark in forum .NET
    Replies: 9
    Last Post: 03-31-2002, 11:14 AM
  5. C# Compiler (csc.exe)
    By John Knoop in forum .NET
    Replies: 5
    Last Post: 10-28-2000, 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
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

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