Как найти наибольшее кратное n, которое помещается в 32-разрядное целое число - PullRequest
Новая
       71

Как найти наибольшее кратное n, которое помещается в 32-разрядное целое число

2 голосов
/ 31 октября 2019

Я читаю Функциональное программирование в Scala и у меня возникают проблемы с пониманием фрагмента кода. Я проверил ошибки в книге, и в данном отрывке нет опечатки. (На самом деле, он имеет опечатку, но опечатка не влияет на код, о котором у меня есть вопрос.)

В рассматриваемом коде вычисляется псевдослучайное неотрицательное целое число, которое меньше некотороговерхняя граница. Функция, которая делает это, называется nonNegativeLessThan. 

trait RNG {
  def nextInt: (Int, RNG) // Should generate a random `Int`. 
}

case class Simple(seed: Long) extends RNG {
  def nextInt: (Int, RNG) = {
    val newSeed = (seed * 0x5DEECE66DL + 0xBL) & 0xFFFFFFFFFFFFL // `&` is bitwise AND. We use the current seed to generate a new seed.
    val nextRNG = Simple(newSeed) // The next state, which is an `RNG` instance created from the new seed.
    val n = (newSeed >>> 16).toInt // `>>>` is right binary shift with zero fill. The value `n` is our new pseudo-random integer.
    (n, nextRNG) // The return value is a tuple containing both a pseudo-random integer and the next `RNG` state.
  }
}

type Rand[+A] = RNG => (A, RNG)

def nonNegativeInt(rng: RNG): (Int, RNG) = {
  val (i, r) = rng.nextInt
  (if (i < 0) -(i + 1) else i, r)
}

def nonNegativeLessThan(n: Int): Rand[Int] = { rng =>
  val (i, rng2) = nonNegativeInt(rng)
  val mod = i % n
  if (i + (n-1) - mod >= 0) (mod, rng2)
  else nonNegativeLessThan(n)(rng2)
}

У меня проблемы с пониманием следующего кода в nonNegativeLessThan, который выглядит следующим образом: if (i + (n-1) - mod >= 0) (mod, rng2) и т. Д.

Книгаобъясняет, что все это выражение if-else необходимо, потому что наивная реализация, которая просто принимает мод результата nonNegativeInt, будет слегка перекошена в сторону более низких значений, поскольку Int.MaxValue не гарантируется, чтобы быть кратным n. Следовательно, этот код предназначен для проверки того, будет ли сгенерированный вывод nonNegativeInt больше, чем наибольшее кратное n, которое помещается в 32-битное значение. Если сгенерированное число больше, чем наибольшее кратное n, которое помещается в 32-битное значение, функция пересчитывает псевдослучайное число.

Чтобы уточнить, наивная реализация будет выглядеть следующим образом: 

def naiveNonNegativeLessThan(n: Int): Rand[Int] = map(nonNegativeInt){_ % n}

где map определяется следующим образом 

def map[A,B](s: Rand[A])(f: A => B): Rand[B] = {
  rng => 
    val (a, rng2) = s(rng)
    (f(a), rng2)
}

Повторим, эта наивная реализация нежелательна из-за небольшого отклонения в сторону более низких значений, когда Int.MaxValue не является идеальным кратным n.

Итак, еще раз повторю вопрос: что делает следующий код и как он помогает нам определить, меньше ли число, чем наибольшее кратное n, которое помещается в 32-битное целое число? Я говорю об этом коде внутри nonNegativeLessThan: 

if (i + (n-1) - mod >= 0) (mod, rng2)
else nonNegativeLessThan(n)(rng2)
...