Thursday, February 19, 2009

Enabling root login for MacOS X

# Open the Directory Utility app from Applications - Utility
# Ensure the settings are unlocked (click the lock if necessary)
# Choose Edit > Enable Root User and provide the root user password.

from http://www.oracle.com/technology/products/jdev/htdocs/11/knownissues.html#install4

Tuesday, May 29, 2007

Addicted to Succinct

Since last year, I've been addicted to Succinct Data Structure.
Not yet "complete" region, it seems that new technology emerge each month related to this issue.

One of the algorithms “derived” from this is calculating [rank] and [select] for a given bit string.
For example;

Given bit string
0011 0000 0101 0111
rank(10) =3 … counts of “1” to 10th bit
select(3)=10 … the 3rd “1” is in 10th bit

What I find this interesting is that not only “search index” of calculating rank and select is succinct, but also, this calculation can be done in O(1) regardless of size for any given bit string.

For this calculation, there’s a need to count the number of “1”s in constant bits (for example for 64 bits). This problem (counting bits) is called by many, “the popcount problem” or “the population count”.

It seems that there are many ways to count bits. The fastest maybe is using SSSE3 POPCNT of new Intel processors.
Calculating in older CPU?
After surfing the web a bit, I found it amazing that most of the web pages say that using “bit shift” seems faster than using “predefined tables”

[predefined table]

unsigned char table[256];
void initialize_table()
{
for (int i = 0; i < 256; i++) {
table[i] = count8bit(i);
}
}

unsigned long long count64bit_table(unsigned long long x)
{
int n = 0;
n += table[x & 0xff];
n += table[(x >> 8) & 0xff];
n += table[(x >> 16) & 0xff];
n += table[(x >> 24) & 0xff];
n += table[(x >> 32) & 0xff];
n += table[(x >> 40) & 0xff];
n += table[(x >> 48) & 0xff];
n += table[(x >> 56) & 0xff];
return n;
}


[bit shift]

unsigned long long count64bit_shift(unsigned long long x)
{
x = ((x & 0xaaaaaaaaaaaaaaaaULL) >> 1)
+ (x &amp; 0x5555555555555555ULL);
x = ((x & 0xccccccccccccccccULL) >> 2)
+ (x & 0x3333333333333333ULL);
x = ((x & 0xf0f0f0f0f0f0f0f0ULL) >> 4)
+ (x & 0x0f0f0f0f0f0f0f0fULL);
x = ((x & 0xff00ff00ff00ff00ULL) >> 8)
+ (x & 0x00ff00ff00ff00ffULL);
x = ((x & 0xffff0000ffff0000ULL) >> 16)
+ (x & 0x0000ffff0000ffffULL);
x = ((x & 0xffffffff00000000ULL) >> 32)
+ (x & 0x00000000ffffffffULL);
return x;
}


To be sure, I coded and ran it in my Pentium M machine (Windows XP).
I also wanted to know the difference between C and Java.
Looping the calculation for 10,000,000,000 times, and running 3 times.

The conclusion...

[gcc (without any optimization)]

Input hexadecimal string of 64bit:11ff11ff00ff00ff
Calculating value 1296775004637036799 : 0x11ff11ff00ff00ffULL. Loop:100000*100000
Calculating loop:0...
count64bit_table(0x11ff11ff00ff00ffULL) Count:36 Time:300.752
count64bit_shift(0x11ff11ff00ff00ffULL) Count:36 Time:487.030
Calculating loop:1...
count64bit_table(0x11ff11ff00ff00ffULL) Count:36 Time:299.691
count64bit_shift(0x11ff11ff00ff00ffULL) Count:36 Time:486.098
Calculating loop:2...
count64bit_table(0x11ff11ff00ff00ffULL) Count:36 Time:301.694
count64bit_shift(0x11ff11ff00ff00ffULL) Count:36 Time:489.855


[gcc -O3]

Input hexadecimal string of 64bit:11ff11ff00ff00ff
Calculating value 1296775004637036799 : 0x11ff11ffff00ffULL. Loop:100000*100000
Calculating loop:0...
count64bit_table(0x11ff11ff00ff00ffULL) Count:36 Time:5.858
count64bit_shift(0x11ff11ff00ff00ffULL) Count:36 Time:5.648
Calculating loop:1...
count64bit_table(0x11ff11ff00ff00ffULL) Count:36 Time:5.658
count64bit_shift(0x11ff11ff00ff00ffULL) Count:36 Time:5.678
Calculating loop:2...
count64bit_table(0x11ff11ff00ff00ffULL) Count:36 Time:5.679
count64bit_shift(0x11ff11ff00ff00ffULL) Count:36 Time:5.628


[java (client JVM, Sun 1.5.0_11)]

Input hexadecimal string of 64bit:
11ff11ff00ff00ff
Calculating value 1296775004637036799 : 0x11ff11ff00ff00ffULL. Loop:100000*100000
Calculating loop:0...
count64bit_table(0x11ff11ff ff00ffULL) Count:36 Time:433.834
count64bit_shift(0x11ff11ff ff00ffULL) Count:36 Time:365.485
Calculating loop:1...
count64bit_table(0x11ff11ff ff00ffULL) Count:36 Time:435.066
count64bit_shift(0x11ff11ff ff00ffULL) Count:36 Time:366.146
Calculating loop:2...
count64bit_table(0x11ff11ff ff00ffULL) Count:36 Time:433.744
count64bit_shift(0x11ff11ff ff00ffULL) Count:36 Time:365.856


