atan(x), atan2(y,x)の高速な実装

少し前にatan(x)のテーブル化についての記事を書きましたがソースコードがなかったので あげておきます.  このコードはテーブルのサイズをかなり大きくしたのでROMを2.5KByte程消費します.  
このコードはatan(x)およびatan2(ｙ,x)をfloatの乗算2回, 除算1回で求めることができ, かつ精度はなかなか高いです.  テーブルのサイズを削ればもちろんROM消費は減りますが精度が犠牲になります.  最近のマイコンはROMは比較的潤沢なので, じゃばじゃば使ってしまおうというコンセプトのもと作ったコードなのであしからずです.  ちなみにmathf.hのatan(x)はくっそ重いです.

sqrt(x)と1/sqrt(x)の組み込み向け実装

sqrt(x)と1/sqrt(x)の高速な実装を考えてみます.

sqrt(x)はニュートン法を用いて求めることが多いようです.  ニュートン法はf(x) = 0の解を
求めるためのアルゴリズムです.  問題になるのはニュートン法を実行するときの初期値でしょう.
これはテーブルを用いたりいろいろな方法で見つけます.  しかし, 今回は1/sqrt(x)の高速実装を用いてsqrt(x)を計算するコードを紹介します.

まずは1/sqrt(x)のコードを見てみましょう.
一見???ですがこのコードで1/sqrt(x)が計算できます. wikipediaのhttps://en.wikipedia.org/wiki/Fast_inverse_square_root　に詳細はあります. このコードは前半でbit演算のみで1/sqrt(x)の大体の値を求め, 後半でニュートン法を行い計算の精度を上げています.

1/sqrt(x)が求まればあとはx*1/sqrt(x)でsqrt(x)が得られます. mySqrt(x),invSqrt(x)いずれも精度と速度はニュートン法の回数で調整できます. invSqrt(x)はベクトルの正規化の際等に使えます. たぶん, mathf.hのsqrt(x)を使うよりかは高速だと思います.

arctan(x)のテーブル化

今回は組み込み用途にarctanを使うためにテーブルを利用した実装を考えてみます.
ただ単に定義域を等分割してテーブルを作るのではおもしろくないのでもう少し工夫
をしてみます.

 =====================基本===========================
 ある関数 f(x)を区間[a,b]で考えテーブル化したい ====================================================

1. 区間[a,b]を等分割

 ====================もうちょっと工夫================
ある関数 f(x)を区間[a,b]で考えテーブル化するときに, 
テーブルの幅をf(x)の2階微分の値に応じて変えてみる.

2階微分は関数の傾きの変化率なのでこれが小さいほど
線形近似の精度をあげるのに必要な分割数が減る.



====================================================

===================
arctan(x)でやってみた
===================






あとは16区間毎に普通に線形近似する.  ただし, arctan(x)のxが大きくなったときの値はPI/2に収束するので適当なところで打ち切る.

C++のテンプレートクラスの勉強 リングバッファを利用したキューの実装

今回はC++のテンプレートクラスについて学習したことと, 実際に使用した例としてリングバッファを利用したキューの実装について扱います.

テンプレートクラスについて

C++のテンプレートクラスはクラスを定義するときに複数回出てくるような型を一般的な形で

<class T>のように書いておき(Tが後から指定して使い回したい型)後で型Tを指定する文法です.
要は型は違いますが, 操作は同じものをもったクラス達をまとめて作るために使うものです.  主に
スタックやキューなどのデータ構造の実装に威力を発揮するでしょう.

キューの実装

テンプレートクラスを利用して以下のようなリングバッファを利用したキューを作ってみました.
キューを使う場合に

• 動的にメモリを確保してバッファを作る場合
• あらかじめ確保しておいた領域をバッファとして利用したい場合

