剰余演算を使わずに最大公約数を求めるには

Question

前提・実現したいこと

プログラミング超初心者で初めて質問させていただきました。
題名にもある通り剰余計算を使わずに2変数x,yの最大公約数を求めるにはどのようにすればよいですか？
最大公約数をgcd(x,y)とし、
ｘ、ｙがともに偶のとき,gcd(x,y)→2*gcd(x/2,y/2)
xが奇,yが偶のとき、gcd(x,y)→gcd(x,y/2)
x,yどちらも奇のとき、gcd(x,y)→gcd((x,y)/2,y)
という要領で計算します。
できれば演算子％を使わずにお願いします。
ここに質問の内容を詳しく書いてください。

発生している問題・エラーメッセージ

def gcd(x, y):
   if y==0:
       return x
   elif x&1==0 and y&1==0 and y!=0:
       x, y=x//2, y//2
       return 2*gcd(x, y)
   elif x&1==0 and y&1==1 and y!=0:
       x=x//2
       return gcd(x, y)
   elif x&1==1 and y&1==0 and y!=0:
       y=y//2
       return gcd(x, y)
   elif x&1==1 and y&1==1 and x<y and y!=0:
       x, y=x, (y-x)//2
       return gcd(x, y)
   else:
       x, y=(x-y)//2, y
       return gcd(x, y)
print(f'gcd(123456, 65432)={gcd(123456, 65432)}')
に対してエラーが出ます。

該当のソースコード

python

試したこと

自分なりにコードを書いたのですが初歩的なところでつまずいているのかもしれずエラーコードを見ても分かりません。
とてもレベルの低い質問かもしれませんが、回答してくださればと思います。
ここに問題に対して試したことを記載してください。

補足情報（FW/ツールのバージョンなど）

ここにより詳細な情報を記載してください。

Comments

[maisumakun]

「剰余計算を使わずに」とありますが、他に禁止されているものはありますか？

[syoutaro22]

自分は再帰を使って書こうと思うので再帰を使っていただけたらなと
加えてｘ、ｙは正の整数が前提です。

[maisumakun]

> 自分は再帰を使って書こうと思うので再帰を使っていただけたらなと

剰余演算を使っても再帰で書けますが、他に条件はないのですか？

[syoutaro22]

ｘ、ｙの大小は決まってなくて、時間はo(logx)でという条件があります。

[maisumakun]

我流で実装を行うのであれば、タイトルの「ユークリッドの互除法」は不適当です。消しておきましょう。

[syoutaro22]

申し訳ないです。修正させていただきました。

[tiitoi]

なぜ質問を消したのでしょうか？

Answer 1

アルゴリズムについて

最大公約数をgcd(x,y)とし、
ｘ、ｙがともに偶のとき,gcd(x,y)→2*gcd(x/2,y/2)
xが奇,yが偶のとき、gcd(x,y)→gcd(x,y/2)
x,yどちらも奇のとき、gcd(x,y)→gcd((x,y)/2,y)
という要領で計算します。

これが間違っています。
まず、互除法をちゃんと理解しましょう。
gcd((x-y)/2,y)が正しいとのことなので、互除法はわかっていますね。

プログラムのデバッグについて

突然、大きな数字でやるのではなく、小さな数字から始めましょう。
2と3の最大公約数は求められるでしょうか。

def gcd(x, y):
    if y==0:
        return x
    elif x&1==0 and y&1==0 and y!=0:
        x, y=x/2, y/2
        return 2*gcd(x, y)
    elif x&1==0 and y&1==1 and y!=0:
        x=x/2
        return gcd(x, y)
    elif x&1==1 and y&1==0 and y!=0:
        y=y/2
        return gcd(x, y)
    elif x&1==1 and y&1==1 and x<y and y!=0:
        x, y=x, (y-x)/2
        return gcd(x, y)
    else:
        x, y=(x-y)/2, y
        return gcd(x, y)

print(gcd(2,3))

実行するとエラーが出ますね。

> python gcd.py
Traceback (most recent call last):
  File "gcd.py", line 20, in <module>
    print(gcd(2,3))
  File "gcd.py", line 9, in gcd
    return gcd(x, y)
  File "gcd.py", line 4, in gcd
    elif x&1==0 and y&1==0 and y!=0:
TypeError: unsupported operand type(s) for &: 'float' and 'int'

4行目、つまり elif x&1==0 and y&1==0 and y!=0:のところで、float型とint型で&はできませんというエラーメッセージが出ています。これは理解できますか。

自力で解決できたようなので、いくつかのサンプルを載せておきます。

syoutaro22さんのアルゴリズムですが、これは互減法のアルゴリズムに2だけ割るアルゴリズムを付け加えたものです。こういう発想はプロ的なのですが、syoutaro22さんは初心者ということですので、たまたま思いつけたということなのでしょう。一般的には、数字が小さいときには互減法は互除法より高速なのです。python3の場合は、64ビットを超えると整数の割り算が極端に遅くなるので、その場合も有効かもしれません。

互減法は、割り算機能のついていない組み込み用の小さなCPUなどでも使います。
互減法については最大公約数をもっと高速に求めるなどを見てみてください。

