[Rust] num-bigint と代数方程式の整数解

(ネタ) x ^ 3 + y ^ 3 + z ^ 3 = 42 の答えを見つけたチームがいるらしいのでJSのBigIntで確かめてみる

変な時間に寝たせいで変な時間に起きて寝つけないので, 上の記事の内容を Rust で試してみます. 本記事は実質的に num-bigint クレートの入門記事になっています.

問題

次の整数論の問題があります.

• $x^3 + y^3 + z^3 = 42$ を満足する整数の組 $( x, y, z )$ を求めよ.

オリジナルのニュース記事 (英語) は力技で解 $x = -80,538,738,812,075,974$, $y = 80,435,758,145,817,515$, $z = 12,602,123,297,335,631$ を発見したと報告するものです. この数字が本当に解になっているかをチェックすることがこの記事 (およびネタ元の記事) の主題です.

方針

単に三乗和を計算すればよいだけに見えますが, 数字が大きすぎるために i128 を用いても 桁数が足りません (2 乗までしか計算できない). こういうときは多倍長整数 (BigInt) の出番です. Rust では num-bigint クレートが提供されているので, これを使いましょう.

num-bigint クレートは BigInt と BigUint というふたつの型を提供します. これは整数を表すのに必要なだけのビットをヒープに動的に確保するもので, メモリが許す限り任意に大きな整数を扱うことができます. 計算速度は落ちますが.

実装と結果

num-bigint の詳しい使い方は ドキュメント 読むのが一番ですが, 簡単に説明しておきます.

num_bigint::BigInt は From<i32> や From<i128> 等を実装しているので, BigInt インスタンスを確保する場合はこれを用いて変換するのが一番楽だと思います. BigInt::from(1024) とか 1024.into() とか. FromStr でもあるので, 文字列表現のパースも可能です. ドキュメントに載っている BigInt::new() などのメソッドは整数のバイナリ表現からインスタンスを確保するものなので, 多くの場合あまり実用的ではないと思います.

四則演算 (Add など) は既に実装されているので普通に計算できます. ただし BigInt は Copy でないことに気をつける必要があります. また, べき乗 pow は num-traits クレートのトレイトとして実装されているので, べき乗を使う場合はそれを use しておく必要があります.

ちなみに BigInt は Default + Debug + Display + Clone + Eq + Ord + Hash です. 他に num-traits のトレイトでは Zero + One + Num でもあります.

コード

extern crate num_bigint; // 0.2.2
extern crate num_traits; // 0.2.8
use num_bigint::BigInt;
use num_traits::Pow;

const X: i128 = -80_538_738_812_075_974; 
const Y: i128 = 80_435_758_145_817_515;
const Z: i128 = 12_602_123_297_335_631;

fn main() {
    let x: BigInt = X.into();
    let y: BigInt = Y.into();
    let z: BigInt = Z.into();
    
    let lhs = x.pow(3u32) + y.pow(3u32) + z.pow(3u32);
    println!("X^3+Y^3+Z^3 = {}", lhs );
    
    let rhs: BigInt = 42.into();
    assert_eq!( lhs, rhs );
}

結果

上のコードを動かすと X^3+Y^3+Z^3 = 42 と出力されるはずです. という訳で, 確かに問題の方程式の整数解になっていることが確認できました.