「2^a を与えられたときに a を求める(ただし 1≦ a ≦9)」記事へのコメント

別解

[t-nissie (8647)]

if (x.eq.1) return 0
if (x.eq.2) return 1
if (x.eq.4) return 2
if (x.eq.8) return 3
（中略）
if (x.eq.512) return 9
stop 'illegal x'

こっちの方が見通しがよいしx=1に対応できますが、
ぼくがなにか勘違いしているのかな。

--
love && peace && free_software
t-nissie

Re:別解

[TarZ (28055)]

　合っていると思います。が、元々の問題の要請が、なるべくループやlogを使わない（でもってできればステップも減らしたい）なのです。
　ということで、1, 2, 4, ... 512 の完全最小ハッシュを作る、というのが最小の解のようです。（乗算x1, ビットシフトx1, インデックスメモリ参照x1）

Re:別解

[okky (2487)]

多分その解は『何をもって最小と言うのか』に強く依存していると思う。
例えば、ハッシュテーブルを作るための計算量が丸々無視されている。

メモリをいくら使っても構わないのであれば 0..512 の 513エントリの表を持てばいいだけです。そういう意味ではTable Lookupは最後の手段だと思いますね。

.

いや、実生活で本当にこういう問題があるなら話は別だけどさ。誰がどう見ても『学生演習』の類だもの。こういうのは趣味丸出しにしないと＼(^o^)／

--
fjの教祖様

Re:別解

[t-nissie (8647)]

> ということで、1, 2, 4, ... 512 の完全最小ハッシュを作る、というのが最小の解のようです。

これが題意か。納得。しかし、

>（乗算x1, ビットシフトx1, インデックスメモリ参照x1）

ここまで小さくできないです。これがぼくの限界か（32bit限定だし）：

#define func1to9(x) ( 9 - (2271560481U*(x>>1)*(x>>1)*(x>>1)*(x>>1) >> 28) )
#define func0to8(x) ( 8 - (2271560481U*x*x*x*x >> 28) )

0≦a≦8のほうが綺麗に書けるから、わざわざ1≦a≦9にしているのを使っていないのか…

--
love && peace && free_software
t-nissie

Re:別解

[TarZ (28055)]

　今見つかっている最小のハッシュ関数はこれですね。乗算とシフト、11バイト+終端1バイトのテーブルを使います。どうやって求めたのかは私も解りません。

"\1\2\3\010\6\4\011__\7\5"[n*0x5300000>>28];