flooring divide

[Stephan Houben]

Hi group,

I find myself often needing a "flooring divide", i.e. integer division which
rounds towards negative infinity:

def floor_div(x : Int, y : Int) = math.floor(x.toDouble / y).toInt

Is there a better way to do this than above function?
I searched the docs but this doesn't appear to be a built-in
operation, despite the fact that I find in general the Scala libs very rich.

Stephan

[Erik Osheim]

On Fri, Jun 29, 2012 at 12:06:34PM -0700, Stephan Houben wrote:
> def floor_div(x : Int, y : Int) = math.floor(x.toDouble / y).toInt
>
> Is there a better way to do this than above function?
> I searched the docs but this doesn't appear to be a built-in
> operation, despite the fact that I find in general the Scala libs very rich.

Not AFAIK.

It's a good reminder that Java's integer division isn't the same as
floor division when negative, since Java rounds towards zero (which I
am often frustrated by).

-- Erik

[Daniel Sobral]

Symmetric vs Floored division! Yay!

Hardware favors the former. There were such hell about this on the ANS
Forth Committee, that the standard made both versions available, and
the standard division (/) implementation-dependent.

Naturally, floored division is far superior because you can always
reconstruct the arguments given the division result and remainder.

--
Daniel C. Sobral

I travel to the future all the time.

[Vlad Patryshev]

Daniel, you worked with Forth?

Cool.

(And I remember implementing in Forth all 4 fpu floorings...)

Thanks,
-Vlad

[Dominik]

What I dislike at the proposed solution is

scala> floor_div(5, 0)
res10: Int = 2147483647

What about

def floor_div(x: Int, y: Int) = x / y match {
  case q if q > 0 => q
  case q if x % y == 0 => q
  case q => q-1
}

Dominik

[Rex Kerr]

I like the idea, but I'd write it as

  def floor_div(x: Int, y: Int) = {
    val q = x/y
    if (q > 0 || q*y == x) q
    else q-1
  }

to avoid the extra division and to avoid repeatedly declaring q.

  --Rex

[Stephan Houben]

Hi Rex,

On 02-07-12 23:18, Rex Kerr wrote:
> I like the idea, but I'd write it as
>
> def floor_div(x: Int, y: Int) = {
> val q = x/y
> if (q > 0 || q*y == x) q
> else q-1
> }
>
> to avoid the extra division and to avoid repeatedly declaring q.
>

Note that this goes wrong for y < 0:

scala> floor_div(-2, -3)
res9: Int = -1

FWIW, the reason I asked on this group in the first place is that
I found it remarkably tricky to get right.

Stephan


> --Rex

>
> On Mon, Jul 2, 2012 at 4:37 PM, Dominik <dominik...@gmail.com <mailto:dominik...@gmail.com>> wrote:
>
> What I dislike at the proposed solution is
>
> scala> floor_div(5, 0)

> res10: Int = 2147483647 <tel:2147483647>

[Gruntz Dominik]

sorry, my fault. Indeed tricky.
2nd attempt:

def floor_div(x: Int, y: Int) = {
val q = x/y

if (q*y == x || math.signum(x) == math.signum(y)) q
else q-1
}

Dominik

[Rex Kerr]

That looks good.  This is slightly faster (~20%) on my machine:

  def floor_div(x: Int, y: Int) = {
    val q = x/y

    if (q*y==x) q
    else q - ((x ^ y) >>> 31)
  }

at the expense of being less obvious: (x ^ y) has the sign bit set only if one of the two is negative, and >>> 31 keeps only the sign bit.

  --Rex