rust - 为什么我不能将一个 BigInt 与另一个 BigInt 相除并将其保存到我已初始化为零的变量中？

Question

我有以下代码片段:

use num_bigint::*; // 0.2.2
use num_traits::*; // 0.2.8
use std::ops::*;

fn xgcd(b: &BigInt, a: &BigInt) -> (BigInt, BigInt, BigInt) {
    let mut x0: BigInt = One::one();
    let mut x1: BigInt = Zero::zero();
    let mut y0: BigInt = Zero::zero();
    let mut y1: BigInt = One::one();
    let mut q = 0;
    while a != Zero::zero() {
        q = b.div(a);
        b = a;
        a = &b.rem(a);
        x0 = x1;
        x1 = x0 - q * x1;
        y0 = y1;
        y1 = y0 - q * y1;
    }
    return (*b, x0, y0);
}

它给出了以下错误:

error[E0308]: mismatched types
  --> src/lib.rs:12:13
   |
12 |         q = b.div(a);
   |             ^^^^^^^^ expected integer, found struct `num_bigint::bigint::BigInt`
   |
   = note: expected type `{integer}`
              found type `num_bigint::bigint::BigInt`

我查阅了 num::BigInt 的文档它指出实际上有一个 div 方法以 BigInt 作为参数，但不知何故编译器决定不使用它而是告诉我我不能将 BigInt 与 BigInt 相除。有什么办法可以解决这个问题吗？

Answer 1

and instead tells me that I can't divide a BigInt with a BigInt

事实并非如此。它告诉您将两者相除的结果是一个BigInt，它需要一个{integer}。这是因为您的 q 变量已声明为整数，而不是 BigInt。因此，除法的结果必须是某种内置整数({integer})，但是除法的结果是BigInt一个 BigInt 是另一个 BigInt。

您在其他任何地方都使用了 Zero::zero，所以不清楚您为什么不在这里使用它。幸运的是，您不需要对其进行任何设置，因为无论如何您都不应该在进入循环之前对其进行初始化:

use num_bigint::*; // 0.2.2
use num_traits::*; // 0.2.8

fn xgcd(b: &BigInt, a: &BigInt) -> (BigInt, BigInt, BigInt) {
    let mut a = a.clone();
    let mut b = b.clone();
    let mut x0 = BigInt::one();
    let mut x1 = BigInt::zero();
    let mut y0 = BigInt::zero();
    let mut y1 = BigInt::one();

    while !a.is_zero() {
        let q = &b / &a;
        b = a.clone();
        a = &b % &a;
        x0 = x1.clone();
        x1 = &x0 - &q * x1;
        y0 = y1.clone();
        y1 = &y0 - &q * y1;
    }

    (b, x0, y0)
}

变化包括:

• 使用运算符形式代替方法名称(例如 / 与 div)。
• 添加了一些 .clone() 调用。我无法确保这些是可能的最小克隆数，因此请检查一下。
• 添加了一些&以防止在其他地方克隆。
• Zero::is_zero可以比创建值并比较它更快。
• 使用了 BigInt::zero() 的较短语法。

另见:

• How do I use integer number literals when using generic types?
• Cannot create a generic function that uses a literal zero
• Rust, compute gcd: modularity, references