Arithmetics with std:: num:: wrapping ::Wrapping


#1

Hello,
I don’t understand why t has an unexpected value.

fn main() {
    use std::num::Wrapping;
    let r = Wrapping(16807);
    let s = r * r; // s = 282475249;
    let t = r * s; // t = 1622647863; // instead of 1622650073
    println!("{} {} {}", r, s, t);
}

#2

C:

#include <stdio.h>

int main() {
    unsigned int r = 16807;
    unsigned int s = r * r;
    unsigned int t = r * s;

    printf("%d %d %d\n", r, s, t);
}

Outputs:

16807 282475249 1622647863

Python:

r = 16807
s = (r * r) & (2**32-1)
t = (r * s) & (2**32-1)
print(r, s, t)

Outputs:

16807 282475249 1622647863

The question is: why do you believe t should be 1622650073?


#3

I am trying to implement the GLIBC random number generator from https://www.mathstat.dal.ca/~selinger/random/ .


#4

But that doesn’t use wrapping arithmetic.


#5

I made this

use std::mem;
use std::num::Wrapping;
static mut seed: i32 = 1;
static mut index: usize = 344;
static mut r: Vec<i32> = unsafe { mem::uninitialized() };
fn srand(new_seed: i32) {
    unsafe {
	index = 344;
	r = Vec::with_capacity(344);
	for _ in 0..344 {
	    r.push(0);
	}
	r[0] = new_seed;
	for i in 1..31 {
		r[i] = (Wrapping(16807) * Wrapping(r[i - 1]) % Wrapping(i32::max_value())).0;
		println!("wrapping {} {} {}", i, (Wrapping(16807) * Wrapping(r[i - 1])) % Wrapping(i32::max_value()), (Wrapping(16807) * Wrapping(r[i - 1])));
		if r[i] < 0 {
			r[i] += i32::max_value();
		}
	}
	for i in 31..34 {
		r[i] = r[i - 31];
	}
	for i in 34..344 {
		r[i] = (Wrapping(r[i - 31]) + Wrapping(r[i - 3])).0;
	}
}}

fn rand() -> i32 {unsafe {
    seed = (Wrapping(r[index - 31]) + Wrapping(r[index - 3])).0;
    r.push(seed);
    index += 1;
    seed
}}

But it doesn’t work.


#6

But that’s my point: the original code doesn’t use wrapping. It’s also not using 32-bit integers. If you write different code, you’re going to get a different answer.

You need to go back and read the reference code more carefully. There’s even an explicit note about this:

Note that the multiplication by 16807 is done in a large enough signed integer type so that there is no overflow before the modulo operation.


#7

Note that 2147483647 is different to 2147483648. This is a mod operation, not bitwise and operation. You need to do % 2147483647, you cannot use wrapping, as this isn’t a power of 2.


#8

Thanks, I made the required changes.