Talk:Integer division

[Least absolute remainder] integer division

The [least absolute remainder] integer division of an integer 

m

by a nonzero integer 

n

is defined as

$\left\lfloor {\frac {m}{n}}+{\rm {sgn}}(n)\,{\frac {1}{2}}\right\rfloor ,\quad m\in \mathbb {Z} ,n\in \mathbb {Z} ^{*},$

where 

sgn (n)

is the sign function. In the mapping

$(m,n)\mapsto (q,r):=\left(\left\lfloor {\frac {m}{n}}+{\rm {sgn}}(n)\,{\frac {1}{2}}\right\rfloor ,m-\left\lfloor {\frac {m}{n}}+{\rm {sgn}}(n)\,{\frac {1}{2}}\right\rfloor n\right),\quad m\in \mathbb {Z} ,n\in \mathbb {Z} ^{*},$

the [least absolute remainder] integer division is the integer quotient 

q ∈ ℤ

with 

−  ⌊   | n | /2⌋   ≤   r < | n |  −  ⌊   | n | /2⌋

as the least absolute remainder.

For example

•  

  (7, 2)

  maps to 

  (4, 7  −  4  ×  2) = (4,  − 1)

  ;
•  

  ( − 7, 2)

  maps to 

  ( − 3,  − 7  −  ( − 3)  ×  2) = ( − 3,  − 1)

  ;
•  

  (7,  − 2)

  maps to 

  ( − 4, 7  −  ( − 4)  ×  ( − 2)) = ( − 4,  − 1)

  ;
•  

  ( − 7,  − 2)

  maps to 

  (3,  − 7  −  3  ×  ( − 2) = (3,  − 1)

  .

Am I getting it right? — Daniel Forgues 04:46, 6 September 2016 (UTC)

More compactly written. — Daniel Forgues 03:29, 7 September 2016 (UTC)

I've never heard of least absolute remainder integer division. - Charles R Greathouse IV 04:10, 7 September 2016 (UTC)

With least absolute remainder division, the Euclidean algorithm for gcd takes the least number of steps: 

O (log2(n))

steps instead of 

O (logϕ(n))

steps (with the usual least positive remainder division).

Moore, Thomas (1992). "On the least absolute remainder Euclidean algorithm." In Mathematics and Computer Science Faculty Publications. Paper 13. Available at: http://vc.bridgew.edu/math_compsci_fac/13

Sreeram Vuppala, The Aryabhata Algorithm Using Least Absolute Remainders.

— Daniel Forgues 04:54, 7 September 2016 (UTC)

Thanks for the sources. I can't find that particular quote in either of the sources, but I'm interested to know its origins since 

O (log2(n))

= 

O (logϕ(n))

and so it is essentially wrong. (The intention is clear, of course.) We will be more careful when writing that result up!

I don't have a problem including this operation and associated result in the OEIS wiki, but I'm hesitant to call the q of this operation the integer quotient, since that differs from the usual meaning. But write it up however feels best and I'll try to check back later.

Charles R Greathouse IV 05:23, 7 September 2016 (UTC)

Also,

M. Syafiq Johar (2015), Minimal Number of Steps in Euclidean Algorithm and its Application to Rational Tangles.

Actually, what I see is least absolute remainder Euclidean algorithm, not least absolute remainder integer division. But it appears to me that least absolute remainder Euclidean algorithm uses least absolute remainder integer division (the q of this operation would be the "nearest integer quotient")... — Daniel Forgues 05:36, 7 September 2016 (UTC)

The Ancient Greeks did not have negative numbers. I wonder whether Euclid would have defined his Euclidean division differently, and also his Euclidean algorithm for gcd... — Daniel Forgues 05:46, 7 September 2016 (UTC)

Really he defined it in terms of subtraction, and division is just a convenient shortcut. - Charles R Greathouse IV 20:19, 7 September 2016 (UTC)

I know that 

O (log2(n)) = O (logϕ(n)) = O (log n)

since 

logϕ(n) = log n log ϕ = (2.0780869...) log n

and 

log2(n) = log n log 2 = (1.442695...) log n

. So the least absolute remainder Euclidean algorithm for gcd is only faster by the constant factor 

log 2 log ϕ = 1.44042...

compared to the classical least positive remainder Euclidean algorithm for gcd. I remember having seen somewhere that the number of division steps for the least absolute remainder Euclidean algorithm is of order of 

log2(n)

; since the absolute value of the remainder is essentially divided by 2 at each step, I can see why. — Daniel Forgues 02:47, 9 September 2016 (UTC)

The least absolute remainder division seems in some sense even more natural than least positive remainder division since then 

71 / 9 = 8 rem (−1)

, i.e. 8 parts, the last part being short by 1... (thus a "remainder" only when less than half the divisor, an extra part with a "shortage" otherwise) — Daniel Forgues 03:10, 9 September 2016 (UTC)