Dice, Probabilities and Go, part 1.5

Well, I had planned to write up a full second post right now about switching from using the recursive formula for calculating the probability of rolling some number from multiple dice to using binomial coefficients to avoid floating point math until the last step. However, Daniel Martin pointed out that with a very small change, I could push off the floating point calc to the very end.

Also, if you define N(s, n, k) == s^n * F(s,n,k), you get a nicer recursion relation: (in pseudo-python) 

N(s, 1, k) == 1 if 1 <= k <= s else 0 

N(s, n, k) == sum(N(s, n-1, k-i) for i in [1..s])

Can't argue with that logic. This is why code reviews are great! So I spent a little time getting that working and fast. Switching to integer math made it correct and adding memoization made it much faster.

  package main
  import (
    "fmt"
    "math"
  )

  func main() {
    printRolls_secondTry(6, 6)
  }

  func dieRolls_secondTryWithCache(sides, rolls, dieSum int,
      cache map[string] int64) int64 {
    cacheKey := fmt.Sprintf("%dd%d:%d", rolls, sides, dieSum)
    value, ok := cache[cacheKey]
    if ok {
      return value
    }

    if rolls == 1 {
      if dieSum >= 1 && dieSum <= sides {
        return 1
      } else {
        return 0
      }
    }

    sum := int64(0)

    for i := 1; i <= dieSum - rolls + 1; i++ {
      sum += dieRolls_secondTryWithCache(sides, 1, i, cache) *
          dieRolls_secondTryWithCache(sides, rolls - 1, dieSum - i, cache)
    }
    cache[cacheKey] = sum
    return sum
  }

  func printRolls_secondTry(sides, rolls int) {
    fmt.Printf("%dd%d rolls: \n", rolls, sides)

    maxValue := rolls * sides
    rollSequenceCount := math.Pow(float64(sides), float64(rolls))
    cache := make(map[string]int64)
    for value := rolls; value <= maxValue; value++ {
      valueRolls := float64(dieRolls_secondTryWithCache(
          sides, rolls, value, cache))
      fmt.Printf(" %3d  %8.5f%%\n", value,
         valueRolls / rollSequenceCount * 100)
    }
  }

On my Macbook Air, calculating 15d12 gave the right answer in less than 2 seconds. Without memoization I canceled it after 10 minutes. Better still, it can complete quickly when pasted into golang.org. Not a bad reward for such little effort!

Next time: calculating binomial coefficients and dealing with integer overflow.