Arc4random_uniform on Linux is missing from Foundation?

linux

(Edward Connell) #1

Any ideas when Foundation on Linux will support arc4random_uniform? This is
kind of an important function.
There doesn't seem to be any decent substitute without requiring the
installation of libbsd-dev, which turns out to be messy. Currently I am
doing this, but glibc random with mod does not produce good quality
numbers, due to modulo bias.

Has anyone come up with a better solution to get a true uniform
distribution that isn't super messy?

import Foundation

#if os(Linux)
import Glibc
#endif

public func random_uniform(range: Int) -> Int {
guard range > 0 else { return 0 }
#if os(Linux)
return Int(random()) % range
#else
return Int(arc4random_uniform(UInt32(range)))
#endif
}

Thanks, Ed


(Philippe Hausler) #2

arc4random_uniform is from Darwin not Foundation - it just happens to be in a header we import when you import Foundation.

···

On May 22, 2017, at 8:44 AM, Edward Connell via swift-users <swift-users@swift.org> wrote:

Any ideas when Foundation on Linux will support arc4random_uniform? This is kind of an important function.
There doesn't seem to be any decent substitute without requiring the installation of libbsd-dev, which turns out to be messy. Currently I am doing this, but glibc random with mod does not produce good quality numbers, due to modulo bias.

Has anyone come up with a better solution to get a true uniform distribution that isn't super messy?

import Foundation

#if os(Linux)
  import Glibc
#endif

public func random_uniform(range: Int) -> Int {
  guard range > 0 else { return 0 }
  #if os(Linux)
    return Int(random()) % range
  #else
    return Int(arc4random_uniform(UInt32(range)))
  #endif
}

Thanks, Ed
_______________________________________________
swift-users mailing list
swift-users@swift.org
https://lists.swift.org/mailman/listinfo/swift-users


(Daniel Dunbar) #3

This function isn't something which comes with Foundation, it is supplied by the BSD libraries on Darwin, but those aren't present on Linux.

I recommend looking for a Swift implementation of a high-quality RNG which will meet your needs, rather than trying to rely on a non-portable implementation coming from the base OS.

- Daniel

···

On May 22, 2017, at 8:44 AM, Edward Connell via swift-users <swift-users@swift.org> wrote:

Any ideas when Foundation on Linux will support arc4random_uniform? This is kind of an important function.
There doesn't seem to be any decent substitute without requiring the installation of libbsd-dev, which turns out to be messy. Currently I am doing this, but glibc random with mod does not produce good quality numbers, due to modulo bias.

Has anyone come up with a better solution to get a true uniform distribution that isn't super messy?

import Foundation

#if os(Linux)
  import Glibc
#endif

public func random_uniform(range: Int) -> Int {
  guard range > 0 else { return 0 }
  #if os(Linux)
    return Int(random()) % range
  #else
    return Int(arc4random_uniform(UInt32(range)))
  #endif
}

Thanks, Ed
_______________________________________________
swift-users mailing list
swift-users@swift.org
https://lists.swift.org/mailman/listinfo/swift-users


(Saagar Jha) #4

Saagar Jha

Any ideas when Foundation on Linux will support arc4random_uniform? This is kind of an important function.
There doesn't seem to be any decent substitute without requiring the installation of libbsd-dev, which turns out to be messy. Currently I am doing this, but glibc random with mod does not produce good quality numbers, due to modulo bias.

Modulo bias is easy to deal with, though, if you force random to produce a range that is a multiple of the range that you’re trying to produce:

guard range > 0 else { return 0 }
var random: Int
repeat {
  random = Int(random())
} while(random > LONG_MAX / range * range)
return random % range

···

On May 22, 2017, at 08:44, Edward Connell via swift-users <swift-users@swift.org> wrote:

Has anyone come up with a better solution to get a true uniform distribution that isn't super messy?

import Foundation

#if os(Linux)
  import Glibc
#endif

public func random_uniform(range: Int) -> Int {
  guard range > 0 else { return 0 }
  #if os(Linux)
    return Int(random()) % range
  #else
    return Int(arc4random_uniform(UInt32(range)))
  #endif
}

Thanks, Ed
_______________________________________________
swift-users mailing list
swift-users@swift.org
https://lists.swift.org/mailman/listinfo/swift-users


(Jens Persson) #5

Check out the generators (especially xoroshiro) on this site:

···