のようなシチュエーションが考えられるので, コンストラクタでこれらの選択ができるようにしてあります.  ２つめのシチュエーションはnew演算子を用いてメモリの確保を行うことにかかる時間を節約したいという場合です.  予めRAMの一部をバッファ専用に割り当ててしまうので動的に使えるRAMは減ってしまいますが, 速さが求められる場合には有効です.  2つのシチュエーションの間には速さとメモリのトレードオフがあるわけです.    

最速経路導出アルゴリズムの骨格と乱択足立法

マイクロマウスにおいて2次走行の時間を短縮するためには最速経路導出アルゴリズムの効率化が必要である.  

なんか論文のアブストみたいですね.  今回はこの最速経路導出アルゴリズムについて考察してみたいと思います.  考察と言ってもまずは, 具体的にアルゴリズムの実装方法やアイデアを論じるわけではなくて, プログラムでいう抽象クラスとしてどんな形になるのかな？という考察です.  そして, 考察の後に今実装しようとしているアルゴリズムのアイデアを書いてみます.

まず, 最速経路を定義しておきましょう.  

• 最速経路とは迷路の壁情報と加速度, 最高速度, 各ターンにかかる時間を決めたときに, 考え得る全ての経路のうちマウスが最速タイムでゴールできる経路である.  

よく言われることですが, 加減速とターンがあるマイクロマウスにおいて, 最短経路 ≠ 最速経路なのです.  

じゃあ, 全ての経路をみたら最速経路出るんじゃね?　ってなりますが, マイコンの限られた計算資源と競技時間ではこれは不可能です.  そのため, 実際は

• 最速そうに思える経路を現実的な時間で出すアルゴリズム

を実装することになります.  足立法は上の要件を満たす代表的なアルゴリズムです.

上の定義で重要なのは現実的な時間という文言です.  また書いてませんが現実的メモリ量でという条件も隠れています.  つまり, 使っていい資源は

• メモリ資源（RAM 今のマイコンだとRAMは256kBだから200kBは使える）
• 時間資源 : CPUの計算速度で決まる (競技時間を考えると10秒から長くても1分くらい)

となります.

足立法は実際かなり優秀なアルゴリズムです.  特にいいところは迷路サイズを固定したときに実行時間の上限が評価できることです.  つまり, 固定された時間でまあまあいい経路を出すことができます.  さらに足立法はポテンシャルマップの重みづけのルールをいじると別のまあまあいい経路を出すこともできます.  

さて, 本題です.  単なる足立法だとなかなか最速経路は出せないことは周知の事実だと思います.  そこで, 足立法のようなアルゴリズムの後にさらに別のアルゴリズムで経路を探すことにしましょう.  足立法でまあまあいい経路が出せることは担保できているので, 続くアルゴリズムは10秒くらいで計算を打ち止めします.  

　　Alg1:　固定時間でまあまあいい経路を探すアルゴリズム 

       　　                          +

　　Alg2:　時間を消費してよりよい経路を探し続けるアルゴリズム

 Alg1は足立法をベースにポテンシャルマップの更新方法を変えたものを数通り用意すればいいと思います.  問題はAlg2にはどのようなアルゴリズムをもってくるかです.  経路の全数探索に近いものは幅優先探索を使っても深さ優先探索を使っても適切な枝刈りが必要です.  それに実装がどうしても複雑になりそう...(つくるのがメンドクサイ)

やっぱり, 実装やアイデアはシンプルな方がいいです.  そこでこんなアルゴリズムを実装してみようと思います.  

   ////アイデア////

足立法ベースでポテンシャルの更新に乱数を使用.

      普通の足立法

                        1

                      1 0 1  ← 周りのポテンシャルは+1(定数)で固定

                        1   

       乱数を使った足立法

                          2

                     4   0  3   ←周りのポテンシャルは乱数で決定

                          1  

//////////////////

乱数を使ってポテンシャルを更新する足立法を乱択足立法と呼ぶことにします.  乱択足立法一回あたりにかかる計算時間は疑似乱数の生成が高速ならば足立法とほとんど変わりません.  乱択足立法は呼ぶ毎に違う経路を出すと思われるので, 時間資源が許す限りこれを回します.  その中ででてきた最速経路を出力にします.

