Bug #111: Mod fn for computing remainder - CoCoALib - CoCoA Project

Bug #111

Mod fn for computing remainder

Added by John Abbott about 12 years ago. Updated about 1 month ago.

Status:

Closed

Priority:

Normal

Assignee:

John Abbott

Category:

Documentation

Target version:

CoCoALib-0.99850

Start date:

20 Mar 2012

Due date:

% Done:

100%

Estimated time:

0.76 h

Spent time:

0.75 h

Description

The doc says the result is least non-neg remainder...
BUT the code uses mpz_tdiv which "truncates" towards zero, so the remainder has the same sign as the value being reduced (if the divisor is positive).

I believe the reason for the change was so that MachineInt % BigInt could give a MachineInt result even if the arg is negative (but this was not mentioned in any change log).

The doc also says that negative divisors are not allowed, but the code which checks this has been commented out.

Note that the CoCoA-5 fn Mod calls directly the CoCoALib fn mod. This is probably good (because it should simplify porting C5 code into C++/CoCoALib) but then the C5 doc must also be updated!

What to do??

History

#1 Updated by John Abbott about 12 years ago

The use of tdiv functions produces a (pleasing) sign symmetry:

namely A%B = - ((-A)%B) = - A%(-B) = (-A)%(-B)
also we always have A = div(A,B) + A%B

The negative aspect is that the range of A%B includes negative values; indeed any value from 1-|B| to |B|-1 may occur.

JAA also recalls that negative divisors were banned in CoCoALib for a while, but that this restriction was removed because it was "unnecessary" and only weakly justifiable: I wanted to use fdiv for non-negative remainders and tdiv for integer quotients because this seemed more natural -- this meant that condition (2) would not hold for negative B.

JAA proposes that we accept the current (tdiv) impl, and adjust the documentation accordingly -- giving an example to show that negative remainders can arise.