On Mon, May 22, 2017 at 6:54 PM, Saagar Jha via swift-users < swift-users@swift.org> wrote:

Saagar Jha

On May 22, 2017, at 08:44, Edward Connell via swift-users < > swift-users@swift.org> wrote:

Any ideas when Foundation on Linux will support arc4random_uniform? This
is kind of an important function.
There doesn't seem to be any decent substitute without requiring the
installation of libbsd-dev, which turns out to be messy. Currently I am
doing this, but glibc random with mod does not produce good quality
numbers, due to modulo bias.

Modulo bias is easy to deal with, though, if you force random to produce a
range that is a multiple of the range that you’re trying to produce:

guard range > 0 else { return 0 }
var random: Int
repeat {
random = Int(random())
} while(random > LONG_MAX / range * range)
return random % range

Has anyone come up with a better solution to get a true uniform
distribution that isn't super messy?

import Foundation

#if os(Linux)
import Glibc
#endif

public func random_uniform(range: Int) -> Int {
guard range > 0 else { return 0 }
#if os(Linux)
return Int(random()) % range
#else
return Int(arc4random_uniform(UInt32(range)))
#endif
}

Thanks, Ed
_______________________________________________
swift-users mailing list
swift-users@swift.org
https://lists.swift.org/mailman/listinfo/swift-users

_______________________________________________
swift-users mailing list
swift-users@swift.org
https://lists.swift.org/mailman/listinfo/swift-users


(Jens Persson) #6

Sorry for the premature send ...
Here is the site: http://xoroshiro.di.unimi.it
There is also a section there about "generating uniform doubles in unit
interval" which is worth reading.
And here's how to get uniform floating point values in the range [0, 1)
from various (supposedly) random bit patterns:

extension Double {

    init(unitRange v: UInt64) {

        let shifts: UInt64 = 63 - UInt64(Double.significandBitCount)

        self = Double(v >> shifts) * (.ulpOfOne/2)

    }

    init(unitRange v: UInt32) {

        self = (Double(v) + 0.5) / (Double(UInt32.max) + 1.0)

    }

    init(unitRange v: UInt16) {

        self = (Double(v) + 0.5) / (Double(UInt16.max) + 1.0)

    }

    init(unitRange v: UInt8) {

        self = (Double(v) + 0.5) / (Double(UInt8.max) + 1.0)

    }

}

extension Float {

    init(unitRange v: UInt64) {

        let shifts: UInt64 = 63 - UInt64(Float.significandBitCount)

        self = Float(v >> shifts) * (.ulpOfOne/2)

    }

    init(unitRange v: UInt32) {

        let shifts: UInt32 = 31 - UInt32(Float.significandBitCount)

        self = Float(v >> shifts) * (.ulpOfOne/2)

    }

    init(unitRange v: UInt16) {

        let a = Float(v) + 0.5

        let b = Float(UInt16.max) + 1.0

        self = a / b

    }

    init(unitRange v: UInt8) {

        let a = Float(v) + 0.5

        let b = Float(UInt8.max) + 1.0

        self = a / b

    }

}

You will get a very fast and good quality prng using xoroshiro, converting
to unit range floating point and then back to uniform range int if you want
to, much much faster than arc4random.

/Jens

···

On Mon, May 22, 2017 at 11:17 PM, Jens Persson <jens@bitcycle.com> wrote:

Check out the generators (especially xoroshiro) on this site:

On Mon, May 22, 2017 at 6:54 PM, Saagar Jha via swift-users < > swift-users@swift.org> wrote:

Saagar Jha

On May 22, 2017, at 08:44, Edward Connell via swift-users < >> swift-users@swift.org> wrote:

Any ideas when Foundation on Linux will support arc4random_uniform? This
is kind of an important function.
There doesn't seem to be any decent substitute without requiring the
installation of libbsd-dev, which turns out to be messy. Currently I am
doing this, but glibc random with mod does not produce good quality
numbers, due to modulo bias.

Modulo bias is easy to deal with, though, if you force random to produce
a range that is a multiple of the range that you’re trying to produce:

guard range > 0 else { return 0 }
var random: Int
repeat {
random = Int(random())
} while(random > LONG_MAX / range * range)
return random % range

Has anyone come up with a better solution to get a true uniform
distribution that isn't super messy?

import Foundation

#if os(Linux)
import Glibc
#endif

