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

Я читаю Функциональное программирование на 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}

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

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)

random scala mod functional-programming
person Allen Han    schedule 31.10.2019    source источник
comment
Насколько я могу судить, это ничего не делает, потому что условие никогда не бывает ложным. Поскольку i гарантированно неотрицательно, а n предполагается положительно, это помещает mod в диапазон от нуля до n-1 включительно. Так что (n-1) - mod тоже неотрицательно. Таким образом, условие if всегда истинно.   -  person jwvh    schedule 31.10.2019

Ответы (2)


arrow_upward
0
arrow_downward

У меня точно такое же замешательство по поводу этого отрывка из книги Функциональное программирование в Scala. И я абсолютно согласен с анализом jwvh - утверждение if (i + (n-1) - mod >= 0) всегда будет истинным.

person Val Miscenko    schedule 20.05.2020

arrow_upward
0
arrow_downward

На самом деле, если вы попробуете тот же пример в Rust, компилятор предупредит об этом (просто интересное сравнение того, сколько делается статической проверки). Конечно, карандашный и бумажный подход jwvh — абсолютно правильный подход.

Сначала мы определяем некоторые псевдонимы типов, чтобы сделать код более похожим на код Scala (простите мой Rust, если он не совсем идиоматичен).

pub type RNGType = Box<dyn RNG>;
pub type Rand<A> = Box<dyn Fn(RNGType) -> (A, RNGType)>;

pub fn non_negative_less_than_(n: u32) -> Rand<u32> {
    let t = move |rng: RNGType| {
        let (i, rng2) = non_negative_int(rng);
        let rem = i % n;
        if i + (n - 1) - rem >= 0 {
            (rem, rng2)
        } else {
            non_negative_less_than(n)(rng2)
        }
    };

    Box::new(t)
}

Предупреждение компилятора относительно if nn + (n - 1) - rem >= 0:

warning: comparison is useless due to type limits
person Ahmed Riza    schedule 09.02.2021