def gcd(x, y):
    if y==0:
        return x
    elif x < y:
        return gcd(y, x)  #こうやっておいたほうが間違いが少ない。
    elif x&1==0 and y&1==0:
        return 2*gcd(x//2, y//2)
    elif x&1==0 and y&1==1:
        return gcd(x//2, y)
    elif x&1==1 and y&1==0:
        return gcd(x, y//2)
    elif x&1==1 and y&1==1:
        return gcd(x-y, y)  # 大きいほうから小さいほうを引く
    else:
        print('proguram error') # ここに来るならプログラムの間違い
        raise(Exception)

一方、互除法でやるには、y_waiwaiさんが勧めていたようにやります。以下をご覧下さい。

def gcd(x, y):
    if x < y:
        return gcd(y, x)
    elif y==0:
        return x
    elif x == x // y*y:
        return y
    else:
        return gcd(x-y, y)

Comments

[syoutaro22]

理解できました。

[ppaul]

見直していて、gcd((x,y)/2,y)が意味不明であることに気が付きました。
これは何を意味していますか？

[syoutaro22]

ごめんなさい、、
最初の説明のgcd((x,y)/2,y)は間違いです。
正しくはgcd((x-y)/2,y)です。
申し訳ないです。

[ppaul]

なるほど、それならなら互除法はわかっていますね。
ひょっとしてアセンブラの互除法のアルゴリズムを考えるためにpythonとかで組んでみなさいという課題なのかな。だとしたら、剰余だけじゃなく、割り算も使っちゃだめですね。2による割り算をシフトで済ませれば、割り算なしでできるし、アセンブラレベルで考えれば、そのほうが高速にできますね。

[syoutaro22]

この考え方で組んでみたのですが、コードの書き方が悪いのか、考え方が間違っているのかが分かりません。

[ppaul]

考え方は、(無駄は多いですが)ほぼ合っています。
今のままだと、整数型割り算を使っても、無限ループに入る可能性があります。
問題は、x-yが負の数になった場合をどう考えるかです。
それさえクリアすれば動きますよ。
そこまで行ったら、無駄のないコードを回答に追加しますので、やってみてください。

[syoutaro22]

ifの前に
if x<y:
x,y=y,x
を付け加える。
で合っているでしょうか？

[ppaul]

そう思ってやってみたら、gcd(9,3)が無限ループに入りました。
これはアルゴリズムの問題かな。

[ppaul]

いや、元のプログラムの/を//に変えて、
ifの前に
if x<y:
x,y=y,x
を付け加える。
なら動きますね。
あとで、私が修正したプログラムにコメントを付けて載せます。

[syoutaro22]

自分の書いたコードに
if x<y:
x,y=y,x
を付け加えたらエラーが出ずに計算できました。

[syoutaro22]

了解しました。
長々とした質問に回答してくださりありがとうございました。

Answer 2

まず、プログラムを実行するとエラーになります。
割り算を使っているため、変数がfloatと判断されているようです。
ビットシフトなどに変更しないとだめです。
がしかし、ある意味、bit演算も剰余演算だと思います。

剰余演算を使わずにGCDを求めるには、以下の公式を使えばよいと思います。
GCDは以下の公式が成り立ちます。

GCD(a, b) = GCD(a - b, b)
ここで、a > b

これを使えば、引き算と数の大小比較でGCDを求めることができると思います。

Answer 3

ｘ、ｙがともに偶のとき,gcd(x,y)→2*gcd(x/2,y/2)

xが奇,yが偶のとき、gcd(x,y)→gcd(x,y/2)
x,yどちらも奇のとき、gcd(x,y)→gcd((x,y)/2,y)
という要領で計算します。

ユークリッドの互除法は偶数でも奇数でも関係なく適用できますので、このような場合分けは冗長なだけです。

Comments

[maisumakun]

ユークリッドの互除法の本質とは関係ない、「できれば演算子％を使わず」といった条件や、上の場合分けなどを考えると、（普通にコードを書くことはできても）「syoutaro22さんの期待するコードがどんなものなのかわからない」というのが正直なところです。

[syoutaro22]

剰余演算を使うと楽に計算できるのは重々承知ですが、このプログラミングでエラーがでる理由だけでも教えていただければと思います。

[maisumakun]

どのようなエラーメッセージが出たのですか？

[maisumakun]

> 剰余演算を使うと楽に計算できるのは重々承知ですが

それとは無関係に、偶数か奇数かの場合分けをして処理するようなものは「ユークリッドの互除法」とは呼びません。

[syoutaro22]

以下のようなエラーが出ました。
unsupported operand type(s) for &: 'float' and 'int'

[maisumakun]

Python 3の/演算子は結果をfloatで返します。

[syoutaro22]

つまり//演算子を使うということでしょうか？

[maisumakun]

とりあえずは、そうですね。

[maisumakun]

まずもってですが、ゴールはどこなのでしょうか。

正しく「ユークリッドの互除法」を実装したいのか、それとも「場合分けなどを入れた我流のアルゴリズム」に進みたいのか、そこをはっきりさせてください。

[syoutaro22]

学校の授業の問題の一つで、
def euclid_itr(x, y):
while y != 0:
x, y = y, x % y
return x
print(euclid_itr(6,9))
のようなものを習ったのですが、今度は再帰でなおかつ剰余を使わないで書いてみるとどうなるかとなったので、試したところエラーが出て質問しました。つまり早くはない我流のやり方です。

[maisumakun]

> 今度は再帰でなおかつ剰余を使わないで書いてみるとどうなるかとなったので

剰余を使わなくてもユークリッドの互除法は実装できますが、あえて場合分けを取り入れたいのですか？

[syoutaro22]

そうです。

[maisumakun]

でしたら、もうコメントすることはありません（というか、できません）。

通常の互除法ではない以上、これ以降、どのようにアルゴリズムを組んでいくかについて、
syoutaro22さんの構想がわからないので、自分で頑張ってください。

[syoutaro22]

分かりました。
いろいろ説明不足ですいませんでした。
回答いただきありがとうございました。

Answer 4

整数で除算した結果をそのまま掛けて、元の数値と比較すれば、割り切れてるのかどうかは見れますね