まだ, このアルゴリズムは構想しかしておらず実装はしていません.  なのでちゃんといい経路が出てくるかはわかりません.  難しそうなのは乱数でポテンシャルの更新をするときのさじ加減になるのではないでしょうか.  どんな塩梅で重みをランダム化するかがポイントだと思います.  また, ちょっと工夫すると遺伝的アルゴリズムにもできる気がします.(各マスでのポテンシャルの更新のしかたが遺伝子)

結構前に経路導出に乱数を使うってアイデアはあったのですが, いかんせん時間がなくてずっと妄想の域を脱していませんでした.  使いものになるかは微妙ですが結構簡単に作れて面白そうなのでやってみます.  探索問題に乱数を使うというアイデア自体は全く奇抜なものではありませんし, 良くある手法だと思います.  確率的アルゴリズムって結構面白いですよ.  (データ構造だとブルームフィルタとか, 素数判定だとミラーラビン判定法とか..., 乱択クイックソートとか有名?)  

To　doを書いておきます.

////作りたいものたちとTo do/////

1. ランダム迷路生成ソフト
2. 迷路の壁情報と加速度,最高速度,各ターンにかかる時間を渡すと最速経路を出力するソフト
3. 迷路の壁情報と加速度,最高速度,各ターンにかかる時間を渡すとまあまあ最適な経路を定数時間で出力するソフト
4. 迷路の壁情報と加速度,最高速度,各ターンにかかる時間を渡すと局所最適な経路を現実的な時間で出力するソフト

最終的には1.で作った迷路に対し2.と3. and 4.の結果を比較するのがやりたいことです.  

C++の勉強とSTLをマウスで使おうとしたが使えなかった話

どうもです.  最近はマウス関係のプログラムばかりしているような気がします.


唐突ですが, 今C++の勉強をしています.  自分はあまりプログラムはバリバリ書く方ではありませんし, 一応Cとjavaは少しわかりますがマウスを動かすのに必要な最小限の知識くらいしかありません.  なので, 勉強がてらにC++でキレイにマウスのプログラムを書いてみようという感じです.

C++で書くといいかなと思ったもう一つの理由として, マウスのプログラム開発用に作っているソフトをC++で書いているからというのもあります.

C++で開発するメリットと言えばSTLやBoostの存在が一番にあげられます.  Cでコードを書くとどうしてもスタックやキュー, 線形リストなどの実装を何度もせねばならずコードが汚くなります.  そこで, マウスでもSTLを使おうと思っていろいろ頑張ってみました.

が, 結局使えませんでした...

まあ, でもやったことはブログに書いておこうと思います.
//////////////////////////
開発環境 e2studio
マイコン ルネサスのRX631
//////////////////////////
まず, ルネサスのサイトで情報を収集したところ
http://japan.renesas.com/products/tools/coding_tools/compilers_assemblers/Application_Notes.jsp
アプリケーションノートにSTLライブラリの導入方法のドキュメントとSTLライブラリのソースコードを
発見しました.

このドキュメントはHEWでの設定の方法しか書いていないですが, 設定と言ってもダウンロードしたファイルを解凍してインクルードディレクトリのパスに追加するだけなのでe2studioでも同じことをします.

上にあるプロジェクトのプロパティをクリックし↑のようにたどるとインクルードディレクトリを追加できます.

これで, ソースファイルに#include <vector>と追加してコンパイルをしてみたところどうもエラーが
でます.  どうもダウンロードしてきたソース内の_cstddef.h等の複数のヘッダファイルないの

#      include _STLP_NATIVE_CPP_C_HEADER(cstddef)

という部分が原因のようなので試しにこの記述をすべてコメントアウトしました.  するとコンパイルは通るようになって

#include <vector>
using namespace::std

std::vector<int> v;
と記述してもコンパイルはとおります.
しかし, vectorのpush_back()を使うとコンパイルエラーになってしまいました...


