２００４年度・計算機数学１・第６回実習

1

２００４年度・計算機数学１・第６回実習

2★ exercise-06-4 ２つの正の整数 a, b に対して, 拡張されたユークリッドの互除法を用いて【課題】

ax + by = gcd(a, b)★ exercise-06-1 次の空欄を埋めなさい.
ユークリッドの互除法を用いて a = 40920, b = 24140 の最大公約数を求めよう.

をみたす (x, y) を一組求めるプログラムを書きなさい. ただし, xy = 0 をみたすこと.

40920 = 24140 ×+=×+

=×+

=×+

=×+

=×+

=×+

−

==

★ exercise-06-5 次の空欄を埋めなさい.
２進互除法を用いて a = 40920, b = 24140 の最大公約数を求めよう.
ステップ１ a = 40920, b = 24140 のどちらか一方が奇数になるまで両方を 2 で割ると, k =回割れて, a =,b=となる.

ステップ２ 必要なら a, b がともに奇数になるまで 2 で割り, a, b の大きい方から小さい方を引くことを繰り返すと,

=×+−

=×+−

=である.

−=

★ exercise-06-2 ２つの正の整数の最大公約数を求めるプログラムを「ユークリッドの互除法」を

−

=−

=−

=−

=

ステップ３ したがって gcd(40920, 24140) =×

したがって gcd(40920, 24140) =用いて書きなさい.
★ exercise-06-3 次の空欄を埋めなさい.

拡張されたユークリッドの互除法を用いて a = 40920, b = 24140 に対して,ax + by = gcd(a, b)となる.

をみたす (x, y) を一組求めよう.

× ( 24140 ,=である.

★ exercise-06-6 （やや難？）２つの正の整数の最大公約数を求めるプログラムを「２進互除法」( 40920 ,1,0)=0,1 )− (,,)(,,)=×(,,) −(,,)(,,)=×(,,) −(,,)(,,)=×(,,) −(,,)

