ホーム » 2015 » 4月

月別アーカイブ: 4月 2015

2015年4月
« 3月   5月 »
 1234
567891011
12131415161718
19202122232425
2627282930  

最近の投稿(電子情報)

アーカイブ

カテゴリー

数値の範囲とトラブル事例

先日の数値の範囲の説明で、浮動小数点型(float,double)などについても説明を行う。

16bitコンピュータの時代…

簡単な桁あふれの事例として、古いコンピュータ16bitの時代の事例。

// int は16bitとする。
// パソコン画面上の2点の距離を計算したい。
int x1 , y1 ;
int x2 , y2 ;
int r = (int) sqrt( (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) ) ;

このプログラムは、負の値の平方根を求めた…というエラーメッセージで止まってしまう。

これは、座標が200ドット離れていれば、2乗の和を求めた段階で、40000となるが、 16bit 符号付き整数であれば、最大数が32767 なので桁あふれして、負の数として扱われている。

2038年問題

次に、20XX年問題の説明。 2000年問題とは、古いプログラムで西暦末尾2桁で年を扱っていたプログラムが誤動作を 起こす可能性の問題。

同じように数値の範囲が原因となるものとして、2038年問題を紹介する。 OS unix では、時間を1970年からの経過秒数で表す。 この時、32bit(符号付きint型)であれば、2^31-1が扱える最大数であり、 (2^31-1) / (3600*24*365.22)を求めると、約68年となる。 つまり、32bit int であった場合は、2038年以降は桁あふれで時間を正しく扱えなくなる可能性がある。

しかし、計算の途中の段階で桁あふれして動かない事例はある。 以下の事例は、2004年に実際に発生したトラブルと同様の簡単なコードである。

// intは32bitとする
// 2つの時間の中央時間を計算するコード
int t1 , t2 ;
int tm = (t1 + t2) / 2 ;

32bitの時間情報では、2004年以降は、 t1,t2の上位ビットが01XX……となっているため、 t1+t2 を計算すると最上位ビット(符号ビット)が1となり この後の計算は、負の値として扱われた。

上記のコードは、次のように記述するか、64bit化されたtime_t型で 記述すべきである。

// 32bitでも動く
int tm = t1 + (t2 - t1) / 2 ;
// 64bitのtime_t型
time_t t1 , t2 ;
time_t tm = (t1 + t2) / 2 ; // △
time_t tm = t1 + difftime( t2 , t1 ) / 2 ; // ◎

248日問題

丁度ニュースで、「ボーイング787が248日以上連続稼働すると、電源停止で制御不能となる」というネタが 紹介されている。点検などがあるから、実際はあり得ない状況だとは思えるが、 これもint型の桁あふれが原因らしい。 あり得ないとはいえ、フライバイワイヤ(操縦桿を電気信号で制御)の最新機は、電源が落ちれば即墜落。 これは、10msec単位で、OSの経過時間をint型(32bit)で制御しているのが 原因らしい。10msec*(2^31)=248日で桁あふれが発生して、電源稼働経過時間を誤認するらしい。 これと同様の事象は、Windows Xpなどが出た頃にも発生している。 787ほど深刻な墜落はないにしても、サーバ機なら248日稼働ぐらいはよくある話。

浮動小数点型と演算順位の問題

float型やdouble型は、浮動小数点で実数の小さな値から大きな値まで扱える。


しかしながら、プログラム中の式の順序によっては、注意が必要となる。

int a[ 5 ] = { 10 , 10 , 10 , 10 , 11 } ;
int s = 0 , size = 5 ;
for( int i = 0 ; i < size ; i++ )
s += a[ i ] ;
printf( "%lf¥n" , s / size ) ;
// × %lf はdouble型、s/size はint型で異常な値が表示される。
printf( "%lf¥n" , (double)( s / size ) ) ;
// × s/sizeはint型で、小数点以下が求まらない。
printf( "%lf¥n" , (double)s / (double)size ) ;
// ◎
#define PI 3.141592
double x ;
for( x = 0.0 ; x < 2*PI ; x += (1/6) * PI ) {
printf( "%lf %lf¥n" , x , sin( x ) ) ;
}