v.push_back(1);  //コンパイルエラー

これで, 結構いろいろ頑張ってみてもちゃんとvectorが使えなかったのでe2studioではなくてCS+(Cube suite+??)をダウンロードしてきてSTLを同様にインクルードディレクトリに入れたところ

#      include _STLP_NATIVE_CPP_C_HEADER(cstddef)

ではコンパイルエラーをはかず, いけたかなと思ったのですが, 結局vectorのpush_back()は使えませんでした.  しかし, push_back()以外の他の関数やstackは使えるようです??

#include <vector>
#include <stack>
using namespace std;


void main(void)
{
std::vector<float> hoge;       //コンパイル通る
hoge.push_back(1.0);           //コンパイル通らない
   
std::stack<float> hogehoge; //コンパイル通る
hogehoge.push(1.0);            //コンパイル通る
}

いろいろ調べるとiostreamが既存のものとSTLportのもので競合しているのが原因??
かなというところまではわかったのですが, なんか面倒くさいので結局STLの機能のうち必要なものを勉強がてらにTemplateで実装することにしました.

ふう, 疲れましたね.

ランダム迷路を生成するソフトのアイデア

今年はブログをちゃんと更新すると決めたので更新します.
でも, いつ嘘になるかわかりませんが....


さて, 前回作ると言っていた迷路を読み書きするソフトは完成しました.




なので次はランダムに迷路を生成するソフトの作成です.

ランダムに迷路を生成すると言ってもそんなに大げさなことはしません.  アイデアは
次です.

1. 迷路の外周以外の壁のあるなしをそれぞれ, 疑似乱数を用いて設定
2. 迷路がマウスの迷路のルールに則っているようにする
3. 迷路がゴール可能なものかどうか判定(足立法でスタート区画のポテンシャルが∞になっていたらゴール不能)
4. 1.から3.をゴール可能な迷路が欲しい数得られるまで繰り返す.

ここで, マウスの迷路のルールは以下です.  

• ゴール領域は4x4
• ＆一区画に壁が1つはある
• ＆スタート区画の北側は壁がない

正直, 力技以外の何物でもありません.  本当は同型な迷路を除くような処理も入れるべきですが, めんどくさくて効果が薄そうなものには手をかけないことにします.  今年はなるべく実装が簡単で効果が高くやったら面白いものを優先的に作るというのを行動原理にしています.  

この方法でやってみてあまりにも偏った迷路ばかりが生成されたならばもっとほかの方法を検討してみたいと思います.  

次にやること ～最速経路導出をなんとかする～

おひさしぶりです.  全日本大会が終わってから
まったくマウスの方はできてませんでしたが, 徐々に
進めて行きたいと思います. 

さて, 次にやろうと思うことですが, 最速経路導出を
ちゃんとやるアルゴリズムを書くことです. 
しかし, そのためには少なくとも次が必要になります.

1.   PC上でアルゴリズムの動きを観察できるソフトの作成
2.   アルゴリズムを定量的に評価するためのランダム迷路ジェネレータ

1.ですが, 昔DXライブラリを使って迷路が読み書きできるものは作ったので,
再びDXライブラリを使って作ろうと思います.(昔作ったソフトは昔のPCの中に
あって実家に帰らないと使えない...)  現在, マウスはC++でコードを書いているので
直接アルゴリズムをコピペして動かせるものをつくりたいと思います. 

2.はたぶんそんなに難しくないので1.ができたらさくっと作ります. 

最速経路導出は今までしておらず, この機会にちゃんと作りたい気分になったので
気分が乗っているうちに作ってしまいたいと思います. 

需要があるかわかりませんが,
以下数回に分けてDXライブラリの導入方法などを解説していく予定です. 
今年はちゃんとブログを更新するかな？

ちなみに画像しかなかったですが昔作ったインターフェースはこんな感じでした.
なんか, GBCのゲームみたいな感じですね.