Whats wrong with the C++ compiler ?

The proof and details are here :

http://en.wikipedia.org/wiki/Division_algorithm

I think he got a negative remainder.

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.

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.

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 .

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 .

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 ?

Im fairly confused by this point. However, negative modulo results have existed for decades. If there were an error, I think someone would have noticed before now, seeing as how modulo is very commonly used. See if you can find several matching definations of modulo and compare *that* against the c++ operation, instead of against remainders, and try several compilers as well (you should always get the same result no matter what compiler). Its always possible you have discovered something that has been wrong for 25 or more years, but I just cant imagine a serious bug in so basic a routine has lasted. However, various compilers mess up logical operations on signed numbers as well, and that also surprised me, so odd things do exist in the low level implementations (Mostly by intent for whatever questionable or random reasoning).

You write your own mod for encryption because the standard one cannot handle the large integers used in encryption, right?

thanks for Amady...
first i want to post my thanks and hope to solve that problem but...
why the compiler give us that result??
Is who made the compilers wasn't know the division algorithm and dosen't know that must gives a uniqe (q) and a uniqe(r) ??!!!!!!
i.e. they know or not that :
for all m in Z and n in Z-{0} There exist unique integers q and r such that a = qd + r and 0 ≤ r < | d |, where | d | denotes the absolute value of d.

If the answer was yes, they were know.
why they did that bug (as I see and sure you with me) ..are they couldn't !!! sure no..
and so the question become why they did that ??

If the answer was No, they weren't know.
now we know that this is a bug ... moreover they weren't know that !!
the question become what we can do to solve that bug?

I as a normal user can't think that the computer give me a rong result ...
and that's our problem and we must solve it But HOW ??

Ohhhhhhhhh :mad: :mad: , relly sorry for that defaul
for all m in Z and n in Z-{0} There exist unique integers q and r such that a = qd + r and 0 ≤ r < | d |, where | d | denotes the absolute value of d.

the correct is :
for all m in Z and n in Z-{0} There exist unique integers q and r such that m = qn+ r and 0 ≤ r < | n |, where | n | denotes the absolute value of d.

Hi,

While mathematically correct, your assumptions fail to notice two points:

it is not the compiler that performs the calculations, but the microprocessor. The compiler just translates the code into suitable machine instructions, in this case the instruction that performs the calculation is IDIV, so, -10 % 3 translates into something in the lines of:

mov eax, -10 ; load dividend value
mov ebx, 3 ; load divisor
idiv ebx ; perform integer signed division
; now eax contains the quotient (-3 in this case)
; edx contains the remainder (-1 in this case)So, don't blame your compiler (nor the "great computer scientists" that made that compiler), at least not for this specific "bug".

Intel, in its Software Developer Manual, clearly states how IDIV works and explicitly indicates that:

non-integral results are ALWAYS truncated (chopped) towards 0. Which means IDIV will divide until the absolute value of the reminder is lower than the absolute value of the divisor and no further (which is, in substance, what you ask for, in order to obtain a positive remainder).
the sign of the reminder is ALWAYS the same as the sign of the dividend (in this case, -1 has the same sign as -10).

Is it a bug? Well, It could be said that mathematically speaking the result is not "what was expected" (at least by you). But certainly it is not incorrect, either (the result does satisfy Dividend = Divisor * Quotient + Reminder).

This has to do with the way division is implemented in the processor's ALU (Arithmetic Logic Unit), and the divider circuit's limitations. You can get an idea of the algorithms used for division in circuits by taking a look here (en.wikipedia.org/wiki/Division_%28electronics%29).

IMHO, programming requires one to acknowledge these constraints and, where necessary, devise a way around the limitations the architecture pushes on you. After all, most cyphering programs work correctly, despite this detail...

Hi, Amahdy,

First off, the manual I'm referring to is located here (http://www.intel.com/design/processor/manuals/253666.pdf). This is the first part of the instruction set, volume 2A. Just search for the IDIV instruction in the index. The rest of the volumes can be downloaded here (http://www.intel.com/products/processor/manuals/index.htm) along with some optimization guides. You can find similar info in AMD's website, for their respective processors.

With regards to the fact that this is a bug, I'll just refer to Wikipedia (entire article here (http://en.wikipedia.org/wiki/Remainder)) which states:

The way remainder was defined, in addition to the equality a=qd+r an inequality was also imposed, which was either 0≤ r < |d| or -|d| < r ≤ 0. Such an inequality is necessary in order for the remainder to be unique that is, for it to be well-defined. The choice of such an inequality is somewhat arbitrary. Any condition of the form x < r ≤ x+|d| (or x ≤ r < x+|d|), where x is a constant, is enough to guarantee the uniqueness of the remainder.

With two choices for the inequality, there are two possible choices for the remainder, one is negative and the other is positive. This means that there are also two possible choices for the quotient. Usually, in number theory, we always choose the positive remainder. But programming languages do not. C99 and Pascal choose the remainder with the same sign as a. (Before C99, the C language allowed either choice.) Perl and Python choose the remainder with the same sign as d.

In the excerpt, a is the dividend, d is the divisor, q is the quotient and r is the remainder. As you see, there have been different ways of approaching this and neither is inherently wrong.

Of course, when I said programmers had to know these details I was just generalizing, saying that a programmer should be prepared to circumvent a problem when it comes up, instead of "blaming it to the hardware". After all, hardware is known to have limits.

You posted a solution for the problem already, checking if the reminder is negative and adjusting the results seems to be the correct, and only, way to go.

This could come as news to you, but actually computers are terrible mathematicians... they are too limited in the way they represent numbers, to begin with. In computers, most advanced (and not so advanced) math is either simulated or approximated. For example, a computer does not natively understand negative numbers, or real numbers, it just simulates them, but at the cost of precision.