[R]Euclidean Algorithm in R

R で剰余を求める方法がわからなかったので調査。

Division in R
R の除法は次の演算子を利用
See: R manual ‘Arithmetic Operators’

  • 商(quotient) : %/%
  • 剰余(remainder) : %%

Euclidean Algorithm
この2つを用いて、ベタにユークリッドの互除法を実装すると、次のようになる。

gcd <- function(a, b) {
  while (b > 0) {
    q <- a %/% b
    r <- a %%  b
    a <- b
    b <- r
  }
  a
}

MEMO

  • Python の divmod に相当するものを探したが、見つけられず挫折したのは秘密

Visualize Number of Steps in Euclidean Algorithm
wikipedia を見ていたら、互除法のステップ数が可視化されていたので、ggplot2 で実装してみた。

library(ggplot2)
N <- 300
x <- matrix(nrow=N, ncol=N, 0)

gcd_step <- function(a, b) {
  idx <- 0
   while (b > 0) {
    q <- a %/% b
    r <- a %%  b
    a <- b
    b <- r
    idx <- idx + 1
  }
  idx
}

for (i in 1:N) {
  for (j in 1:i) {
    x[i, j] <- x[j, i] <- gcd_step(i, j)
  }
}

dataframe <- melt(x, c('x', 'y'))

p <- ggplot(dataframe, aes(x, y))
p + geom_point(aes(color=value))  + opts(title='Number of steps in the Euclidean algorithm for GCD(x,y)')

MEMO

  • “melt {resphace}” を用いて matirx の wide format を long format に変換
  • 実行が非常にトロイのでパフォーマンスを改善したいところ
Advertisements
Tagged with: , , , , ,
Posted in algorithm, R
3 comments on “[R]Euclidean Algorithm in R
  1. foo says:

    > gcd
    function(a, b)
    {
    while ((temp <- b %% a) != 0) {
    b <- a
    a <- temp
    }
    return(a)
    }

  2. […] [R]Euclidean Algorithm in R […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Archives
  • RT @__apf__: How to write a research paper: a guide for software engineers & practitioners. docs.google.com/presentation/d… /cc @inwyrd 4 months ago
  • RT @HayatoChiba: 昔、自然と対話しながら数学に打ち込んだら何かを悟れるのではと思いたち、専門書1つだけ持ってパワースポットで名高い奈良の山奥に1週間籠ったことがある。しかし泊まった民宿にドカベンが全巻揃っていたため、水島新司と対話しただけで1週間過ぎた。 それ… 5 months ago
  • RT @googlecloud: Ever wonder what underwater fiber optic internet cables look like? Look no further than this deep dive w/ @NatAndLo: https… 5 months ago
  • @ijin UTC+01:00 な時間帯で生活しています、、、 10 months ago
  • RT @mattcutts: Google's world-class Site Reliability Engineering team wrote a new book: amazon.com/Site-Reliabili… It's about managing produc… 1 year ago
%d bloggers like this: