我计算素数的 Rust 脚本似乎冻结在 16777213

Question

我是 Rust 语言的新手，我一直在做这个，这是我的第一个 Rust 项目，目的是更好地了解语言的工作原理。我有这段计算素数的代码，但每次达到值 16,777,213 时它都会停止。它不会恐慌，不会崩溃，只会冻结。 我找到了另一篇文章，其中有人在 C++ 中尝试了类似的事情并且遇到了同样的问题：Prime number generator stopps abruptly at 16777213 | StackOverflow，但似乎没有人回答如何修复它。

这是我的代码：

fn half(val: i128) -> bool { // For better precision (to prevent false positives in small numbers)
    let mut factors: Vec<i128> = vec![];
    for i in 1i128..(((val as f32)/2.0)+1.0) as i128 {
        let factor: f32 = (val as f32)/(i as f32);
        if factor == factor.round() {
                let factor:i128 = factor as i128;
                if factor != val {
                    factors.push(factor as i128)
                }
            }
        }
    if factors.is_empty() {
        return true
    } else {false}
}
fn root(val:i128) -> bool {
    let mut factors: Vec<i128> = vec![];
    for i in 1i128..((val as f32).sqrt().round()+1.0) as i128 {
        if val > 2 {
            let factor: f32 = (val as f32)/(i as f32);
            if factor == factor.round() {
                let factor: i128 = factor as i128;
                if factor != val {
                    factors.push(factor)
                }
            }
        }
    }
    if factors.is_empty() {
        return true
    } else {false}
}
fn is_prime(val:i128) -> bool {
    if val > 100 {
        root(val)
    }
    else {
        half(val)
    }
}
fn main() {
    //let mut primes: Vec<i128> = vec![];
    let mut i:i128 = 16_700_000;
    loop {
        let prime: bool = is_prime(i);
        if prime {
            println!("{}",i)
            /*
This was the original code, but I removed the vector so that I'd be able to
determine the exact value at which the script breaks at.
            primes.push(i);
            if primes.len() as i32 == 24 {
                println!("{:?}",primes);
                primes.clear()
            }*/
        }
        i += 1
    }
}

Answer 1

你必须用

f32

替换所有

f64

。我会尝试更深入地解释它，但现在发现这个修复问题。

首先为了简化，我们可以假设

if val > 100

始终为真，并从考虑中排除

half

功能。

现在我们可以重写程序以查看 f32 和 f64 版本之间的差异：

fn root_64(val:i128) -> bool {
    let mut factors: Vec<i128> = vec![];
    for i in 1i128..((val as f64).sqrt().round()+1.0) as i128 {
        if val > 2 {
            let factor: f64 = (val as f64)/(i as f64);
            if factor == factor.round() {
                let factor: i128 = factor as i128;
                if factor != val {
                    factors.push(factor)
                }
            }
        }
    }
    println!("F64 {} {:?}", val, factors);
    if factors.is_empty() {
        return true
    } else {false}
}

fn root_32(val:i128) -> bool {
    let mut factors: Vec<i128> = vec![];
    for i in 1i128..((val as f32).sqrt().round()+1.0) as i128 {
        if val > 2 {
            let factor: f32 = (val as f32)/(i as f32);
            if factor == factor.round() {
                let factor: i128 = factor as i128;
                if factor != val {
                    factors.push(factor)
                }
            }
        }
    }
    println!("F32 {} {:?}", val, factors);
    if factors.is_empty() {
        return true
    } else {false}
}

fn is_prime_64(val:i128) -> bool {
    if val > 100 {
        return root_64(val)
    };
    return false
}
fn is_prime_32(val:i128) -> bool {
    if val > 100 {
        return root_32(val)
    };
    return false
}
fn main() {
    //let mut primes: Vec<i128> = vec![];
    let mut i:i128 = 16_777_210;
    loop {
        let prime_32: bool = is_prime_32(i);
        let prime_64: bool = is_prime_64(i);
        if prime_32 || prime_64 {
            println!("{} 32:{} 64:{}",i, prime_32, prime_64)
        }
        i += 1;
        if i > 16_777_260 {
            break
        }
    }
}

我们可以看到最初的因素列表是相等的，但是对于

16777217

因素列表开始是不同的：

F32 16777210 [8388605, 3355442, 1677721]
F64 16777210 [8388605, 3355442, 1677721]

...

16777213 32:true 64:true

...

F32 16777217 [16777216, 8388608, 4194304, 2097152, 1048576, 524288, 262144, 131072, 65536, 32768, 16384, 8192, 4096]
F64 16777217 [172961, 65281, 24929]

我们可以注意到

16777217 / (2^24) = 1.0000000596

但是

16777216 / (2^24) = 1

所以让我们专注于从数字

16777217

计算正方形。

root_32方法找到的因子列表表明

16777217

比较接近

16777216

factor == factor.round()

其中

factor

是除法的结果

(val as f32)/(i as f32)

你甚至可以为它写测试

#[cfg(test)]
mod tests {
    #[test]
    fn it_works() {
        let result = 16777217 as f32 / 16777216 as f32;
        assert_eq!(result.round(), 1f32);
        assert_eq!(result, 1f32);
    }
}

如果您有兴趣为什么

2^24

对于这个近似值至关重要，您可以阅读有关

f32

结构

https://doc.rust-lang.org/std/primitive.f32.html

尤其是

pub const MANTISSA_DIGITS: u32 = 24u32
Number of significant digits in base 2.