2018-09-21

Rust を触った上で困惑したこと

背景

ユークリッド互除法を Rust で書いてみた上でハマった点があったのでいくつか覚書して置きます.
先に言っておきますが, 諸々の事情で C++er が Rust を始めて困惑したこと集みたいになっているので悪しからず...
別に「Rust のここがダメ! 」とか言いたいわけではありません.

ハマりポイント

1. 変数がデフォルト, イミュータブル

イミュータブルとは変更できないと言う意味なのですが, 以下の様なプログラムはコンパイルエラーになってしまいます。

// コンパイルエラーになる例

let a = 100;
a += 20; // 変更するとエラー

変更したい変数には mut をつけます.　mut はミュータブルの略です.

let mut a = 100;
a += 20;

2. 三項演算子が使えない

let a = 10 > 2 ? 1 : 2; // expected one of `.`, `;`, `?`, or an operator here

条件文 ? val1 : val2 ではなく以下の様に if 条件文 { val1 } else { val2 } の様に書きます.

let a =  if 10 > 2 { 1 } else { 2 };

ちなみに, Rust では条件文に () をつけません. つけると次の様な警告が出ます help: remove these parentheses

3. シャドーイング

let a = 20;
{
    let a = a * 10; // シャドーイング
    println!("a: {}", a); // 200
}

println!("a: {}", a); // 20

let a = a / 10; // シャドーイング
println!("a: {}", a); // 2

「こいつ, 動くぞ！」ってなりました. シャドーイングは既存の格納先を無視して新しい格納先を変数に入れ込む方法の様です. スコープを外れると元の参照先になるので, 破棄しているわけではなさそうです.

他, 参考になりそうな記事

qiita.com qiita.com

2018-09-20

ユークリッド互除法のプログラム

先日ユークリッド互除法 - y-say1125’s diary を書いたので, 今回はプログラムを掲載します.

$mod$ と代入だけでできるのでシンプルに書けますね.

ちなみにですが, Rust でコードは書き慣れてない初心者です 😇

ユークリッドの互除法

2018-09-19

ユークリッド互除法

目的

最近ユークリッド互除法をコードに落とし込む機会があったのですが, 自分の理解を整理できていなかったのでまとめます.

ユークリッド互除法とは

2 つの自然数 $a, b$ の最大公約数を計算する方法です.

自然数 $a, b$ の最大公約数を $gcd(a, b)$ と表す場合, 以下の定理を用いて計算します.

$a > b \in \mathbb{N}$ とし, $a$ を $b$ で割ったときの商を $q \in \mathbb{N}$ 余りを $r$ とする.

つまり $a = b \times q + r$ , $0 \leq r$ < $b$
このときに $gcd(a, b) = gcd(b, r)$ となる

例1. $gcd(130, 156)$

まず, $a = 156, b = 130$ として, $a = b \times q + r$ の式を埋めてみましょう.
$156 = 130 \times 1 + 26$

ユークリッドの互除法より, $gcd(a, b) = gcd(b, r)$ です.
なので, $a' = b, b' = r$ として $a' = b' \times q' + r'$ を埋めると以下の様になります.
$130 = 26 \times 5 + 0$

このとき, $b' = 26$ と $r' = 0$ の最大公約数は 26 であることが明らかです.
よって, 26 が最大公約数となります.

ユークリッド互除法の証明

それでは, $gcd(a, b) = gcd(b, r)$ となることを証明します.
ここで $G = gcd(a,b), G' = gcd(b, r) \in \mathbb{N}$ と定義します.

まずこの式に立ち返りましょう. $a = b \times q + r$

$a = b \times q + r, G' = gcd(b, r)$ より, $a = G'( b \times q' + r')$ が成り立ちます.
よって, $a, b$ は共に $G'$ を因数に含むことがわかります.
そして, $G = gcd(a,b)$ なので, $G' \leq G$ であることがわかります.
$a = b \times q + r$ より, $r = b \times q - a$ であることに注目すると,
$r = b \times q - a, G = gcd(a, b)$ より, $r = G( b \times q' + a')$ が成り立ちます.
よって, $r, b$ は共に $G$ を因数に含みます.
そして, $G' = gcd(b,r)$ なので, $G \leq G'$ であることがわかります.

1, 2 より $gcd(a, b) = gcd(b, r)$ が成り立ちます.

参考文献

プログラミングの背景・数論 : ユークリッドの互除法 2014/06