How to randomize booleans in bulk

Question

I want to randomize 10,000 booleans in pure swift and get the sum of all those that are true.

score 3 · Accepted Answer · edited May 23 '17 at 11:43

A sum can be conveniently computed with the reduce() function:

/// Return the result of repeatedly calling `combine` with an
/// accumulated value initialized to `initial` and each element of
/// `sequence`, in turn.
func reduce<S : SequenceType, U>(sequence: S, initial: U, combine: (U, S.Generator.Element) -> U) -> U

If you are only interested in the sum:

let sum = reduce(0 ..< 10000, 0) { (sum, _) in sum + Int(arc4random_uniform(2)) }

If you need the Bool array and the sum:

let bools = map (0 ..< 10000) { _ in arc4random_uniform(2) == 1 }
let sum = reduce(bools, 0) { $0 + Int($1) }

Update: As Zaph suggested below, one should utilize all 32 bits from the arc4random... functions to reduce the number of function calls. This would be

let numberOfInt32 = 10000 / 32
let remainingBits = 10000 % 32

let sum = reduce(0 ..< numberOfInt32, 0) { (sum, _) in sum + NumberOfSetBits(arc4random()) }
    + NumberOfSetBits(arc4random_uniform(UInt32(1 << remainingBits)))

where NumberOfSetBits() counts the number of set bits and is a translation of https://stackoverflow.com/a/109025/1187415 to Swift:

func NumberOfSetBits(var i : UInt32) -> Int {
    i = i - ((i >> 1) & 0x55555555)
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
    return Int((((i + (i >> 4)) & 0x0F0F0F0F) &* 0x01010101) >> 24)
}

(See also Rikkle's answer which was posted in the mean time ...)

There remains one issue, 10,000 calls to arc4random_uniform in a short time may well overwhelm the capabilities to produce cryptographically random numbers. Just using arc4random() and using all 32-bits would help avoid this potential problem by reducing the calls by a factor of 32. — zaph, Mar 23 '15 at 15:25
@Zaph: thanks for the feedback, I have tried to implement your suggestion. For the sum of 10.000 random bits, it reduces the time from 8ms to approx 0.3ms on my computer. Using arc4random_buf as Rikkle suggested in his answer might even be faster. — Martin R, Mar 23 '15 at 16:19

Miknash · Answer 2 · 2015-03-23T15:32:00.087

2

If you don't need to save your booleand

var sum = 0
for i in 1...10000{
   if(arc4random_uniform(2) == 1)
      sum++
}

If you do want to save them

var sum = 0
var boolArrays = []
for i in 1...10000{
   if(arc4random_uniform(2) == 1){
      sum++
      boolArray.addObject(true)
   }
   else{
       boolArray.addObject(false)
   }
}

edited Mar 23 '15 at 15:32

answered Mar 23 '15 at 15:16

Miknash

7,888
3
34
46

1

Do not use `random()` it is not random, instead use `arc4random()` or in this case `arc4random_uniform(2)`. Further, `random()` without a seed will repeat each tie the program is run. – zaph Mar 23 '15 at 15:18
forgot to remove it, arc4random)uniform(n) will create random number in range of 0 to n-1. Thanks again – Miknash Mar 23 '15 at 15:23
1

Correct me if I'm wrong: it must be: "for i in 1...10000" ? – Duyen-Hoa Mar 23 '15 at 15:30

score 2 · Answer 3 · edited May 23 '17 at 11:43

2

I would suggest using arc4random_buf on a 10,000/8 number of bytes, then applying the sideways addition (or "Hamming Weight") to sum up all the bits in that series of bytes, one int (32 bits) at a time. See https://stackoverflow.com/a/109025/1401029 for good pseudo code of the Hamming Weight.

This should be significantly faster and cleaner than any looping construct that includes a random function inside it.

edited May 23 '17 at 11:43

Community

1
1

answered Mar 23 '15 at 15:43

Rikkles

3,372
1
18
24

After reading your answer I also assumed that calling arc4random_buf() once (on a buffer of size 10,000/8) is faster than calling arc4random() 10,000/32 times. I made a simple benchmark now and interestingly, it turned out that there is almost no difference in the timing. – Martin R Mar 23 '15 at 18:28
Interesting! So the buffer version mosty loops throught the int32 version. Still though, both are probably much faster than doing arc4random_uniform() to get a 0/1 value on each bit. – Rikkles Mar 23 '15 at 18:31
Oh I just saw your comment above that drops the time by 25x between the bit and the word. Good :) – Rikkles Mar 23 '15 at 18:32
Actually that comparison was done in Debug mode. In Release mode and with Swift 1.2 the difference is 24ms vs 0.8 ms for 1,000,000 bits. – Martin R Mar 23 '15 at 18:34
And I do hope that you believe me that I did not copy your ideas. I started working on the improved version after receiving Zaph's comment and found the same NumberOfSetBits() function. I saw (and upvoted) your answer only when my improved code was ready to be posted. – Martin R Mar 23 '15 at 18:41
No worries. I was surprised everyone was suggesting getting a horribly inefficient random bit every time. – Rikkles Mar 23 '15 at 18:43

score 1 · Answer 4 · answered Mar 23 '15 at 15:23

arc4random_uniform() will return a uniformly distributed random number less than upper_bound.

var countTrue : Int = 0
var countFalse : Int = 0
for i in 1 ... 10000 {
    if (arc4random_uniform(2) == 1) {
         countTrue++
    } else {
         countFalse++
    }
}

NSLog("count true: \(countTrue), count false: \(countFalse)")

score 0 · Answer 5 · answered Mar 24 '15 at 01:25

If you don't need the actual Booleans, the sum has a binomial distribution with N=10000 and p=1/2. For that large an N, it's pretty much indistinguishable from a Gaussian with a mean of N*p and a variance of N*p*(1-p) (which corresponds to a standard deviation of 50), rounded to the nearest integer. You can generate standard normals using the Box-Muller method, and scale as follows:

import Cocoa

let uniform_denom = UInt32(RAND_MAX) + 1

func u0_1() -> Double {
  var num = arc4random_uniform(uniform_denom)
  return Double(num) / Double(uniform_denom)
}

func gaussian() -> (Double, Double) {
  var d = sqrt(-2.0 * log(u0_1()))
  var theta = 2.0 * M_PI * u0_1()
  return (d * cos(theta), d * sin(theta))  // 2-tuple of std normals
}

var sum = 5000 + Int(round(50.0 * gaussian().0))  // scale to mean = 5000, std-dev = 50

How to randomize booleans in bulk

5 Answers5