binary exponentiation

任意の数の累乗を計算する時には、for文で累乗する回数だけ数を掛け合わせる、というのは小学生でも思いつく。だが、累乗する回数が大きくなったとき、例えば1億乗とかやられたときには極端に遅くなるのは明らかだ。

二進累乗法というやり方がある。これは2の累乗に乗数を展開することで、掛ける回数をビット数＋数回に抑えるという考え方だ。累乗する数を1ビットシフトして掛けることで、x^2, x^4, x^8, x^16 ... といった具合で累乗する回数を2の累乗倍に増やしていくことで、累乗する回数を減らすことができる。

累乗する回数を減らすことは、累乗する対象の値が double だった場合に誤差を減らす効果をもたらす。
.... って、言葉で言ってもわけわかんないすよね(´ー｀; )



[ Update September 11th 2012 06:32 JST by m ]

べき乗のアルゴリズムのうち、上位桁から計算する方法 を上記はコードにしたものだ。これの計算量は 最大でも 2 * logN (N は累乗する回数) なので、O(logN) となる。

% operator

http://0xcc.net/blog/archives/000083.html

剰余を求める % 演算子はプログラムの世界では非常によく用いられる。特に一定の範囲の数値があった場合に、剰余が同じ値で数値をグループ化する用途に役立つのは皆様ご存知でしょう。

たまたま2つの値の最大公約数を求める関数を再発明する機会があり、コードを書いていた。この問題に対して、この世界でよくある解法が「ユークリッドの互除法」である。これは以下の手順(※)で成り立つ

1. 2つの値のうち大きなものから小さなものを引く
2. 1. の結果と、値の小さなものについて、上記 1. を繰り返す
3. 1. の結果が0になったとき、その時に引いた小さい値が最大公約数である

上記 2. を繰り返すことは、最終的には値の小さなもので割ったときの余りを求めることと同義なので、この手順は剰余で代用することで速度向上を図るのが普通だ。これをコードにすると以下のような感じである。

b = b % a;

このときに、b と a のどちらか（もしくはいずれか）が負の数値だったらどうなるか。このコードをレビューしていた pascaljp から「オペランドが負の場合、結果も負の場合があるよ」と指摘されてびっくらこいた。

よーく考えると、負の剰余って複数通りの解釈ができる。

7 % -5 -> 余りは -3(商は-2)または 2(商は-1)
-7 % 5 -> 余りは 3(商は-2)または -2(商は-1)
-7 % -5 -> 余りは 3(商は-2)または -2(商は1)

これについては処理系によってまちまちのようで、それを詳しく示したのが上記の高林さんのエントリである。

実際、剰余演算子を使う場合、「余りの値については殆どの場合興味がなく、グループ化する用途には役立ってればいい」という考え方もあるだろうが、今回の場合みたく問題になることもあるんだなと再認識した次第である。

よく考えたら、2つの値の最大公約数を求める場合に、片方または両方が負であっても最大公約数は同じことがわかったのでそれを用いて書き下したのが以下のコードである。



(※) これは A, B の最大公約数をGとすると、B と A - B の最大公約数もGとなるという考え方に基づく。その証明は ここ あたりでもどうぞ。

fibonacci number

fib(param) + fib(param - 1) と本番で書いてしまった。。(※) なんで気付かなかったんだろう（涙

(※)無論、無限ループになる

[ Update January 31st 0:35 JST by mumumu ]

勿論for文でも書ける。こちらの方がスタックを使わない。

[PATCH] Auto/FetchTitle.pm default configuration changes

http://coderepos.org/share/changeset/38602

IRCで http URL が貼られたときにタイトルを自動表示するという処理はよく行われていて、IRCプロキシ tiarra にもそのためのプラグインが実装されている。だがそのいくつかのパラメータが今風じゃないなと思ったのでpatchを当ててコミットした。

- タイムアウト値のデフォルトを3秒から10秒にした
- 取得するHTMLのバイト数を最大4Kから64Kにして、その値を recv_limit として設定可能にした。全部 amazon.co.jp が悪い

ひとつめの変更は、リダイレクトを行うサイトも珍しくないので、3秒では貼られるサイトによってはタイムアウトが頻発するために行った。ふたつめの recv_limit の変更については、回線が細い人にとっては過剰な変更であろう。だからこの値は変更できるようにしておいた。

HTML5 de face recognition

https://developer.mozilla.org/ja/Canvas_tutorial