[java -server]
Input hexadecimal string of 64bit:
11ff11ff00ff00ff
Calculating value 1296775004637036799 : 0x11ff11ff00ff00ffULL. Loop:100000*100000
Calculating loop:0...
count64bit_table(0x11ff11ff ff00ffULL) Count:36 Time:275.627
count64bit_shift(0x11ff11ff ff00ffULL) Count:36 Time:42.952
Calculating loop:1...
count64bit_table(0x11ff11ff ff00ffULL) Count:36 Time:121.685
count64bit_shift(0x11ff11ff ff00ffULL) Count:36 Time:43.142
Calculating loop:2...
count64bit_table(0x11ff11ff ff00ffULL) Count:36 Time:121.194
count64bit_shift(0x11ff11ff ff00ffULL) Count:36 Time:42.651


Quite interesting results!
And yes, Sun java library Integer.countBits() and Long.countBits() are using bit shift algorithms.

Sunday, November 19, 2006

Kinokuniya


自宅にネットワークがないことをいいことに、更新していなかったのだが復活。

自宅の近所に日系スーパーマーケットのMitsuwaと 紀伊国屋がある。紀伊国屋の売り上げトップリストがあった。
さすがSiliconValley? 面白いですね。

Tuesday, August 29, 2006

シリコンバレー生活 … 3日目

こちらに来て最初の月曜日。
アメリカでの大金の移動(車を買う、家を借りるなどなど)は銀行振り込みではなく、チェックが主流。
そのためにも朝一でサンフランシスコにある銀行に行って口座の開設を行った。
4business daysほどでチェックが手元に届くとのこと。

実際にはチェックが来てから車を買うことになるのだが、とりあえず感覚をつかむために銀行から帰る途中で中古車ディーラーへ立ち寄ってみた。
日本ではマツダのロードスターに乗っていたが、アメリカでは実用性重視(コストパフォーマンス重視?)、ということで日本車セダン系にしようかと考えている。
立ち寄ったのはホンダ系の中古車ディーラーなのだが、出てきた営業マンはつい先週まで隣のフォルクスワゴンの営業マンだったらしい。こちらに来ている同僚(3週間前にこちらに来た)がフォルクスワゴンを買ったのだが、そのときに対応した営業マンだそうだ。。。
彼曰く、日本車は売るのが簡単だからね~、とのこと。

「売るのが簡単」でもフツウ、隣にあるライバル(?)へサクッと移動するものなのか??
それともこれがアメリカ流なのか。。

中古車の価格の目安はKelly Blue Guide(http://www.kbb.com/)で調べられるが、一般にディーラー系の場合、このガイドより幾分高くなるらしい。
いわゆる諸費用はナンバープレートが生きていれば(日本で言う車検か?)購入額の約10%とのこと。
中古車の場合、とにかく値切り交渉がすべてな気がする。
今日紹介してもらった車など最初に提示された額はKelly Blue Guideの約1.5倍。最終的にそこそこに落ち着いたが、、、

とりあえずこの営業マンとお友達になっておいて「今日はピンとこなかったけど、また来るよ」とか適当なことを言って早々に退散した。

Monday, August 28, 2006

シリコンバレーでの道 … 2日目

さて昨日は、サンフランシスコ国際空港に着くとまずはレンタカーを借りた。

そのレンタカーがGPS付きだったのだが。。日本のカーナビとはまるで違う。

日本のカーナビは地図とナビゲーションが主体に見えるが、こちらのはGPS受信機におまけとして地図とナビゲーションが付属している感じ(メーカもMagellanということはGPSが主体なわけも納得)。画面も異様に小さい。

早速ホテルの住所を入れて ドライブスタート。
せっかくサンフランシスコに来たのだから、ゴールデンゲートブリッジを経由してから、と思ったのだけど、GPSがなかなか言うことを聞いてくれない。結局フリーウェイをぐるぐると迷ったあげく、ゴールデンゲートブリッジは断念。素直にホテルに向かった。
ちなみに悪態ばかりついたこのGPS、目的地にまっすぐ到着するためには結構優れもの。道がまったく分からない初心者には強い味方ですね。道を覚えないのが難だけど。。。
チェックイン後は道を覚える意味もあって、とりあえず日本の食料品店と本屋、それに近くにある大型コンピュータショップをインターネットで調べていってみた。
拍子抜けするほどあっけなく目的に到着し、GPS大活躍です。

Saturday, August 26, 2006

シリコンバレーでの道 … 1日目

出発10日前を最後に途絶えていたこのブログ、今日とうとうアメリカ西海岸の地を踏みました。

正直10日そこらでアメリカ行きを準備するのは正気ではない。それでもなんとか(周りに迷惑かけて?)今ここにいることが素直にうれしい。

これに懲りずに、今後はシリコンバレー「での」道を書いてみる。

Thursday, August 17, 2006

シリコンバレーへの道…2

(出発まで10日)

今日までにやったこと
・Amexの申請
・家を出ることを大家に伝えた
・アメリカに行く飛行機の手配
アメリカに着いてから1週間分の
 ・宿を予約
 ・レンタカーを予約

今日やったこと
・引越し業者の手配
  …VISAがまだ取得できていないので、アメリカに荷物を送ることができない。そのため、いったん実家に預けることに。
・実家に電話
  …「荷物3ヶ月ほど預けさせてね」コール

今後のTODO
まだまだ山ほど。。。