public func random_uniform(range: Int) -> Int {
guard range > 0 else { return 0 }
#if os(Linux)
return Int(random()) % range
#else
return Int(arc4random_uniform(UInt32(range)))
#endif
}

Thanks, Ed
_______________________________________________
swift-users mailing list
swift-users@swift.org
https://lists.swift.org/mailman/listinfo/swift-users

_______________________________________________
swift-users mailing list
swift-users@swift.org
https://lists.swift.org/mailman/listinfo/swift-users


(Jens Persson) #7

Here's a stripped down verison of my implementation of the Xoroshiro128+
PRNG:
https://gist.github.com/anonymous/527602968812f853d6147aea8c66d660

/Jens

···

On Mon, May 22, 2017 at 11:21 PM, Jens Persson <jens@bitcycle.com> wrote:

Sorry for the premature send ...
Here is the site: http://xoroshiro.di.unimi.it
There is also a section there about "generating uniform doubles in unit
interval" which is worth reading.
And here's how to get uniform floating point values in the range [0, 1)
from various (supposedly) random bit patterns:

extension Double {

    init(unitRange v: UInt64) {

        let shifts: UInt64 = 63 - UInt64(Double.significandBitCount)

        self = Double(v >> shifts) * (.ulpOfOne/2)

    }

    init(unitRange v: UInt32) {

        self = (Double(v) + 0.5) / (Double(UInt32.max) + 1.0)

    }

    init(unitRange v: UInt16) {

        self = (Double(v) + 0.5) / (Double(UInt16.max) + 1.0)

    }

    init(unitRange v: UInt8) {

        self = (Double(v) + 0.5) / (Double(UInt8.max) + 1.0)

    }

}

extension Float {

    init(unitRange v: UInt64) {

        let shifts: UInt64 = 63 - UInt64(Float.significandBitCount)

        self = Float(v >> shifts) * (.ulpOfOne/2)

    }

    init(unitRange v: UInt32) {

        let shifts: UInt32 = 31 - UInt32(Float.significandBitCount)

        self = Float(v >> shifts) * (.ulpOfOne/2)

    }

    init(unitRange v: UInt16) {

        let a = Float(v) + 0.5

        let b = Float(UInt16.max) + 1.0

        self = a / b

    }

    init(unitRange v: UInt8) {

        let a = Float(v) + 0.5

        let b = Float(UInt8.max) + 1.0

        self = a / b

    }

}

You will get a very fast and good quality prng using xoroshiro, converting
to unit range floating point and then back to uniform range int if you want
to, much much faster than arc4random.

/Jens

On Mon, May 22, 2017 at 11:17 PM, Jens Persson <jens@bitcycle.com> wrote:

Check out the generators (especially xoroshiro) on this site:

On Mon, May 22, 2017 at 6:54 PM, Saagar Jha via swift-users < >> swift-users@swift.org> wrote:

Saagar Jha

On May 22, 2017, at 08:44, Edward Connell via swift-users < >>> swift-users@swift.org> wrote:

Any ideas when Foundation on Linux will support arc4random_uniform? This
is kind of an important function.
There doesn't seem to be any decent substitute without requiring the
installation of libbsd-dev, which turns out to be messy. Currently I am
doing this, but glibc random with mod does not produce good quality
numbers, due to modulo bias.

Modulo bias is easy to deal with, though, if you force random to produce
a range that is a multiple of the range that you’re trying to produce:

guard range > 0 else { return 0 }
var random: Int
repeat {
random = Int(random())
} while(random > LONG_MAX / range * range)
return random % range

Has anyone come up with a better solution to get a true uniform
distribution that isn't super messy?

import Foundation

#if os(Linux)
import Glibc
#endif

public func random_uniform(range: Int) -> Int {
guard range > 0 else { return 0 }
#if os(Linux)
return Int(random()) % range
#else
return Int(arc4random_uniform(UInt32(range)))
#endif
}

Thanks, Ed
_______________________________________________
swift-users mailing list
swift-users@swift.org
https://lists.swift.org/mailman/listinfo/swift-users

_______________________________________________
swift-users mailing list
swift-users@swift.org
https://lists.swift.org/mailman/listinfo/swift-users


(Edward Connell) #8

Thank you for all the feedback and options. In further investigation, I
also ran across the family of xx48 rngs, which appear to be on both
platforms. They claim to be uniformly distributed.