ax + by = gcd(a, b)(,,)=×(,,) −(,,)をみたす (x, y) を一組求めるプログラムを「２進互叙法」を利用して書きなさい. ただし, xy = 0(,,)=×(,,) −(,,)(,,)=×(,,) −(,,)(,,)=×(,,) −(,,)(,,)=×(,,) −(,,)を用いて書きなさい.
★ exercise-06-7 （難）２つの正の整数 a, b に対してをみたすこと.
★ exercise-06-8 （難）上の問題 (exercies-06-7）で用いたアルゴリズムの正当性を証明しなさい.
★ exercise-05-9 ２つの正の整数の最小公倍数を求めるプログラムを書きなさい.

したがって40920 ×+ 24140 ×= gcd(40920, 24140)が成り立つ. また, 他の (x, y) の組は40920 ×+ 24140 ×=0であることより,x=+n×

y=+n×であらわすことができる.

ex06.tex,v 1.12 2004-05-17 13:17:20+09 naito Exp

ex06.tex,v 1.12 2004-05-17 13:17:20+09 naito Exp

２００４年度・計算機数学１・第６回実習

3２００４年度・計算機数学１・第６回実習

4● 前回の講義のキーポイント及び補足● 前回の課題の解説• 負の整数の表現方法として２の補数による表現を用いると, 加算回路を用いて減算を行うことが可能★ exercise-05-1 西暦 1900 年から西暦 2004 年までの閏年をすべて出力するプログラムを書きなさい.

となる.

/* $Id: exercise-05-1.c,v 1.2 2004-05-12 16:22:22+09 naito Exp $ */• 計算機内部の「実数」は「（２進）浮動小数点数」であらわさる. Ｃ言語においては double 型（または float 型）であらわされる.

#include <stdio.h>• 浮動小数点数の「仮数部」の桁数は有限であるため, （たとえば）１０進数の 0.1 は有限桁の２進浮動小数点型では正確な値をあらわすことはできなない. したがって（たとえば） 0.1 を 10 回加算し#define START#define ENDても 1.0 と等しいとは限らない.

• 整数の（int 型の） 1 と浮動小数点数の（double 型の） 1.0 とは, メモリ内部における表現が全く異なる.

1900
2004

int main(int argc, char **argv){• 算術演算においては次の事実が成り立つ.

int– 両方の被演算数が同じ整数型であるときには, 結果の型もその整数型となる.

year ;

for(year = START; year <= END; year++) {– 両方の被演算数が同じ浮動小数点型であるときには, 結果の型もその浮動小数点型となる.

if (((year%4 == 0)&&(year%100 != 0))||(year%400 == 0))– 片方の被演算数が int 型であり, もう片方の被演算数が double 型であるとき, 演算が行われる

printf("%d\n", year) ;前に int 型の数値が double 型に変換される. これを「算術変換」と呼ぶ. （算術変換の詳し}い挙動は K&R A6 を参照）

return 0 ;• 論理 AND 演算子, 論理 OR 演算子は左オペランドを先に評価する. （他の演算子のオペランドの評価順序は不定である）論理 AND 演算子, 論理 OR 演算子は左オペランドを評価した時点で結果の値

}• 閏年の条件は「西暦が４の倍数である中で, １００の倍数にはならない年. ただし, ４００の倍が確定するときには, 右オペランドの評価は行わない.

数の時には閏年とする」というものである. 条件が「独立」ではないため, 種々の書き方が考え

論理 AND/OR とビット AND/OR の挙動の違いを示すプログラム例は次のようなものである. （こられる.

れは久保氏に教えてもらった）/* $Id: loginal_bit_and.c,v 1.2 2004-05-15 15:41:42+09 naito Exp $ */#include <stdio.h>• 上のプログラム例は, 閏年になる条件を「素直」に書いたものである. わかりやすくするため「括弧」が少々冗長になっている.
• 西暦を表す変数は n, i などの単純な識別子名ではなく, year などの「意味のはっきりした」識別子名を使うことが望ましい.

inti, j, count ;int main(int argc, char **argv)• 他の条件判断例には以下のようなものがある.

{▼ 誤りではないもの

i = 0 ; j = 0 ; count = 0 ;– ((year%100 != 0)&&(year%4 == 0))||(year%400 == 0)

while(i++<10 | j++<10) count += 1 ;printf("i = %d, j = %d, count = %d\n", i,j,count) ;– (year%400 == 0)||((year%100 != 0)&&(year%4 == 0))

i = 0 ; j = 0 ; count = 0 ;while(i++<10 || j++<10) count += 1 ;– (year%400 == 0)||((year%4 == 0)&&(year%100 != 0))
これらは間違ってはいない. しかし, プログラムを書く場合には主に次の２つの考え方がprintf("i = %d, j = %d, count = %d\n", i,j,count) ;ある.

i = 0 ; j = 0 ; count = 0 ;while(i++<10 & j++<10) count += 1 ;1. プログラムをわかりやすく書く.
2. 高速に動作するプログラムを書く.

printf("i = %d, j = %d, count = %d\n", i,j,count) ;i = 0 ; j = 0 ; count = 0 ;この２つの考え方は相反する場合があり, （極端な言い方をすれば）閏年の判定もその一種である.

while(i++<10 && j++<10) count += 1 ;printf("i = %d, j = %d, count = %d\n", i,j,count) ;1. 「プログラムをわかりやすく書く」立場にたてば, 「閏年」の条件をそのまま条件文にreturn 0 ;}
ex06.tex,v 1.12 2004-05-17 13:17:20+09 naito Exp記述するのが望ましい. プログラム例の((year%4 == 0)&&(year%100 != 0))||(year%400 == 0)

ex06.tex,v 1.12 2004-05-17 13:17:20+09 naito Exp

２００４年度・計算機数学１・第６回実習

5は「条件」をそのまま記述したものである. 一方, 他の例は条件の記述順序が異なっている. この程度の単純な（３つ程度の）条件の時にはどれでもすぐに意味をとることが２００４年度・計算機数学１・第６回実習

6★ exercise-05-2 ２つの int 型の整数の和を計算するプログラムを書きなさい.

/* $Id: exercise-05-2.c,v 1.9 2004-05-15 14:53:47+09 naito Exp $ */#include <stdio.h>

できるが, 条件が複雑になった場合には, 「条件を簡潔に, かつわかりやすく」書くことが必要となる.

2. 「高速に動作するプログラムを書く」立場にたってみよう. この時は, それぞれの条件文に対して除算が何回実行されるかを調べる必要がある. ここでは 1601 から 2000 ま
でに対して除算の合計回数を調べてみよう.
year
1 4 の倍数でない
2 4 の倍数で 100 の倍数でない
3 100 の倍数で 400 の倍数でない
4 400 の倍数
合計

出現数1200396
311600(a)22333207(b)32224402(c)33214797(d)23313601(e)23313601(f)22333207int

a, b, c, sum ;unsigned int

n ;int main(int argc, char **argv){
a = 0xab123 ; b = 0x00ffffff ;sum = c = 0 ;(a) ((year%4 == 0)&&(year%100 != 0))||(year%400 == 0)

for(n=1;n;n<<=1) {(b) ((year%100 != 0)&&(year%4 == 0))||(year%400 == 0)

sum |= (a^b^c)&n ;c = (((a&b)|(b&c)|(c&a))&n)<<1 ;(c) (year%400 == 0)||((year%100 != 0)&&(year%4 == 0))(d) (year%400 == 0)||((year%4 == 0)&&(year%100 != 0))}(e) if (year%400 == 0)...; else if ((year%4 == 0)&&(year%100 != 0))...

printf("%d + %d = %d", a,b,sum) ;return 0 ;(f) if ((year%4 == 0)&&(year%100 != 0))...; else if (year%400 == 0)...
}▼ 誤りだと思われるもの– ((year%4 == 0)&(year%100 != 0))|(year%400 == 0)
論理 AND/OR ではなくビット AND/OR を使うと, 条件判断を行うための式の値とし「インクリメント」を使うことを認めれば, 次のような書き方もある.

ては等価となるが, 計算に無駄が多いことがわかる. 実際, year = 1601 から 2000 に/* $Id: exercise-05-2-1.c,v 1.4 2004-05-15 14:54:02+09 naito Exp $ */対して 1600 × 4 = 6400 回の除算が行われる.

#include <stdio.h>#define INT_BITS– (((is_leap = year%4) == 0)&&(is_leap%25 != 0))||(is_leap%100 == 0)32

これは, 一見「格好よく」見えるのだが, “25”, “100” という数字の意味が一見してはわからない. これは「プログラムをわかりやすく書く」ことに反している. 閏年の判定

int

a, b, c, sum, n ;の場合, year は高々（１０進）４桁であり, 100 で割っても 400 で割ってもその計算速度に大きな違いはない. しかし, 極めて長い桁の数値に対する演算の場合には, このような工夫は必要かもしれない.

int main(int argc, char **argv){
a = 0xab123 ; b = 0x00ffffff ;▼ 何とも言えないけど「ちょっとねぇ」と思うもの

sum = c = 0 ;if (year%400 == 0)...; else if ((year%4 == 0)&&(year%100 != 0))...
if ((year%4 == 0)&&(year%100 != 0))...; else if (year%400 == 0)...

for(n=0;n<INT_BITS;n++) {閏年の判定を（後に講義で出てくる）関数として実現し, 関数内部でこれを書くのであれ

sum |= (a^b^c)&(1<<n) ;c = (((a&b)|(b&c)|(c&a))&(1<<n))<<1 ;ば, 関数内部は一種の「ブラックボックス」と思えるので, 悪くはないのだと思うが, いきなりプログラム中にこのような条件があらわれると, 一体何を判定しているのかよくわから}
printf("%d + %d = %d\n", a,b,sum) ;ない. 少なくとも, この if 文の主旨がわかりやすいとは言えない. また, ここの条件判断における除算回数は上を参照のこと.

return 0 ;}ex06.tex,v 1.12 2004-05-17 13:17:20+09 naito Exp

ex06.tex,v 1.12 2004-05-17 13:17:20+09 naito Exp