parC int division rounds up

Question

I came across this code in parC.

I can't understand in which scenario (the yellow mark) it can happen? I mean when does the result of division can round up when the value type is Int?

Answer 1

I know nothing about parC, but as far as C is considered, you're right: integer division of positive values is defined to truncate the fraction, that is to round towards zero.

However, there is another bug in the code: if the array is too long, the midpoint may be calculated incorrectly.

To be precise, if initial to is greater by 2 or more than a half of maximum value representable in int type (INT_MAX), then one of recursive call will get fr, to values both greater than (INT_MAX/2) and the expression (to+fr) will cause an arithmetic overflow. The result of (to+fr)/2 will be less than fr/2.

To avoid this, expression like fr + (to - fr)/2 is recommended instead of (to + fr)/2.

EDIT

There are also bugs in the description! See the image:

The (4,5) → (4, 5) recursion happens one level earlier than authors indicate, so one subtree should not actually appear in the graph. Additionally, if the program gets stuck in the red-arrow loop, then the (6,5) recursion will never happen – the process will never reach that branch.

Interesting, authors apparently overlooked yet another loop appearing in their drawing;
recursion (1,2) → (1,2) appears even earlier than those two mentioned above:

As a side note, I can't imagine how they obtained two different results of partitioning the same range:
(4,5) → (4,5) + (6,5) and (4,5) → (4,5) + (5,5)
(see green frames). Possibly they were so absorbed with forcing the idea of up-rounding that they neglected any reasoning about all other aspects of the problem.

Based on this single example I would recommend to put the book in a trash bin.

Answer 2

You are right, integer division for positive operands in C always rounded to floor of the division, check this question for more details. I'm not familiar with parC, but it's said to be full C++ language with some additions from other languages, so described task seems to be incorrect.

If there are concerns left, you always have opportunity to check task directly: setup environment for parC, type implementation of rsum() and execute rsum(A, 1, 5).

Answer 3

You might be reading a text which is older than 18 years. In older versions of the C standard, division with negative operands could get rounded in an implementation-defined way: either downwards or upwards. Meaning that -3/2 could give you either -1 or -2 depending on compiler.

This was recognized as a design flaw in the language and was corrected with the C99 standard. Nowadays, C always uses "truncation towards zero" no matter compiler.