# rand(1:10) vs Int(round(10\*rand())

**URL:** <https://discourse.julialang.org/t/rand-1-10-vs-int-round-10-rand/14339>\
**Category:** Performance\
**Created:** [August 30, 2018, 11:01pm UTC](https://discourse.julialang.org/t/rand-1-10-vs-int-round-10-rand/14339 "2018-08-30T23:01:31Z")\
**Posts on this page:** 18\
**Page:** 1

<div class="post-metadata">

**Author:** ![mbeach42](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mbeach42/32/5747_2.png) [@mbeach42](https://discourse.julialang.org/u/mbeach42)\
**Post date:** [August 30, 2018, 11:01pm UTC](https://discourse.julialang.org/t/rand-1-10-vs-int-round-10-rand/14339/1 "2018-08-30T23:01:31Z")

</div>

Why should I use rand(1:N) for an integer N, instead of Int.(round.(rand()\*N?)) On my computer, it seems that Int.(round.(rand()\*N?)) is about 3 times faster than rand(1:10).

---

<div class="post-metadata">

**Author:** ![mbauman](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mbauman/32/31082_2.png) [@mbauman](https://discourse.julialang.org/u/mbauman)\
**Post date:** [August 30, 2018, 11:12pm UTC](https://discourse.julialang.org/t/rand-1-10-vs-int-round-10-rand/14339/2 "2018-08-30T23:12:51Z")

</div>

- It’s more succinct
- It’s more obvious in terms of what it’s doing
- I trust Julia to make sure that `rand(1:N)` is bias-free. If your shortcut is indeed “safe,” then I’d imagine the RNG folks would be happy to implement that as the implementation for `rand(1:N)`, so that performance difference might disappear in the future.

---

<div class="post-metadata">

**Author:** ![rdeits](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rdeits/32/286_2.png) [@rdeits](https://discourse.julialang.org/u/rdeits)\
**Post date:** [August 30, 2018, 11:20pm UTC](https://discourse.julialang.org/t/rand-1-10-vs-int-round-10-rand/14339/3 "2018-08-30T23:20:07Z")

</div>

To that point, it turns out that `Int(round(rand() * N))` is definitely not bias-free:

 ![Screenshot%20from%202018-08-30%2019-19-56](https://global.discourse-cdn.com/julialang/original/3X/1/8/1840e25890a5466ad62318fe126ce3b270efedb2.png)

---

<div class="post-metadata">

**Author:** ![NiclasMattsson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/niclasmattsson/32/21988_2.png) [@NiclasMattsson](https://discourse.julialang.org/u/NiclasMattsson)\
**Post date:** [August 30, 2018, 11:34pm UTC](https://discourse.julialang.org/t/rand-1-10-vs-int-round-10-rand/14339/4 "2018-08-30T23:34:14Z")

</div>

Well, `1 + floor(Int, rand()*N))` should be bias free and indeed appears to be significantly faster than `rand(1:N)`. But the fact that OP seriously messed up the expression is a decent anecdotal argument for why people should usually use the simpler formulation anyway.

---

<div class="post-metadata">

**Author:** ![rickhg12hs](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rickhg12hs/32/5926_2.png) [@rickhg12hs](https://discourse.julialang.org/u/rickhg12hs)\
**Post date:** [August 31, 2018, 1:18am UTC](https://discourse.julialang.org/t/rand-1-10-vs-int-round-10-rand/14339/5 "2018-08-31T01:18:01Z")

</div>

Beautiful demonstration of the underlying fair uniformly distributed random number generator AND rounding intervals. 😆

---

<div class="post-metadata">

**Author:** ![greg\_plowman](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/greg_plowman/32/8100_2.png) [@greg\_plowman](https://discourse.julialang.org/u/greg_plowman)\
**Post date:** [August 31, 2018, 1:52am UTC](https://discourse.julialang.org/t/rand-1-10-vs-int-round-10-rand/14339/6 "2018-08-31T01:52:10Z")

</div>

Also see [random sampling from an (abstract)array is slow · Issue #20582 · JuliaLang/julia · GitHub](https://github.com/JuliaLang/julia/issues/20582)

---

<div class="post-metadata">

**Author:** ![mbeach42](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mbeach42/32/5747_2.png) [@mbeach42](https://discourse.julialang.org/u/mbeach42)\
**Post date:** [August 31, 2018, 6:27am UTC](https://discourse.julialang.org/t/rand-1-10-vs-int-round-10-rand/14339/7 "2018-08-31T06:27:17Z")

</div>

Yeah, Int(ceil(N\*rand())) is seems unbias and is much faster. My code is performance critical, so I need all the speed boosts I can get.

---

<div class="post-metadata">

**Author:** ![mschauer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mschauer/32/13946_2.png) [@mschauer](https://discourse.julialang.org/u/mschauer)\
**Post date:** [August 31, 2018, 6:58am UTC](https://discourse.julialang.org/t/rand-1-10-vs-int-round-10-rand/14339/8 "2018-08-31T06:58:47Z")

</div>

As long as `N` is not too big then the bias is very small. Biases become visible for big `N`, for example:

```julia
julia> N=10^16; M=10^6; mean(iseven(Int(ceil(N*rand()))) for i in 1:M)
0.549885

julia> N=10^16; M=10^6; mean(iseven(rand(1:N)) for i in 1:M)
0.500379

```

[@bkamins has corrected benchmarks]

---

<div class="post-metadata">

**Author:** ![bkamins](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bkamins/32/208538_2.png) [@bkamins](https://discourse.julialang.org/u/bkamins)\
**Post date:** [August 31, 2018, 7:34am UTC](https://discourse.julialang.org/t/rand-1-10-vs-int-round-10-rand/14339/9 "2018-08-31T07:34:21Z")

</div>

You might also have a look at this [Julia snippets: Basics of generating random numbers in Julia](https://juliasnippets.blogspot.com/2017/11/basics-of-generating-random-numbers-in.html) (it is Julia 0.6 based but the reasons for the bias have not changed).

Having said that for very small `N` in very tight loops I use the approximate formula as the bias is small and it is significantly faster (see the corrected benchmark below - also you have to use `1+floor` not `ceil` as `ceil` can produce `0`):

```julia
julia> f1(N=5,M=10^6) = mean(iseven(1+floor(Int, N*rand())) for i in 1:M)
f1 (generic function with 3 methods)

julia> f2(N=5,M=10^6) = mean(iseven(rand(1:N)) for i in 1:M)
f2 (generic function with 3 methods)

julia> @btime f1()
  9.020 ms (0 allocations: 0 bytes)
0.400145

julia> @btime f2()
  17.681 ms (0 allocations: 0 bytes)
0.399574

```

---

<div class="post-metadata">

**Author:** ![jlapeyre](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jlapeyre/32/4514_2.png) [@jlapeyre](https://discourse.julialang.org/u/jlapeyre)\
**Post date:** [September 1, 2018, 6:42pm UTC](https://discourse.julialang.org/t/rand-1-10-vs-int-round-10-rand/14339/10 "2018-09-01T18:42:53Z")

</div>

The algorithm here: [https://arxiv.org/abs/1805.10941](https://arxiv.org/abs/1805.10941)  
is faster and is claimed to be unbiased.

EDIT: (Skip this. Corrected and improved code is in my following post)

```julia
mytrunc(x) = UInt64((x << 64) >> 64)
function nearlydivisionless(s)
    x = rand(UInt64)
    m = convert(UInt128, x) * s
    l = mytrunc(m)
    if (l < s)
        t = -s % s
        while l < t
            x = rand(UInt64)
            m = convert(UInt128, x) * s
            l = mytrunc(m)
        end
    end
    return Int(m >> 64)
end

function biased(s)
    return floor(Int, rand() * s)
end

```

Benchmarks:

```julia
julia> @btime nearlydivisionless(10);
  7.042 ns (0 allocations: 0 bytes)

julia> @btime biased(10);
  5.188 ns (0 allocations: 0 bytes)

julia> @btime rand(0:9);
  12.698 ns (0 allocations: 0 bytes)

```

---

<div class="post-metadata">

**Author:** ![bkamins](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bkamins/32/208538_2.png) [@bkamins](https://discourse.julialang.org/u/bkamins)\
**Post date:** [September 1, 2018, 9:42pm UTC](https://discourse.julialang.org/t/rand-1-10-vs-int-round-10-rand/14339/11 "2018-09-01T21:42:33Z")

</div>

This is indeed very good. Additionally we can specialize the function for small `s` (fitting in `UInt32`) to gain even more speed in this case.

---

<div class="post-metadata">

**Author:** ![jlapeyre](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jlapeyre/32/4514_2.png) [@jlapeyre](https://discourse.julialang.org/u/jlapeyre)\
**Post date:** [September 1, 2018, 11:55pm UTC](https://discourse.julialang.org/t/rand-1-10-vs-int-round-10-rand/14339/12 "2018-09-01T23:55:52Z")

</div>

> [@bkamins](#):
>
> (fitting in `UInt32` ) to gain even more speed in this case.

Yes. In this case the new algorithm appears to be significantly faster than the biased algorithm:

```julia
@inline function drawl(s::Integer, maxval, T, T2)
    x = rand(T)
    m = convert(T2, x) * s
    l = m % maxval
    return (l, m)
end

@inline function _nearlydivisionless(s::Int32)
    nbits = 32
    __nearlydivisionless(s, UInt32, UInt64, UInt64(1) << nbits, nbits)
end

@inline function _nearlydivisionless(s::Int64)
    nbits = 64
    __nearlydivisionless(s, UInt64, UInt128, UInt128(1) << nbits, nbits)
end

function nearlydivisionless(s::Integer)
    if s < typemax(UInt32)
        s1 = Int32(s)
    else
        s1 = Int64(s)
    end
    _nearlydivisionless(s1)
end

@inline function __nearlydivisionless(s::Integer, T, T2, maxval, nbits)
    l, m = drawl(s, maxval, T, T2)
    if (l < s)
        t = maxval % s
        while l < t
            l, m = drawl(s, maxval, T, T2)
        end
    end
    return Int(m >> nbits)
end

biased(s) = floor(Int, rand() * s)

```

Here are the benchmarks:

The builtin function:

```julia
julia> @btime rand(0:99);
  9.358 ns (0 allocations: 0 bytes)

```

The biased algorithm:

```julia
julia> @btime biased(100);
  4.893 ns (0 allocations: 0 bytes)

```

The following function checks that `100 < typemax(UInt32)` and chooses the routine accordingly. In addtion, it’s a bit faster if the argument is `Int32(100)` rather than `100`.

```julia
julia> @btime nearlydivisionless(Int32(100));
  5.209 ns (0 allocations: 0 bytes)

```

Bypassing the check mentioned above is much faster. Much faster than the biased algorithm as well.

```julia
julia> @btime _nearlydivisionless(Int32(100));
  3.698 ns (0 allocations: 0 bytes)

```

These functions appear to work correctly now. The implementation above could no doubt be improved significantly.

If you read the paper, you’ll find that for n = 100, a single division is performed `2e-6` percent of the time. The other times, no division is performed.

I think choosing the routine based on whether `n < typemax(UInt32)` is not optimal. As `n` approaches the maximum value of the type, a single division is performed more often. This may kill the advantage of working with `UInt64` rather than `UInt128`.

---

<div class="post-metadata">

**Author:** ![KZiemian](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kziemian/32/9020_2.png) [@KZiemian](https://discourse.julialang.org/u/KZiemian)\
**Post date:** [September 15, 2018, 12:32pm UTC](https://discourse.julialang.org/t/rand-1-10-vs-int-round-10-rand/14339/13 "2018-09-15T12:32:38Z")

</div>

What is conclusion of the debate? Can be stated in few sentance?

---

<div class="post-metadata">

**Author:** ![mschauer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mschauer/32/13946_2.png) [@mschauer](https://discourse.julialang.org/u/mschauer)\
**Post date:** [September 15, 2018, 12:58pm UTC](https://discourse.julialang.org/t/rand-1-10-vs-int-round-10-rand/14339/14 "2018-09-15T12:58:34Z")

</div>

There is general interest in exploring the method from [https://arxiv.org/abs/1805.10941](https://arxiv.org/abs/1805.10941) for use in Julia. The following issue keeps track, though not so much has happened for now: [improve performance of `rand(n:m)` · Issue #29004 · JuliaLang/julia · GitHub](https://github.com/JuliaLang/julia/issues/29004)

---

<div class="post-metadata">

**Author:** ![KZiemian](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kziemian/32/9020_2.png) [@KZiemian](https://discourse.julialang.org/u/KZiemian)\
**Post date:** [September 15, 2018, 9:55pm UTC](https://discourse.julialang.org/t/rand-1-10-vs-int-round-10-rand/14339/15 "2018-09-15T21:55:48Z")

</div>

Thank you, that all I need to know.

---

<div class="post-metadata">

**Author:** ![y4lu](https://avatars.discourse-cdn.com/v4/letter/y/47e85d/32.png) [@y4lu](https://discourse.julialang.org/u/y4lu)\
**Post date:** [September 16, 2018, 9:50am UTC](https://discourse.julialang.org/t/rand-1-10-vs-int-round-10-rand/14339/16 "2018-09-16T09:50:03Z")

</div>

`*10^16` might be stretching the float 64 precision levels a bit, 70% integer numbers returned

```julia
julia> M= 10^6;
julia> x=0; for i in 1:M; global x;
  n = 10^16;
  n=n*rand();
  x=x+ ((n%1)==0.0);
  end; print(x);
700058
```

---

<div class="post-metadata">

**Author:** ![foobar\_lv2](https://avatars.discourse-cdn.com/v4/letter/f/ee59a6/32.png) [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)\
**Post date:** [September 16, 2018, 11:15am UTC](https://discourse.julialang.org/t/rand-1-10-vs-int-round-10-rand/14339/17 "2018-09-16T11:15:27Z")

</div>

> [@y4lu](#):
>
> `*10^16` might be stretching the float 64 precision levels a bit, 70% integer numbers returned

```julia
julia> 10^16 == Float64(10^16)
true

```

The problem is that `rand(Float64)` effectively generates random fixed-point numbers and then converts them to floats. See [https://discourse.julialang.org/t/output-distribution-of-rand/12192](https://discourse.julialang.org/t/output-distribution-of-rand/12192).

---

<div class="post-metadata">

**Author:** ![y4lu](https://avatars.discourse-cdn.com/v4/letter/y/47e85d/32.png) [@y4lu](https://discourse.julialang.org/u/y4lu)\
**Post date:** [September 18, 2018, 12:32am UTC](https://discourse.julialang.org/t/rand-1-10-vs-int-round-10-rand/14339/18 "2018-09-18T00:32:07Z")

</div>

Here’s another funny example

```julia
julia> 10^16 +1.0 == 10^16 -1.0
true

```