RとPython書き比べ（ユークリッドの互除法）

R
Python
Author

Kentaro Kamada

Published

July 31, 2020

ユークリッドの互除法

ユークリッドの互除法は

  • 2つの自然数の最大公約数（GCD: Greatest Common Diviser）を求めるアルゴリズム
  • そのために以下の性質を利用

\(a\), \(b\)は自然数で\(a \neq 0\)のとき

等式：\(a = bq + r\)において，\(\mathrm{GCD}(a, b) = \mathrm{GCD}(b, r)\)が成り立つ

この性質を利用して，

「\(a\)を\(b\)で割って余り\(r_1\)を算出」→「\(b\)を\(r_1\)で割って余り\(r_2\)を算出」→…

→「\(r_{n-1}\)を\(r_n\)で割ると割り切れた」

→\(\mathrm{GCD}(r_{n-1}, r_n) = \mathrm{GCD}(r_{n-2}, n_{n-1})= ...=\mathrm{GCD}(b, r_1) = \mathrm{GCD}(a, b) = r_n\)

という形で最大公約数を求める

Rで関数を実装

  • 関数定義
# ユークリッドの互除法
gcd <- function(a, b){
  if (!(a %% 1 == 0 & b %% 1 == 0 & a > 0 & b > 0)) {
    cat('入力が自然数じゃないのでやり直し')
  } 
  else if (a < b) {
    w <- a
    a <- b
    b <- w
  }
  while (b != 0) {
    r <- a %% b
    a <- b
    b <- r
  }
  return(a)
}
  • 実行結果
gcd(50856, 96007)
[1] 163

Pythonで実装

  • 関数定義
# ユークリッドの互除法
def gcd(a, b):
  if not (a % 1 == 0 and b % 1 == 0 and a > 0 and b > 0):
    print('入力が自然数じゃないのでやり直し')
  elif a < b:
    w = a
    a = b
    b = w
  while not b == 0:
    r = a % b
    a = b
    b = r
  else:
    return(a)
  • 実行結果
gcd(50856, 96007)
163

両言語の比較

1. 制御構文

動作 R Python
関数定義 name <- function(引数){処理} def name(引数):処理
条件分岐1 if(条件式){処理} if 条件式:処理
条件分岐2 else if(条件式){処理} elif 条件式:処理
繰り返し while(条件式){処理} while 条件式:処理

2. 演算子など

動作 R Python
整数商 %/% //
剰余 %% %
論理積 & and
論理和 | or
否定 ! not

Rでは一貫して記号で演算子が与えられている一方， Pythonは条件分岐に関わる部分はアルファベットが用いられている。

Rの論理演算子がfilter処理とかで多用されることがイメージされている一方， Pythonはもっぱら条件分岐での使用がイメージされてそう？ （if not ～とかは自然に読みやすいけど，filter(a == 1 and b <= 3 and ～)は長くなって読みにくいみたいな）

追記

制御フローの見直し

R

  • 変数の代入の部分を;を用いて一列にできるらしい（やってることは変わらない）
  • Pythonみたいなa, b = b, aという書き方はできず，中間変数を使わざるを得ない
gcd2 <- function(a, b){
  if (!(a %% 1 == 0 & b %% 1 == 0 & a > 0 & b > 0)) {
    cat('入力が自然数じゃないのでやり直し')
  } 
  else {
    if(a < b){
      tmp <- a; a <- b; b <- tmp
    }
    while(b != 0){
      r <- a %% b; a <- b; b <- r 
    }
    return(a)
  }
}

Python

  • a, b = b, aという記法が大変便利。スワップ処理とかで中間変数が必要ない。
def gcd2(a, b):
  if not (a % 1 == 0 and b % 1 == 0 and a > 0 and b > 0):
    print('入力が自然数じゃないのでやり直し')
  else:
    if a < b:
      a, b = b, a
    while a % b != 0:
      a, b = b, a % b
    else:
      return b

再帰関数を用いた実装

再帰関数をコメントで教えてもらったので実装してみた。

注意点として，b == 0になるまで繰り返してしまうと，引数が自然数という条件に反してしまうので，その一回前（a % b == 0）まで繰り返すように書き換える必要がある。

  • Python
def gcd3(a,b):
  if not (a % 1 == 0 and b % 1 == 0 and a > 0 and b > 0):
    print('入力が自然数じゃないのでやり直し')
  else:
    if a < b:
      a, b = b, a
    if not a % b == 0:
      return gcd3(b, a % b)
    else:
      return b
gcd(50856, 96007)
163
gcd2(50856, 96007)
163
gcd3(50856, 96007)
163
  • R

再帰関数を呼び出す用のRecallという関数もある

gcd3 <- function(a, b){
  if (!(a %% 1 == 0 & b %% 1 == 0 & a > 0 & b > 0)) {
    cat('入力が自然数じゃないのでやり直し')
  } 
  else {
    if (a < b) {
      tmp <- a; a <- b; b <- tmp
    }
    if (a %% b != 0) {
      return(Recall(b, a %% b)) # またはgcd(b, a %% b)
    }
    else return(b)
  }
}
gcd(50856, 96007)
[1] 163
gcd2(50856, 96007)
[1] 163
gcd3(50856, 96007)
[1] 163