プログラミングの小ネタ


フィリップフロップ

この行を実行するたびに,iの値は-1,1,-1,1,...,と規則的に切り替わる.1命令で実装できる.

この行を実行するたびに,iの値は0,1,0,1,0,1,...,と規則的に切り替わる.1命令で実装できる.符号なし型の変数で実装できる.

この行を実行するたびに,iの値は0,1,2,...,9,0,1,2,...,と10の周期で規則的に切り替わる.

あるいは,

前述した方式の系.Kが2のべき乗である場合,ビット演算子のひとつであるand演算で実装可能.プロセッサと最適化法によってはこちらのほうが高速.

ビット演算子の優先順位

C言語においては,ビット演算子&の演算優先順位は比較演算子より低い.加法演算子+と同じ感覚で使うとバグを誘発しがち.たとえば,

というプログラムがあったとする.一見,変数aの下位8bitが0x04と等しいかチェックする条件式に見えるが,そうではない.実際は,演算子==と演算子&では演算子&の方が優先順位が高いため,以下のように解釈される.

このままでは常にif文の条件式の演算結果が0になってしまう.ビット演算子を使う場合は常に()をつけるほうがよい.

浮動小数点型変数におけるまるめ誤差・桁落ち

以下のようなfor文をかんがえる.

counter変数には何回ループが実行されたかがはいる.一見,1000/0.01=100000が出力結果のように思える.しかし,このプログラムは次のような出力をおこなう.

一回余分にループをおこなっていることが確認できる.

これは,コンピュータは0.01を有限2進小数として一旦まるめているためおこる問題である.すなわち,コンピュータは0.01を0.009*********と認識している.この誤差が積み重なることによって,この問題が発生する.同様の理由で,以下のコードはfor文をぬけず,暴走する.

0.01をいくら積み重ねても,1000と等しくならない.ループは整数型でまわしたほうが無難である.あるいは,以下のように適当に微小な数字を用意し,範囲でしぼむことが考えられる.

この手のノウハウはACM国際大学対抗プロ グラミングコンテストで多く学ぶことができるので,興味が向いた読者はそちらにチャレンジしてみるのもよいかもしれない.また,数値の扱いに関する諸問題に詳しい解説がある.

有理数体での演算

浮動小数点で演算をおこす限り,まるめ誤差の問題から逃れることはできない.演算の回数が少ないのであれば,浮動小数点ではなく,有理数で数を表現することにすれば,(分母・分子のいずれかがオーバーフローするまでの間は)誤差なく演算が行われる.例えば,2/3を整数2と整数3のペア,4/3を整数4と整数3のペアとしてプログラム上で表現することにする.乗算をする場合は,2*4,3*3を計算し,整数8と整数9のペアを出力すればよい.
たし算をする場合は当然約分が必要である.コーディングは少しめんどくさい.

double,float型変数の暗黙なキャストについて

こじまうすblogより.

コンパイラの設定によっては,プログラム内で1.0001と書いただけでは倍精度と判断される恐れがある.floatのような単精度で高速演算をしているつもりが,キャストした後に倍精度演算を行っている場合がありえる.単精度演算を行いたいなら,コンパイラの設定を見直す・定数は1.0001Fのように単精度であることを明示するなどの工夫が必要である.

固定小数点方式

変数の扱う範囲が有界であるなら,整数型演算によって,固定小数点方式をエミュレートしてもよい.誤差が乗ることにかわりはないが,浮動小数点ほどは誤差は乗らない.また,実際の演算は整数型変数でおこなうため,浮動小数点型より高速.ただし,極端に大きい数・極端に小さい数を扱うことはできないので注意が必要.

たとえば,0.0, 0.01, 0.02, 0.03, ..., 10.0の範囲の数字を扱う場合を考える.0.0=0/100, 0.01=1/100, 0.02=2/100, ..., 10.0=1000/100と,これらの小数は分数で表現できる.この分子部分のみを変数として記憶し,有理数体で四則演算を行えばよい.0.03+0.05を演算することを考えよう.この式は(3/100)+(5/100)とひとしいため,3+5を整数演算で計算する.この結果は整数8である.すなわち,(8/100)が計算結果である.0.1*5.0を演算することを考えよう.この式は(10/100)*(500/100)とひとしいため,分子の答えは5000.分母の答えは100000.ただし,分数の分子のみを変数として記憶するため,分母を100に正規化する.すなわち,5000を100で割って,50/100が計算結果である.

この例では分母を100にしたが,分母をint型で扱える最大値に設定すれば,より正確に演算ができる.

四捨五入

整数型から浮動小数点型にキャストをすると,小数点以下が切り捨てられる.この仕様を活用することで四捨五入が実装できる.

ただし,i>=0である必要がある.

unsignedを使うときの注意

このように引き算を行うと,引き算の結果はsigned intになるので,型のキャストが暗黙に行われます.コンパイラによっては「精度落ち」の警告を発します.また,a=1,b=2の場合にcの値が巨大な値になる可能性があるため,RAM節約のためにunsignedを使う場合には注意が必要です.

シフト命令

以下のようなソースを考える.

この機能はシフト命令を使って,以下のようにも実装できる.

SH7147では,シフト命令は1ステート,掛け算は2~5ステート必要であるから,シフト命令実装が得に見える.ところが,1bit,2bit,8bit,16bitシフト命令はあっても,nbitシフト命令はない(少なくともハードウェアマニュアルには記述がない).そのため,複数回のシフト命令が実行される可能性がある.

実際に実装してみると,前者の掛け算で実装した場合のほうが実行時間は短かった.おそらく最適化の都合でわずかに後者に無駄なコードが混ざったと考えられる.

何でもかんでもシフト命令でやれば早くなるというわけではないようだ.

関数のインライン展開

一般的なマイクロマウスロボットでは,プログラムサイズとROMサイズでは後者が巨大であることが多い.また,関数はオーバーヘッドが(思ったより)大きく,プログラムの実行速度を大幅に低下させる.

関数のインライン展開は重要である.SHマイコンの場合,

のように,関数直前に#pragma命令を配置することでインライン展開を指定できる.(Cコンパイラマニュアルを参照のこと.)

エンディアンに注意する

STM32F103xxシリーズはLittle Endian formatになっている.共用体を使って,適当なbitにアクセスできるプログラムを書く場合,直観とは異なるbitにアクセスすることになってしまうので注意.(詳しくは,エンディアンを参照)ビッグエンディアンフォーマットがメモリの実装として採用されているハードウェアを採用するなら良いが,リトルエンディアンフォーマットが採用されているハードウェアを使う場合,メモリ番地を陽に指定してアクセスすることを避けたほうが良いかもしれない.

乱数

探索ルーチンで使われます.

  • ランダムに歩くだけのネタ探査アルゴリズム
  • 複数の同コスト行動があった場合にランダムで選ぶ場合

rendom(int max){

0からmaxまでの乱数をかえす.RAND_MAXが小さいときに偏りををおこす.

0からmaxまでの乱数をかえす.RAND_MAXが小さいときおこる乱数の偏りをなくしてくれる.+1.0部分でfloatにキャストされている点がポイント.

文字列から浮動小数点型へ変換

文字列から浮動小数点型へ変換する場合,stdlib.hにあるatof関数が便利です.ところが,標準ライブラリはROM容量を圧迫する傾向があります.

自作関数と比べてサイズが小さい側を採用するといいでしょう.

==3x3逆行列プログラム==
マウスには使わないかもしれません.(これを使う制御を開発中.)

外部リンク