Home c# The residue for the negative argument is erroneous?

The residue for the negative argument is erroneous?

Author

Date

Category

In many programming languages ​​(C, C++, C #, Java, various Pascal, PHP, JavaScript dialects) there is a residue calculation operator. It acts obvious, the only correct way for positive values ​​of the argument (17% 5 == 2 ), but for a negative division and positive divider, it gives a negative result:

- 17% 5 == -2

The usual application of the % operator, however – to calculate hashes, indexes in the ring buffer, as well as the calculation of the canonical representative groups of numbers, that is, to represent equivalence rating. For example, the number of the week of the week is naturally calculated as the balance of the division of the “global” number of the day by 7. Checking the number to oddness is also determined by the residue during division by 2.

However, the % statement as it is implemented in the mentioned languages, unsuitable without additional processing: a function like

int mod (int n, int d)
{
  INT RESULT = N% D;
  If (Sign (Result) * Sign (D) & LT; 0)
    result + = d;
  RETURN RESULT;
}

which provides a positive result with a positive divider.

in such a function, unlike % , there is a useful invariant:

mod (n + k * d, d) == mod (n, d)

(provided that the calculation of both parts does not lead to overflow).

I will give a few examples.

1) Checking for oddness usually looks like this:

// Bool ODD = N% 2 == 1; // not right!
BOOL ODD = N% 2! = 0; // Pretty artificiality

But with the new operator it works easier:

bool odd = mod (n, 2) == 1; // As expected.

2) To calculate the bucket’a in the hash table, also uses the residue:

int bucketidx = object.gethashcode ()% buckets.count;
if (Bucketidx & lt; 0) bucketidx + = buckets.count;

or so (code from .NET 4.0)

int positivehashcode = object.gethashcode () & amp; 7FFFFFFF;
int bucketidx = positivehashcode% buckets.count;

At the same time

int bucketidx = mod (object.gethashcode (), budkets.count);

would work in any case.

3) bringing an angle in degrees to canonical form (from 0 to 360):

mod (angle, 360)

In Radians: Mod (Angle, 2 * Pi)

The same with % looks much more hard.

ATTENTION, QUESTION : Does someone need a % statement as defined in the language? It would not be better that the % operator returned the value like MOD ? I assume that whenever the % statement is used, actually meant exactly mod , and either input arguments are always positive or A correction is used for negative division, or the program contains a bug.

Does anyone have examples (from practice or theoretical) when you need the existing behavior of the operator % ?


Two respondents rightly notice that the private q and the residue r when dividing n on D should satisfy the condition

n == Q * d + r

In order for it to work, you can override and dividing so that rounding is always running down: Q == Floor ((Double) N / (Double) D) . At the same time, the desired ratio will be automatically performed:

4/3 == 1 4% 3 == 1 4 = 1 * 3 + 1
 3/3 == 1 3% 3 == 0 3 = 1 * 3 + 0
 2/3 == 0 2% 3 == 2 2 = 0 * 3 + 2
 1/3 == 0 1% 3 == 1 1 = 0 * 3 + 1
 0/3 == 0 0% 3 == 0 0 = 0 * 3 + 0
-1 / 3 == -1 -1% 3 == 2 -1 = -1 * 3 + 2
-2 / 3 == -1 -2% 3 == 1 -2 = -1 * 3 + 1

et al.


Answer 1, Authority 100%

The question seems to me it is rather in the field of definition than logic.

If you plunge into the history of the question, the divisible and balance of division belongs to the well-known theorem in the theory of numbers, the fact that any integer can be decomposed on a divide and balance of division – theorem Proven in the time of Euclide . The trouble is only with the fact that during Euclide, people did not know negative numbers.

If one of the numbers is a divider or delimitable, then the task will have 2 solutions – with a negative and positive residue. This is where the arrangement / definition arises. Russian has a 2-digit interpretation, but in English
The residue language is indicated by 2 terms:

Remainder – the balance of division (maybe negative)

residual – literally sediment (always positive)

So in Java, and so on. Languages ​​are used in the module in the sense of Remainder, and what @vladd This is residual