drand48, erand48, jrand48, lcong48, lrand48, mrand48, nrand48, seed48,
srand48

http://pubs.opengroup.org/onlinepubs/007908775/xsh/drand48.html

Any reason not to use one of these instead?

Thanks, Ed

···

On Tue, May 23, 2017 at 3:18 AM, Jens Persson <jens@bitcycle.com> wrote:

Here's a stripped down verison of my implementation of the Xoroshiro128+
PRNG:
https://gist.github.com/anonymous/527602968812f853d6147aea8c66d660

/Jens

On Mon, May 22, 2017 at 11:21 PM, Jens Persson <jens@bitcycle.com> wrote:

Sorry for the premature send ...
Here is the site: http://xoroshiro.di.unimi.it
There is also a section there about "generating uniform doubles in unit
interval" which is worth reading.
And here's how to get uniform floating point values in the range [0, 1)
from various (supposedly) random bit patterns:

extension Double {

    init(unitRange v: UInt64) {

        let shifts: UInt64 = 63 - UInt64(Double.significandBitCount)

        self = Double(v >> shifts) * (.ulpOfOne/2)

    }

    init(unitRange v: UInt32) {

        self = (Double(v) + 0.5) / (Double(UInt32.max) + 1.0)

    }

    init(unitRange v: UInt16) {

        self = (Double(v) + 0.5) / (Double(UInt16.max) + 1.0)

    }

    init(unitRange v: UInt8) {

        self = (Double(v) + 0.5) / (Double(UInt8.max) + 1.0)

    }

}

extension Float {

    init(unitRange v: UInt64) {

        let shifts: UInt64 = 63 - UInt64(Float.significandBitCount)

        self = Float(v >> shifts) * (.ulpOfOne/2)

    }

    init(unitRange v: UInt32) {

        let shifts: UInt32 = 31 - UInt32(Float.significandBitCount)

        self = Float(v >> shifts) * (.ulpOfOne/2)

    }

    init(unitRange v: UInt16) {

        let a = Float(v) + 0.5

        let b = Float(UInt16.max) + 1.0

        self = a / b

    }

    init(unitRange v: UInt8) {

        let a = Float(v) + 0.5

        let b = Float(UInt8.max) + 1.0

        self = a / b

    }

}

You will get a very fast and good quality prng using xoroshiro,
converting to unit range floating point and then back to uniform range int
if you want to, much much faster than arc4random.

/Jens

On Mon, May 22, 2017 at 11:17 PM, Jens Persson <jens@bitcycle.com> wrote:

Check out the generators (especially xoroshiro) on this site:

On Mon, May 22, 2017 at 6:54 PM, Saagar Jha via swift-users < >>> swift-users@swift.org> wrote:

Saagar Jha

On May 22, 2017, at 08:44, Edward Connell via swift-users < >>>> swift-users@swift.org> wrote:

Any ideas when Foundation on Linux will support arc4random_uniform?
This is kind of an important function.
There doesn't seem to be any decent substitute without requiring the
installation of libbsd-dev, which turns out to be messy. Currently I am
doing this, but glibc random with mod does not produce good quality
numbers, due to modulo bias.

Modulo bias is easy to deal with, though, if you force random to
produce a range that is a multiple of the range that you’re trying to
produce:

guard range > 0 else { return 0 }
var random: Int
repeat {
random = Int(random())
} while(random > LONG_MAX / range * range)
return random % range

Has anyone come up with a better solution to get a true uniform
distribution that isn't super messy?

import Foundation

#if os(Linux)
import Glibc
#endif

public func random_uniform(range: Int) -> Int {
guard range > 0 else { return 0 }
#if os(Linux)
return Int(random()) % range
#else
return Int(arc4random_uniform(UInt32(range)))
#endif
}

Thanks, Ed
_______________________________________________
swift-users mailing list
swift-users@swift.org
https://lists.swift.org/mailman/listinfo/swift-users

_______________________________________________
swift-users mailing list
swift-users@swift.org
https://lists.swift.org/mailman/listinfo/swift-users


(Saagar Jha) #9

drand48 is a small LCG and I think it also needs to be seeded before you use it with srand48; otherwise it’ll give the same sequence each time.

Saagar Jha

···

On May 24, 2017, at 08:15, Edward Connell <ewconnell@gmail.com> wrote:

Thank you for all the feedback and options. In further investigation, I also ran across the family of xx48 rngs, which appear to be on both platforms. They claim to be uniformly distributed.