このプログラムは、1/6が整数型で行われるため(つまり0とPIを掛ける)、 xの値が変化しない。 これは、"x += (1.0/6.0) * PI" と書かなければならない。

隠蔽化の課題(複素数クラスを例に)

前回の隠蔽化の話を受け、実際のプログラムの例を課題に説明。 複素数クラスを(実部,虚部)で実装した後に、(絶対値,偏角)に直したら…

基本プログラム(実部と虚部)

複素数を扱うクラスを作るのであれば、基本的には以下の様なコードとなるだろう。 複素数どうしの簡単な加算・乗算を記載する。

class Complex {
private:
   double re , im ;
public:
   Complex( double x , double y ) {
      re = x ;
      im = y ;
   }
   // 上記コンストラクタは、以下のようにも書ける。
   // Complex( double x , double y )
   // :   re( x ) , im( y )
   // { メンバ以外の初期化... }
   void print() {
      printf( "%lf+j%lf¥n" , re , im ) ;
   }
   void add( Complex &z ) {
      re = re + z.re ;
      im = im + z.im ;
   }
   void mul( Complex &z ) {
      double x = re * z.re - im * z.im ;
      double y = re * z.im + im * z.re ;
      re = x ;
      im = y ;
   }
} ;
int main() {
   Complex a( 1 , 2 ) ;
   Complex b( 2 , 3 ) ;
   a.add( b ) ;
   a.print() ;
   a.mul( b ) ;
   a.print() ;
   return 0 ;
}

Complexクラス内部をリファクタリング

しかし、前述プログラムでは、mul()メソッドは、add()メソッドよりは、 複雑なものとなっている。 しかし、複素数の乗算は、(絶対値と偏角)を用いれば、絶対値の乗算・偏角の加算で 処理は簡単に記述できる。そこで、クラス内部を乗算と偏角で処理をするように変更してみる。

class Complex {
private:
   double r , th ;
public:
   Complex( double x , double y ) {
      r = sqrt( x*x + y*y ) ;
      th = atan2( y , x ) ; // atan2は象限を考慮してくれる
   }
   void print() {
      printf( "%lf ∠ %lf¥n" , r , th / 3.141592 * 180.0 ) ;
   }
   void add( Complex &z ) {
      // ここは面倒な式になっちゃう
   }
   void mul( Complex &z ) {
      r  = r  * z.r ;
      th = th + z.th ;
   }
} ;
int main() {
   Complex a( 1 , 2 ) ;
   Complex b( 2 , 3 ) ;
   a.add( b ) ;
   a.print() ;
   a.mul( b ) ;
   a.print() ;
   return 0 ;
}

ここで重要なポイントは、2つめの絶対値∠偏角のプログラムの呼び出し側 main() は、 1つめのプログラムとまるっきり同じである。

このように、オブジェクト指向の隠蔽化を行っていれば、当初のクラス設計が悪くて後で変更 したくなった場合、利用者側からの見た目の動作を変更せずに、内部のデータ構造や処理メソッドを 変更が可能となる。 このように、利用者側からの見た目を変更せずに処理の内部を変更すること、 リファクタリング と呼ぶ。これにより、プログラムの不備や問題点があっても、積極的にプログラムを 改良できることから、不備の少ない安全なプログラムを作れるようになる。

隠蔽化の課題

以上の2つのプログラムで複素数の計算メソッド、加算(add),除算(sub),乗算(mul),除算(div)…その他を (実部,虚部)、(絶対値,偏角)で記載し、適切に記述をすれば、呼び出し側main()を まるっきり同じものにできることを通して、隠蔽化についてレポートにまとめよ。

レポートでは、以下の点を記載すること。(レポートは、本科中間試験の頃までに提出が望ましい)

  • 2つの方式でのプログラム例
  • 上記プログラムに対する説明
  • 上記プログラムが正しく動作していたことが判る結果
  • この課題から判る考察

パスワードの有効期限…

福井高専の様々なWebシステムを利用している場合、 パスワードなどの認証は、UnifIDone というシステムに 統合されています。

1504301038_957x368.png

このシステムでは、安易なパスワード管理による不正アクセス を防止するために、パスワードの有効期限が400日に設定されています。