PS How the division of the module is calculated in different languages ​​you can see here – Once again testifies In favor of the fact that the question is not in logic, but in agreement.


Answer 2, Authority 23%

And who said that the balance from division should meet the requirements that beneficial @vladd ?

Open the standard, paragraph 5.6. It is clearly written that it makes the % :

(A / B) * B + A% B is equivalent to a, if only b! = 0

That is, behavior is standardized and expected.

Why not make the rest always positive? Yes, because this condition will not be performed either we will need to recognize that the integer division of negative numbers is not subject to the usual laws of algebra.

Apparently, not only mathematicians agree with this, but also processor manufacturers, because there is the same implementation.


Answer 3, Authority 10%

I believe that the logic of the module itself is crumbling, because:

a / b = c whole (d residue)

c * b + d = a

In the case of a negative number, we get:

- 15/2 = -7 (-1)

Reverse:

- 7 * 2 + (-1) = -15

i.e., that I want to say, mathematics collapses, if you take a positive balance or do this:

- 15/2 = -8 (+1)

upd: what about examples from practice, hmm, there are no them 🙂 I somehow did not have to get the balance from the negative number 🙂


Answer 4, Authority 9%

have to use such an operator%, how did the developers made it and as it is described in the standard, though, I know two areas where the balance of division is used is noise-resistant coding and cryptography. In both cases, the balance from division must return only a positive integer.

This requirement is based on the theory of finite fields of Galois. It is important to understand – what is an algebraic group, an algebraic ring and a Galua field (and wiki to help you). But the correct sale of division is simple in the final field is a whole algorithm similar to Euclidea algorithm. And it should also be noted that the final fields exist not for any number of arguments. And division in extended halua fields is even more difficult – based on the division of polynomials in the final fields.

So for example, consider the Galoi field out of 7 elements. That is, we have a field of definition (and the area of ​​permissible values)
{0, 1, 2, 3, 4, 5, 6} and additions of addition and multiplication by module 7.
In this case: (1/3) MOD 7 = 5 because (5 * 3) MOD 7 = 1.
However, the command on C will give a value (1/3)% 7 = 0

So it would not be bad so that the team% worked as in mathematical theory, but in practice it has to do something like this example from my old program:

// A / B MOD C
Long __fastcall TFORMELLIPTICCRYPT :: sub_div (Long A, Long B, Long C)
{
LONG D, E, F, G, H, I, J;
d = 1; E = 0; G = C; j = b;
for (i = 0; j & gt; 0; i ++)
  {
  h = b / g;
  j = b - h * g;
  if (i! = 0)
      {
      F = D * H + E;
      E = D;
      d = f;
      }
  b = g;
  G = J;
  }
if (I% 2! = 0) E = C - E;
d = (a * e)% c;
Return (D);
}

Of course, there are not rarely cases when such difficulties are unnecessary.

And besides the construction of the division, there is still extracting roots and logarithms in the module (in the final fields and rings) that are considered completely different than in the usual algebra of real numbers and for so much roads that some known cryptosystems are found on the computational complexity of their implementation ( Diffi Helmman, El Gamal, DSA, “Radders Laying”, cryptography on elliptical curves in finite fields, etc. etc.)

But it is much more important if the standard of language is accepted – it is better not to change it, but only complementing, otherwise the programs written over the years and dozens of years will be not correct in new versions of compilers. And without it there is enough dancing with a tambourine when applying for a newer version of the compiler, when “outdated” commands are removed from it. And if the team remains correct, but will give another result – this will require efforts comparable with the correction of “Errors 2000” at the end of last century.


Answer 5

I thought here and it seems to me that the operation of the balance from division must be taken as it was conceived by the author. This is his right, and if they do not agree with his opinion, then make your own residue operation or write a function that you have done). Conclusion: the percentage symbol is just a tool and how to use it each decides for itself.

Programmers, Start Your Engines!

Why spend time searching for the correct question and then entering your answer when you can find it in a second? That's what CompuTicket is all about! Here you'll find thousands of questions and answers from hundreds of computer languages.

Recent questions