タイトルだけ書いて、とてつもなく大仰なタイトルだよなオイと思った（藁
要するに下記のようなことをJSでできないの？ と聞かれてHTML5(っぽいもの。validではない）でやってみただけです。ハイ。



canvasって HTML5 の丁度いい入門だと思う。何ができるのって人はこのエントリのはじめに張った MDCのリンクを是非見ると良いと思います。また、IE で下記のコードを動かすには explorercanvas が必要です。

mystery program

Perlって何でもできるよね。いわゆる6曜を計算してくれる実装があったのがPerlだけだったんだよね。DateTimeも便利だよね。モダンPerlには必須だよね (一行独白

[memo] Looking up the past timeline

Twitterのタイムラインを調べて、ちょっとしたワードにマッチしたものを削除する処理が必要になった。さすがにWebインターフェイスから手動で調べるのはやってられない。

Net::Twitter楽だよね。例外処理が微妙にダサイと感じるのはPerlそのものの問題なので置いといて、と。ひっかかったのは マルチバイト文字の正規表現を書くときは、Perlの内部フォーマットである UTF-8フラグが立った状態にしないといけない、という点くらいだろうか。

俺別にPerlが嫌いなわけじゃないんだね、と改めて再認識した。



[ Update January 2nd 20:36:55 JST by m ]

例外処理がちょっとダサイ点については Try::Tiny がちょっとカッコいい！(｀ー´)
tokuhirom さめ情報ありがちょーヽ(´ー｀。)ノ

use Try::Tiny;
try {
    die "error occured!";
} catch {
    warn "caught error: $_";
}

Default answer 'yes' in CPAN?

http://d.hatena.ne.jp/Craftworks/20090415/1239762931

Perl のCPANモジュールをインストールするときに非常にうざいと感じるのが、依存モジュールをインストールする場合に以下のように聞かれる場合があることだ

---- Unsatisfied dependencies detected during ----
----       MIYAGAWA/XML-Atom-0.37.tar.gz      ----
    XML::LibXML [requires]
    XML::XPath [requires]
Shall I follow them and prepend them to the queue
of modules we are processing right now? [yes]

これにデフォルトで 'yes' と答える方法がはじめのリンクでは複数紹介されているが、PERL_AUTOINSTALL='--defaultdeps' は効かなかったので、結局 yesコマンドを使っている。Perl Wizardの方々はこうしてらっしゃるのかしらん(´ー｀; )

[ Update January 2nd 20:21:33 JST by m ]

sudo perl -MCPAN -e shell
CPAN> o conf prerequisites_policy follow
CPAN> o conf commit

tokuhirom さめの教えに従って上記を実行したら自動で入ったす！
これからはこうしておこう(｀ー´)

New Year 2010

あけましておめでとうございます！ 本年も宜しくお願い致します。
今年は迷いをなくし、もっと低レベルなコードで成果を出せたよと言える年にしたいです。それだけですね(｀ー´)

今年のタグ: code, C, C++, assembler, life, marriage, hardware, translation, etc

various Gravity

今や携帯やゲームのコントローラーで一般的になった加速度センサー。Android もそれに対応していて、Java を通じてハードウェアに加えた加速度の値を取り出すことができる。ただ、Android が載っている Linux の仕組み上、ハードウェアに直接 Java がアクセスできるはずもないので、C(++) のコードを経由してデバイスドライバにアクセスする。

----

ところで、Android で加速度センサーにアクセスする C(++)のコードを実装するには、必ず特定のヘッダを実装しなければならない。それが sensors.h だ。加速度センサーは今いる場所の重力加速度(※)を基準にした値がハードウェアから渡ってくることが多いので、上記の sensors.h にも いろいろな場所の重力の値が定義されている。それを以下に引用しておく。

/**
 * Values returned by the accelerometer in various locations in the universe.
 * all values are in SI units (m/s^2)
 */
 
#define GRAVITY_SUN             (275.0f)
#define GRAVITY_MERCURY         (3.70f)
#define GRAVITY_VENUS           (8.87f)
#define GRAVITY_EARTH           (9.80665f)
#define GRAVITY_MOON            (1.6f)
#define GRAVITY_MARS            (3.71f)
#define GRAVITY_JUPITER         (23.12f)
#define GRAVITY_SATURN          (8.96f)
#define GRAVITY_URANUS          (8.69f)
#define GRAVITY_NEPTUNE         (11.0f)
#define GRAVITY_PLUTO           (0.6f)
#define GRAVITY_DEATH_STAR_I    (0.000000353036145f)
#define GRAVITY_THE_ISLAND      (4.815162342f)

こんなところに Android 持ってかねーYO！ という値がたくさん定義されている。誰か DEATH STAR に Android を持っていった人、是非重力加速度の具合を体で感じ、俺に是非教えてください。

----

(※）地球の場合 9.8 m/s^2。物理でやったよね！ 俺はスカーリ忘れてた

sed as grep replacement

デーモン化したプログラムのログを syslog に吐かせていて、そのログのみを抽出したいと考えた。だが、grep(1) もない、awk(1) もない。テキスト系のプログラムで役に立ちそうだったのは cat(1) と sed(1) だけであった ....

サーバやPC上のUNIXで作業をするときは上記のような環境は考えられないわけだが、組み込み環境ではフットプリント（ストレージの消費量）を抑えるためにそういうことが往々にしてある。要するに、sed を grep の代わりとして使いたいわけです ... と思ったとき5分くらい手間取ったのでメモしておく。

----

たとえば、search.txt から regex にマッチする行だけを出力したい場合は、以下のようにする。これは /regex/ という条件文を ! で否定し、d で「マッチしないものを削除する」ことにより、逆にマッチするものを出力するという変なことをしている。

cat search.txt | sed -e '/regex/!d'

正直、こんなことをするのは組み込み環境以外ないし、どうでもいいっちゃいいんだけどね（藁

[memo] malloc, free(3)

http://www.linux.or.jp/JM/html/LDP_man-pages/man3/malloc.3.html

考えてみれば当たり前なんだけど、free(3) に渡すポインタは malloc(3) 等から返ってきたポインタ「そのもの」でなければならない。以下のコードは FreeBSD 6.4 Release だと実行時に「warning: modified (chunk-) pointer」という警告が出る。Linuxだとアボートする。



バッファに構造体の中身をコピーするようなコードを書いているときに、上記のような間違いを犯したことがあるので記録しておく。

misc_register - Linux kernel API

http://d.hatena.ne.jp/TRANSii/20080911/p1

major番号、minor番号をいちいちregister, unregisterしてデバイスファイルをudev経由で作りたくねーよ的な要求は必ずあると思うのだが、さりとて上記のような正規かどうかもわからな いAPIを使うのも躊躇われるので悩ましいところである。

----

とはいえ、Linux kernel プログラミングで３分クッキングは素晴らしい試みだと思う。

やってみて思うのは、C言語がたとえわかっていても前提知識が多すぎる。内部のAPIやディレクトリ構造がバージョンごとに当たり前のように変わる。まあ、後者は開発者たちが一致して決めたポリシーだし、今のプロジェクトのまわし方だと十二分に理に叶っていることなので文句はないのだけれども。

前者の前提知識の量にしても、ひるがえってWebを見たところでそれなりにあるわけだから、まぁ、、というところだろうか。

[memo] bit shift operator

C言語のビットシフト演算子は、左オペレータの幅以上の値を右オペレータに指定した場合、その動作は未定義である。これは規格で定義された動作である。以下、JIS X 3010 2003 (ISO/IEC 9899) P48 より引用する。

6.5.7 ビット単位のシフト演算子
   シフト式：
       加減式
           シフト式 << 加減式
           シフト式 >> 加減式
制約　各オペランドは，整数型をもたなければならない。
意味規則　整数拡張を各オペランドに適用する。結果の型は，左オペランドを拡張した後の
型とする。右オペランドの値が負であるか，又は拡張した左オペランドの幅以上の場合，
その動作は，未定義とする。

----

このことから、ビットパターンを出力する以下のコードは c の値によって動作するか否かが決まる。型によってオペレーターの幅は異なるため、頭の隅にいれておく必要があろう。間違っても俺のように何も考えずに100ビットとかシフトさせようとしないでください(´ー｀; )

#include <stdio.h>

int main(int argc, char *argv[])
{
   unsigned long long a = 65535; // long long は一般に64bitの幅を持つ
   int c;
   for (c = 63; c >= 0;c--) {    // c を 64にすると途端に動作しなくなる
       printf("%d", (int)((a >> c) & 1));
   }
   printf("\n");
   return 0;
}

math

数学が苦手だったので、学生時代の知識を引っ張り出そうとしても急には引っ張り出せないので困る。けど解決できないわけじゃない（一行独白

[memo] How to get Database Metadata by PHP

普段データベースのメタデータを取得する機会なぞあまりない。だが、ORMを弄るときは別だ。ユーザがそうしたものを全部プログラムに書いてくれれば不要なのだが、今時の怠惰なプログラマはそれらを自動生成または補完することを求めるからである。

ということで、ちょっと Creole と adodb の場合を調べたのでメモしておく。test というテーブルのメタデータを取得する流れを記してある。尚、エラー処理は省略してある。

----

1. adodb の場合

require_once 'adodb/adodb.inc.php';

$dsn = 'mysql://foo:bar@localhost/test';
$conn = NewADOConnection($dsn);

//  get ADOFieldObject
//  A field object is a class instance with (name, type, max_length) defined.
//  @see http://phplens.com/adodb/reference.functions.metacolumns.html
$columns = $conn->MetaColumns('test');
foreach ($columns as $column) {
   var_dump($column->name);
   var_dump($column->type);
   var_dump($column->max_length);
}

2. Creole の場合

require_once 'creole/Creole.php';

//   first get DatabaseInfo object.
$dsn = 'mysql://foo:bar@localhost/test';
$conn = Creole::getConnection($dsn);
$info = $conn->getDatabaseInfo();

$test_info = $info->getTable('test');     //  TableInfo object.
$test_columns = $test_info->getColumns(); //  ColumnInfo object.

//  finally get as you like.
//  @see http://creole.phpdb.org/docs/api/creole.metadata/ColumnInfo.html
foreach ($test_columns as $column) {
   var_dump($column->getName());
   var_dump($column->getNativeType());
}

Ethna 2.5.0 preview2 announced

http://sourceforge.jp/forum/forum.php?forum_id=16056

ようやくアナウンスした。小粒な変更しかないように見えるが、PEAR依存が半分外れていることだけでも割と侮れない。まあ、このリリースは次への布石に過ぎない。

preview3 がおそらく本番だ。いよいよ悪名高いDBとSessionまわりに手を入れるからだ。
おそらくUTF-8化くらいアレなんじゃないかな。実装というよりは落としどころを探すのが（藁

フレームワークというのは実装以上に落とし所を探るのが大変だったりする。

naked Programming

最近は PHP をあまり書いていない。ActionScript が専らである。

ところで、家でプログラミングするとき、裸でプログラミングするというスタイルを提唱
したとして、賛同する人はいるんだろうか。いや、いるよねぇ。冬は流石に暖房入れてい
ないと無理だけど、夏とかは気持ちいいと思うんだけどな。

全裸プログラミング、別名ノーガードプログラミング、ともいう（違

要するに、自分の生産性が上がるスタイルであれば何でもいいと思う。そういうありふれ
た結論なのだが、そのために裸になる、という人もいるんでね、と思う。

＃断っておくが流石に職場では自重している

reverse for loop

どうも for 文で逆順ループを書くとき、二つめの式に == を使ってしまう癖が抜けないことに気がついた。たとえば以下のようなコードである。

int a = 255;
int i;
for (i = a; i == 0; i--) {
  // 入る訳ない
}

上記はC言語だが、昨日の朝 PHP でも同じことをやってしまって唖然とした。for 文でなくて while 文とかにした方が俺的には間違いに気付きやすいので、そうした方がいいかもしれない。

逆順でない時には間違えないのに、なんでだろうね(´ー｀; )

m9(*´〜｀) (C language memo)

http://d.hatena.ne.jp/keyword/m9%A1%CA%A1%B0%A7%A5%A1%B0%A1%CB%A5%D7%A5%AE%A5%E3%A1%BC%A1%BC%A1%BC%A5%C3

最近俺的にプギャーな出来事が多い。C言語に関して。

1. static *char func() {} ってナニ！？
2. 「変数はブロックの初めに宣言しなければならない」というANSI(C89) なルールを巡って「gccなんてゆとりコンパイラ使ってるからだ」といわれのないDISをくらう
3. 以前 /.J で書いた このコードがセグる 理由を思い出すのに3分かかった

俺は何も学んでいないのかと唖然とするばかり。書きまくるしかないんだよね(´ー｀; )

----

Cが体に染み付いている人には釈迦に説法でしかないが、自分へのメモとして上記を解説しておく。

※ 1. は当然 *char なんて型はないのでエラーになる(char* はあるけどね！)。関数の引数や変数宣言については絶対に間違わないのだが、関数の戻り値については上記のような間違いを未だによくする(´ー｀; )
※ 2. は gcc4 が C99 なモードでデフォルトは動くから、 int a; a = 1; int b = 100; などというコードをブロックのはじめに書いていても通るのであって、gccが悪いわけではない。こうしたC++的なコードについて、ANSI C 的な警告を出させたければ、-Wall では駄目で、-pedantic オプションをつけてコンパイルする必要がある。
※ 3. は *p == "\n" が、ポインタと文字列の先頭アドレスを比較しているだけであって、実際に文字列比較を行っていないために、無限ループがbreakせず、(たまたま連続して格納されていると思われる) char *envp[] および、それ以降の領域を読んでしまってセグるというもの