このため、年度が改まる頃には、システムにアクセスする際には、 パスワード有効期限の警告が表示されます。 この際には、パスワードの変更をお願いします。

教職員の場合には、UnifIDone のパスワード変更へのリンクは、 グループウェア Garoon の右下にあるリンク集の所に、 「パスワード変更」のリンクがあります。

1504301038_369x386.png

学生の場合には、ブラウザのブックマーク先頭に、 「パスワード変更」が登録されています。

Debian 8.0/Jessie のインストール

Debian 8.0 / Jessie が stable となって配布が始まったので、 まずは影響の少ないサーバに入れてみる。 自宅や自室のサーバは、すでに Jessie に切り替え済みだけど、 久々だと、なかなか手間取る。

# aptitude remove `dpkg -l | awk '{print $2}' | egrep -e ^kde-`
# aptitude remove `dpkg -l | awk '{print $2}' | egrep -e ^gnome-`

あたりを実行して、依存の原因となりそうなパッケージはひとまず 減らしてから、

# aptitude update ; aptitude full-upgrade

ただし、処理中に libxml-libxml-perl が更新前の削除でエラーが発生し 手間取ってしまった。パッケージの依存情報の微妙なエラーがあるようだ。 この次に学科のメインサーバの更新となるが、 その際には、一番最初に削除してからにしよう。

再起動させたら失敗

更新は上手くいったが、翌朝再起動をかけたら起動しない。 Debian/Jessie/netinst のCDを作り、リカバリーモードで起動させる。

起動時には、ブートローダーで linux-image-2.16 なんかを探しているので、 古いブートローダーを使おうとしている。どうも、grub2のインストールで失敗していた様子。 以下のコマンドで、インストールを確認し再起動。

# aptitude install grub2
# grub-install /dev/sda
# update-grub

