# Why is fld(a, b) so much slower than floor(a / b)?

**URL:** <https://discourse.julialang.org/t/why-is-fld-a-b-so-much-slower-than-floor-a-b/30914>\
**Category:** General Usage\
**Created:** [November 10, 2019, 11:02am UTC](https://discourse.julialang.org/t/why-is-fld-a-b-so-much-slower-than-floor-a-b/30914 "2019-11-10T11:02:50Z")\
**Posts on this page:** 12\
**Page:** 1

<div class="post-metadata">

**Author:** ![zsoerenm](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/zsoerenm/32/664_2.png) [@zsoerenm](https://discourse.julialang.org/u/zsoerenm)\
**Post date:** [November 10, 2019, 11:02am UTC](https://discourse.julialang.org/t/why-is-fld-a-b-so-much-slower-than-floor-a-b/30914/1 "2019-11-10T11:02:51Z")

</div>

I am using `mod` in a hot loop and I wondered why it is taking so much time.  
When I implemented `mod` myself with

```julia
mod_fast(a, b) = a - b * floor(a / b)

```

I found out it was a lot faster:

```julia
julia> @btime mod_fast($(Ref(1232.23))[], 1023)
  2.298 ns (0 allocations: 0 bytes)
209.23000000000002
julia> @btime mod($(Ref(1232.23))[], 1023)
  8.325 ns (0 allocations: 0 bytes)
209.23000000000002

```

The documentation says that `fld` is used instead of `floor`. And this is indeed makes a lot of difference:

```julia
julia> @btime floor($(Ref(1232.23))[] / 1023)
  1.888 ns (0 allocations: 0 bytes)
1.0
julia> @btime fld($(Ref(1232.23))[], 1023)
  8.911 ns (0 allocations: 0 bytes)
1.0

```

So what is the exact difference?  
Is it save to use my `mod` function?

---

<div class="post-metadata">

**Author:** ![oheil](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oheil/32/220745_2.png) [@oheil](https://discourse.julialang.org/u/oheil)\
**Post date:** [November 10, 2019, 11:46am UTC](https://discourse.julialang.org/t/why-is-fld-a-b-so-much-slower-than-floor-a-b/30914/2 "2019-11-10T11:46:51Z")

</div>

You can follow whats going on with `which`:

```julia
julia> which(fld,(Float64,Int))
fld(x::Real, y::Real) in Base at promotion.jl:355

```

which is:

```julia
fld(x::Real, y::Real) = fld(promote(x,y)...)

```

You get:

```julia
julia> which(fld,(Float64,Float64))
fld(x::T, y::T) where T<:Real in Base at operators.jl:701

```

which is:

```julia
fld(x::T, y::T) where {T<:Real} = convert(T,round((x-mod(x,y))/y))

```

On the other hand:

```julia
julia> which(floor,(Float64,))
floor(x::Real) in Base at floatfuncs.jl:152

```

which is just:

```julia
floor(x::Real; kwargs...) = round(x, RoundDown; kwargs...)

```

I am not sure it this is enough to explain the differences in performance.

---

<div class="post-metadata">

**Author:** ![GunnarFarneback](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gunnarfarneback/32/1827_2.png) [@GunnarFarneback](https://discourse.julialang.org/u/GunnarFarneback)\
**Post date:** [November 10, 2019, 11:49am UTC](https://discourse.julialang.org/t/why-is-fld-a-b-so-much-slower-than-floor-a-b/30914/3 "2019-11-10T11:49:47Z")

</div>

Edit: Never mind, my reading skills are too limited.

> [@zsoerenm](#):
>
> So what is the exact difference?

`fld` does integer division. This tends to be slower than floating point division these days.

> [@zsoerenm](#):
>
> Is it save to use my `mod` function?

For your use case it may very well be, but not for the full range of the arguments.

```julia
julia> mod(typemax(Int), typemax(Int) - 1)
1

julia> mod_fast(typemax(Int), typemax(Int) - 1)
0.0

```

---

<div class="post-metadata">

**Author:** ![GunnarFarneback](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gunnarfarneback/32/1827_2.png) [@GunnarFarneback](https://discourse.julialang.org/u/GunnarFarneback)\
**Post date:** [November 10, 2019, 4:02pm UTC](https://discourse.julialang.org/t/why-is-fld-a-b-so-much-slower-than-floor-a-b/30914/4 "2019-11-10T16:02:58Z")

</div>

To answer the actually asked question, i.e. the floating point case.

> [@zsoerenm](#):
>
> So what is the exact difference?

What happens exactly can be traced down the call chain as already shown. The difference mostly boils down to attention to rounding and cancellation issues.

> [@zsoerenm](#):
>
> Is it save to use my `mod` function?

That depends on how sensitive your code is to getting a result out of range.

```julia
julia> mod_fast(prevfloat(12.3), 1.23)
-1.7763568394002505e-15

julia> mod(prevfloat(12.3), 1.23)
1.229999999999999

```

---

<div class="post-metadata">

**Author:** ![oheil](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oheil/32/220745_2.png) [@oheil](https://discourse.julialang.org/u/oheil)\
**Post date:** [November 10, 2019, 5:56pm UTC](https://discourse.julialang.org/t/why-is-fld-a-b-so-much-slower-than-floor-a-b/30914/5 "2019-11-10T17:56:37Z")

</div>

It seems, defining your own `mod` function is not a bad idea, e.g. using the built-in function can give strange results:

```julia
julia> div(-7,3)
-2

julia> mod(-7,3)
2

```

---

<div class="post-metadata">

**Author:** ![GunnarFarneback](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gunnarfarneback/32/1827_2.png) [@GunnarFarneback](https://discourse.julialang.org/u/GunnarFarneback)\
**Post date:** [November 10, 2019, 6:08pm UTC](https://discourse.julialang.org/t/why-is-fld-a-b-so-much-slower-than-floor-a-b/30914/6 "2019-11-10T18:08:27Z")

</div>

What is strange about those results and what results did you expect?

---

<div class="post-metadata">

**Author:** ![oheil](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oheil/32/220745_2.png) [@oheil](https://discourse.julialang.org/u/oheil)\
**Post date:** [November 10, 2019, 6:39pm UTC](https://discourse.julialang.org/t/why-is-fld-a-b-so-much-slower-than-floor-a-b/30914/7 "2019-11-10T18:39:00Z")

</div>

I would expect that mod(-7,3) results in -1 but I know that this is implementation specific (or if you want depends on the mathematical definition).

```julia
-7 / 3 = -3 remainder 2

```

So “strange” is bad wording, lets say it may be surprising, depending on what you expect.  
In this sense it is not wrong to implement it the way one wants to have it.

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [November 11, 2019, 5:52am UTC](https://discourse.julialang.org/t/why-is-fld-a-b-so-much-slower-than-floor-a-b/30914/8 "2019-11-11T05:52:37Z")

</div>

I think it is the documented behavior: from `?mod` (emphasis is mine),

> The reduction of x modulo y, or equivalently, the remainder of x after floored division by y, i.e. x -  
> y\*fld(x,y) if computed without intermediate rounding.
> 
> The result will have **the same sign as y, and magnitude less than abs(y)** (with some exceptions, see note below).

But maybe the wording is a bit indirect — please consider making a small PR to this docstring with the example above.

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [November 11, 2019, 5:59am UTC](https://discourse.julialang.org/t/why-is-fld-a-b-so-much-slower-than-floor-a-b/30914/9 "2019-11-11T05:59:22Z")

</div>

Note that Julia agrees with C and Python. Java disagrees, and is arguably wrong since it means that fld in Java rounds to 0 instead of -Inf, which is very annoying for some purposes.

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [November 11, 2019, 6:04am UTC](https://discourse.julialang.org/t/why-is-fld-a-b-so-much-slower-than-floor-a-b/30914/10 "2019-11-11T06:04:37Z")

</div>

There are three questions here:

1. whether the documented behavior is correct (it is),

2. whether it could be explained a bit better (yes, and people stumbling into it are in the best position to do so),

3. is it violating some common consensus or expectation (like `1 + 3` returning `9`).

(3) is much harder to argue here as different languages have apparently different semantics. In any case, it cannot be changed before 2.0 as it would be breaking, and it is unlikely that people would want to break this, but you can always open an issue about it.

---

<div class="post-metadata">

**Author:** ![jling](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jling/32/212909_2.png) [@jling](https://discourse.julialang.org/u/jling)\
**Post date:** [November 11, 2019, 6:43am UTC](https://discourse.julialang.org/t/why-is-fld-a-b-so-much-slower-than-floor-a-b/30914/11 "2019-11-11T06:43:00Z")

</div>

mathematical definition of reminder also agrees with `mod` (not saying math people always have the most convenient definition for programming purpose), just that in no way is this strange

> **[Remainder](https://en.wikipedia.org/wiki/Remainder)**
>
> In mathematics, the remainder is the amount "left over" after performing some computation. In arithmetic, the remainder is the integer "left over" after dividing one integer by another to produce an integer quotient (integer division). In algebra of polynomials, the remainder is the polynomial "left over" after dividing one polynomial by another. The modulo operation is the operation that produces such a remainder when given a dividend and divisor.
> Alternatively, a remainder is also what is left...

> If _a_ and _d_ are [integers](https://en.wikipedia.org/wiki/Integer), with _d_ non-zero, it can be proven that there exist unique integers _q_ and _r_ , such that _a_ = _qd_ + _r_ and 0 ≤ _r_ \< _|d|_ . The number _q_ is called the _[quotient](https://en.wikipedia.org/wiki/Quotient)_ , while _r_ is called the _remainder_ .

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [November 11, 2019, 8:29am UTC](https://discourse.julialang.org/t/why-is-fld-a-b-so-much-slower-than-floor-a-b/30914/12 "2019-11-11T08:29:37Z")

</div>

I believe you should think of modular arithmetic as something that always wraps around into the same range (0 to something). Here, it is illustrated with a clock: [Modular arithmetic - Wikipedia](https://en.wikipedia.org/wiki/Modular_arithmetic) It would be strange to not coerce time to fall into the 12-to-12 (or even better, 0-24) range.

As far as I understand, the difference in sign behaviour is exactly what distinguishes `mod` from `rem`.