Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

When is the difference between quotRem and divMod useful?

From the haskell report:

The quot, rem, div, and mod class methods satisfy these laws if y is non-zero:

(x `quot` y)*y + (x `rem` y) == x
(x `div`  y)*y + (x `mod` y) == x

quot is integer division truncated toward zero, while the result of div is truncated toward negative infinity.

For example:

Prelude> (-12) `quot` 5
-2
Prelude> (-12) `div` 5
-3

What are some examples of where the difference between how the result is truncated matters?

like image 412
grom Avatar asked Dec 04 '08 06:12

grom


People also ask

What is divMod Haskell?

Tags: haskell, programming. divMod is integer division and modulo that truncates towards negative infinity, while quotRem is integer division and modulo that behaves like C-style operators which truncate towards zero.

What Is REM in Haskell?

rem is integer remainder, satisfying: (x `quot` y)*y + (x `rem` y) == x. div is integer division truncated toward negative infinity.


3 Answers

Many languages have a "mod" or "%" operator that gives the remainder after division with truncation towards 0; for example C, C++, and Java, and probably C#, would say:

(-11)/5 = -2
(-11)%5 = -1
5*((-11)/5) + (-11)%5 = 5*(-2) + (-1) = -11.

Haskell's quot and rem are intended to imitate this behaviour. I can imagine compatibility with the output of some C program might be desirable in some contrived situation.

Haskell's div and mod, and subsequently Python's / and %, follow the convention of mathematicians (at least number-theorists) in always truncating down division (not towards 0 -- towards negative infinity) so that the remainder is always nonnegative. Thus in Python,

(-11)/5 = -3
(-11)%5 = 4
5*((-11)/5) + (-11)%5 = 5*(-3) + 4 = -11.

Haskell's div and mod follow this behaviour.

like image 172
ShreevatsaR Avatar answered Oct 20 '22 11:10

ShreevatsaR


This is not exactly an answer to your question, but in GHC on x86, quotRem on Int will compile down to a single machine instruction, whereas divMod does quite a bit more work. So if you are in a speed-critical section and working on positive numbers only, quotRem is the way to go.

like image 23
luqui Avatar answered Oct 20 '22 11:10

luqui


A simple example where it would matter is testing if an integer is even or odd.

let buggyOdd x = x `rem` 2 == 1
buggyOdd 1 // True
buggyOdd (-1) // False (wrong!)

let odd x = x `mod` 2 == 1
odd 1 // True
odd (-1) // True

Note, of course, you could avoid thinking about these issues by just defining odd in this way:

let odd x = x `rem` 2 /= 0
odd 1 // True
odd (-1) // True

In general, just remember that, for y > 0, x mod y always return something >= 0 while x rem y returns 0 or something of the same sign as x.

like image 7
namin Avatar answered Oct 20 '22 13:10

namin