更新の最終段階は、夜中に家からの作業だったけど、reboot は翌朝にして正解だった…(x_x;

2015年体育祭-電子情報-翠

1504291100_1108x607.png

2015年4月26日(第420回)

体育祭準備のため、収録でお送りしました。

  • まるよし Train Pops ~ 国語と遊ぼう! 第100便 「寄せ書き」
  • 体育祭の思い出
  • 体育祭の撮影について
  • お花見について

担当:田中(2B・MC)、植村(2E・MIX)、山田(2B)、川﨑(2EI)、西(教員)

宿直で、寮イベント焼き芋づくり

1504231945_640x640.JPG

再帰関数の処理と再帰方程式

前回の授業で、処理速度のオーダ記法について解説し、 実際例と処理速度の問題について解説する。 後半は、再帰呼び出しの処理速度見積もりのための再帰方程式を示す。

特殊な処理時間の見積もり

前回授業の最後に検討しておくようにと伝えた、 の処理時間のオーダについて、Nが巨大となった時の、最大項を見つければ良いことから、 が、N→∞において 発散するのか収束するのかを求める方法にて説明する。

また、2つのアルゴリズムがNの増加で処理時間が変化する時の事例として、 「データ件数が10件で、最大選択ソートが10msec、クイックソートが20msec出会った場合、 データ100件では、どちらが速いか?、この結果から、 データ件数がいくつ以上であれば、どちらの方法が良いか?」 といった問題について説明する。

最大選択ソートであれば、 より、 であるとする。 一方、クイックソートは、 より、 であるとする。 より、 より、

これより、データ100件の場合には、 となる。 また、 となりクイックソートの方が速い。

さらに、 となるNを求めれば、N件以上は クイックソートが速い…といった件数を求められる。

再帰関数と再帰方程式

再帰関数は、自分自身の処理の中に「問題を小さくした」自分自身の呼び出しを含む関数。

// 階乗
int fact( int x ) {
   if ( x <= 1 )
      return 1 ;
   else
      return x * fact( x-1 ) ;
}
// ピラミッド体積
int pyra( int x ) {
   if ( x <= 1 )
      return 1 ;
   else
      return x*x + pyra( x-1 ) ;
}
// フィボナッチ数列
int fib( int x ) {
   if ( x <= 2 )
      return 1 ;
   else
      return fib( x-1 ) + fib( x-2 ) ;
}

これらの関数の結果について考えるとともに、この計算の処理時間を説明する。 最初のfact(),pyra()については、 x=1の時は、関数呼び出し,x<=1,return といった一定の処理時間を要し、 で表せる。 x>1の時は、関数呼び出し,x<=1,*,x-1,returnの処理に加え、x-1の値で再帰の処理時間がかかる。 このことから、 で表せる。 これを代入によって解けば、 で表せる。 こういった式は、再帰方程式と呼ばれ、一般式を求めることとなる。

最後に、再帰方程式の事例として、ハノイの塔の処理時間について説明し、 数学的帰納法での証明を示す。

ハノイの塔

ハノイの塔は、3本の塔にN枚のディスクを積み、ディスクの上により大きいディスクを積まずに、移動させるパズル。 ハノイの塔の移動回数を とした場合、 少ない枚数での回数の考察から、 ということが予想される。

この予想が常に正しいことを証明するために、ハノイの塔の処理を、 最も下のディスク1枚と、その上の(N-1)枚のディスクに分けて考える。 これより、


ということが言える。 ディスクが 枚で、予想が正しいと仮定すると、 枚では、



となり、 枚でも、予想が正しいことが証明された。 よって数学的帰納法により、1枚以上で予想が常に成り立つことが証明できた。

C言語の構造体からオブジェクト指向に

前回の構造体の説明から、ポインタ渡しの説明を行った後、同様のプログラムをC++で書き換えることで、classやメソッドなどの説明を行う。

構造体でオブジェクト指向もどき

例えば、名前と電話番号の構造体で処理を記述する場合、 以下の様な記載を行うことで、データ設計者とデータ実装者で分けて 仕事ができることを説明。

struct Person {
   char name[10] ;
   int  phone ;
} ;
void readPerson( struct Person* p ) {
   // ポインタの参照で表記
   scanf("%s%d" ,
   (*p).name , &(*p).phone ) ;
}
void printPerson( struct Person* p ) {
   // アロー演算子で表記
   printf( "%s %d¥n" ,
   p->name , p->phone ) ;
}
void main() {
   struct Person table[ 10 ] ;
   for( int i = 0 ; i < 10 ; i++ ) {
      readPerson( &table[i] ) ;
      printPerson( &table[i] ) ;
   }
}

このプログラムの書き方では、mainの中を読むだけもで、 データ入力とデータ出力を行うことはある程度理解できる。 この時、データ構造の中身を知らなくてもプログラムが理解でき、 データ実装者はプログラムを記述できる。これをデータ構造の隠蔽化という。 一方、readPerson()や、printPerson()という関数の中身についても、 入力・出力の方法をどうするのか知らなくても、 関数名から動作は推測できプログラムも書ける。 これを手続きの隠蔽化という。

C++のクラスで表現

上記のプログラムをそのままC++に書き直すと以下のようになる。

class Person {
private: // クラス外からアクセスできない部分
   char name[10] ; // メンバーの宣言
   int  phone ;
public: // クラス外から使える部分
   void read() { // メソッドの宣言
      // pのように対象のオブジェクトを明記する必要はない。
      scanf( "%s%d" , name , &phone ) ;
   }
   void print() {
      printf( "%s %d¥n" , name , phone ) ;
   }
} ;
void main() {
   Person table[ 10 ] ;
   for( int i = 0 ; i < 10 ; i++ ) {
      table[i].read() ;  // メソッドの呼び出し
      table[i].print() ;  // オブジェクト.メソッド()
   }
   // 文法エラーの例
   printf( "%d¥n" , table[0].phone ) ;
   // phoneはprivateなので参照できない。
}

用語の解説:C++のプログラムでは、データ構造とデータの処理を、並行しながら記述する。 データ構造に対する処理は、メソッド(method)と呼ばれる。 データ構造とメソッドを同時に記載したものは、クラス(class)と呼ぶ。 そのclassに対し、具体的な値や記憶域が割り当てられたものをオブジェクト(object)と呼ぶ。

コンストラクタとデストラクタ

プログラムを記述する場合、そのデータ構造を使うにあたり、 初期値が代入を忘れその値を参照すると、予想外の動きの原因となってしまうことが多い。

そこでオブジェクト指向では、データ構造の初期化手続き(同様に処理が終わった後の事後手続き)を 明確に記載するための初期化のコンストラクタ(と事後処理はデストラクタ)の文法がある。

class Person {
private:
   char name[10] ;
   int  phone ;
public:
   Person( char s[] , int tel ) { // コンストラクタ
      strcpy( name , s ) ;
      phone = tel ;
   }
   void print() {
      printf( "%s %d¥n" , name , phone ) ;
   }
} ;
void main() {
   // オブジェクト宣言とコンストラクタでの初期化
   Person saitoh( "tsaitoh" , 272925 ) ;
   saitoh.print() ;
}

コンストラクタを宣言する場合には、返り値無しのクラス名を関数名として記述する。 デストラクタを宣言する場合には、先頭に「~」をつけたクラス名で無引数で記述する。 簡単な例として、文字列をヒープ領域に保存する処理を示す。

// デストラクタが便利な例
class String {
private:
   char* str ;
public:
   // コンストラクタ
   String( char*s ) {
      // ヒープメモリ上に文字列を確保
      str = (char*)malloc( strlen( s ) + 1 ) ;
      strcpy( str , s ) ;
   }
   // デストラクタ
   ~String() {
      free( str ) ; // freeしないとメモリーリークになる。
   }
   void print() {
      printf( "%s" , str ) ;
   }
} ;
void main() {
   String s( "abcdefg" ) ;
   s.print() ;
}  // mainを抜ける段階でsは不要となる。
// ここで自動的にデストラクタ呼び出し~String()をしてくれる。

関数の値渡しと、整数型の数値の範囲

丁度、講義の前に別授業の課題に取り組んでいる学生を見ていたら、 次週に説明を行おうと思っていたN進数、小数点を含む2進数であった。 丁度、「計算機構成論」の補数、「数値計算」の小数点を含む2進数の講義で、 いつもになく、内容と説明時期が重複している…(^_^;

関数の値渡し

関数との引数の値渡しについて解説。 C言語では基本の値渡しメカニズムしかない。 引数で副作用(side effect)を返したい場合は、その代用としてポインタ渡しを利用する。 また、配列が引数の場合、値渡しのためのコピーを最小限とするため、 配列先頭アドレスによるポインタ渡しで行われることを説明する。

// 値渡し
void foo( int x ) {
   x++ ;
   printf( "%d¥n" , x ) ;
}
void main() {
   int a = 123 ;

   foo( a ) ; // 124
   foo( a ) ; // 124
}
// ポインタ渡し
void foo( int* px ) {
   (*px)++ ;
   printf( "%d¥n" , *px ) ;
}
void main() {
   int a = 123 ;

   foo( &a ) ; // 124
   foo( &a ) ; // 125
}
// 参照渡し(C++の新しい文法で紹介のみ)
void foo( int &x ) {
   x++ ;
   printf( "%d¥n" , x ) ;
}
void main() {
   int a = 123 ;

   foo( a ) ; // 124
   foo( a ) ; // 125
}
// 配列でのポインタ渡し
void foo( int x[] ) {
   x[0]++ ;
   printf( "%d¥n" , x[0] ) ;
}
void main() {
   int a[1] = { 123 } ;

   foo( a ) ; // 124
   foo( a ) ; // 125
}

整数型の数値範囲

整数型などの数値範囲について説明を行うために、2の補数表現を復習したあと、 数値の範囲について説明する。

type          | range     | unsigned |    signed
--------------+-----------+----------+---------------
char          | 8bit      | 0..255   |   -128..127
short int     | 16bit     | 0..65535 | -32768..32767
int           | 32bit     | 0..2^32-1|  -2^31..2^31-1
long int      | ?32bit?   |          |
long long int | gcc 64bit | 0..2^64-1|  -2^63..2^63-1

数値範囲の大まかな計算のための2つの方法として、 や、 10進数での桁数の概算のために、 より、 といった計算を行う方法について説明。

次週は、16bitコンピュータで int が簡単に桁あふれする問題や、 2038年問題や2004年問題などを解説する予定。