drand48, erand48, jrand48, lcong48, lrand48, mrand48, nrand48, seed48, srand48

http://pubs.opengroup.org/onlinepubs/007908775/xsh/drand48.html

Any reason not to use one of these instead?

Thanks, Ed

On Tue, May 23, 2017 at 3:18 AM, Jens Persson <jens@bitcycle.com <mailto:jens@bitcycle.com>> wrote:
Here's a stripped down verison of my implementation of the Xoroshiro128+ PRNG:
https://gist.github.com/anonymous/527602968812f853d6147aea8c66d660

/Jens

On Mon, May 22, 2017 at 11:21 PM, Jens Persson <jens@bitcycle.com <mailto:jens@bitcycle.com>> wrote:
Sorry for the premature send ...
Here is the site: http://xoroshiro.di.unimi.it <http://xoroshiro.di.unimi.it/>
There is also a section there about "generating uniform doubles in unit interval" which is worth reading.
And here's how to get uniform floating point values in the range [0, 1) from various (supposedly) random bit patterns:
extension Double {
    init(unitRange v: UInt64) {
        let shifts: UInt64 = 63 - UInt64(Double.significandBitCount)
        self = Double(v >> shifts) * (.ulpOfOne/2)
    }
    init(unitRange v: UInt32) {
        self = (Double(v) + 0.5) / (Double(UInt32.max) + 1.0)
    }
    init(unitRange v: UInt16) {
        self = (Double(v) + 0.5) / (Double(UInt16.max) + 1.0)
    }
    init(unitRange v: UInt8) {
        self = (Double(v) + 0.5) / (Double(UInt8.max) + 1.0)
    }
}
extension Float {
    init(unitRange v: UInt64) {
        let shifts: UInt64 = 63 - UInt64(Float.significandBitCount)
        self = Float(v >> shifts) * (.ulpOfOne/2)
    }
    init(unitRange v: UInt32) {
        let shifts: UInt32 = 31 - UInt32(Float.significandBitCount)
        self = Float(v >> shifts) * (.ulpOfOne/2)
    }
    init(unitRange v: UInt16) {
        let a = Float(v) + 0.5
        let b = Float(UInt16.max) + 1.0
        self = a / b
    }
    init(unitRange v: UInt8) {
        let a = Float(v) + 0.5
        let b = Float(UInt8.max) + 1.0
        self = a / b
    }
}

You will get a very fast and good quality prng using xoroshiro, converting to unit range floating point and then back to uniform range int if you want to, much much faster than arc4random.

/Jens

On Mon, May 22, 2017 at 11:17 PM, Jens Persson <jens@bitcycle.com <mailto:jens@bitcycle.com>> wrote:
Check out the generators (especially xoroshiro) on this site:

On Mon, May 22, 2017 at 6:54 PM, Saagar Jha via swift-users <swift-users@swift.org <mailto:swift-users@swift.org>> wrote:

Saagar Jha

On May 22, 2017, at 08:44, Edward Connell via swift-users <swift-users@swift.org <mailto:swift-users@swift.org>> wrote:

Any ideas when Foundation on Linux will support arc4random_uniform? This is kind of an important function.
There doesn't seem to be any decent substitute without requiring the installation of libbsd-dev, which turns out to be messy. Currently I am doing this, but glibc random with mod does not produce good quality numbers, due to modulo bias.

Modulo bias is easy to deal with, though, if you force random to produce a range that is a multiple of the range that you’re trying to produce:

guard range > 0 else { return 0 }
var random: Int
repeat {
  random = Int(random())
} while(random > LONG_MAX / range * range)
return random % range

Has anyone come up with a better solution to get a true uniform distribution that isn't super messy?

import Foundation

#if os(Linux)
  import Glibc
#endif

public func random_uniform(range: Int) -> Int {
  guard range > 0 else { return 0 }
  #if os(Linux)
    return Int(random()) % range
  #else
    return Int(arc4random_uniform(UInt32(range)))
  #endif
}

Thanks, Ed
_______________________________________________
swift-users mailing list
swift-users@swift.org <mailto:swift-users@swift.org>
https://lists.swift.org/mailman/listinfo/swift-users

_______________________________________________
swift-users mailing list
swift-users@swift.org <mailto:swift-users@swift.org>
https://lists.swift.org/mailman/listinfo/swift-users