tarosukeの日記： めも 6
日記 by
tarosuke
nが2mだということは、つまりその値をかけるということがシフトと同義であるということでもある。だとするなら".."[n * x >> y]のxは4bits(16bits版なので)の窓をスライドしていったときに出てくるパターンがユニークであるという条件を満たすパターンになる。
4bitsの窓はオーバーフローとシフトによるビットロストで作る。xのパターンを探したらあとはxとyで4bitsのウインドウができるようにビット位置を調節するだけ。
xのパターンは、手順としてはまだわからんが16bits版の場合ケツを01111000に決めてしまえば探索範囲は狭くなる。011110000にして最後を0にする方法もあるだろうけど。んで、この場合ここにはf,e,c,8のパターンが含まれているのでこれ以外のパターンになるように、パターンが重ならないようにビットを前に追加していく(このアルゴリズムはわからん)。
解がいっぱいありそうなので探索でもそう難しくないと思う。
# って、あの値、間違ってたら赤っ恥だなー。
--
ぐはぁ。赤っ恥だorz
--
011110000にして最後を0にした方が探索範囲が狭いが...。
n bit で表現できる全てのビットパターンを… (スコア:1)
多分、「乗算」対象の定数はこのビットパターンの一部分(必要なところだけを残してあとは0でマスクしたもの)だと思います。
問題は。はて…そのpackしたビットパターン、対照性を考慮したら一位決定だったっけか??? という辺り。ちゃんと覚えてないです。
fjの教祖様
Re:n bit で表現できる全てのビットパターンを… (スコア:1)
最初の方で云ってる「窓」がそれ。
マスクは意味的には正しいが演算的には乗算とシフトに吸収できるので無駄ってとこ。
# 逆順にすればシフトの代わりにマスクでできるかな(でもシフトの方が値が小さいので有利な事が多いかもね)？
んで、条件を満たす値はたぶん一つじゃないと思うけど、ここでは全ての値を求めようとしてるんじゃなくて一つでいいから簡単に求めようという方針なので一意かどうかはあんまり問題じゃない。9bitsみたいに中途半端な長さで最短の表を見つけようとする時には関係あるかもしれないが。
Re:n bit で表現できる全てのビットパターンを… (スコア:1)
あー、うん。そうなんだけれど、そうは言っても今回のように a=[0..8] な時に、lookup table を短くしようとすると出力 o(a) の範囲もなるべく [0..8] から大きく逸脱したくない。間違っても [7..15] なんて範囲の値を出されて lookup table の最初の7個は無駄です…なんてうれしくないわけで。
あと、この手のビットパッキング問題って大抵がNPと予測されている。で、いくつか例外的に Pで済む場合があるのだけれど、確かそのためには解が一通りでは駄目だった気が…なんかそんな条件があった気がするんですよ。
『Pで済む』場合って大抵、アルゴリズムが判っている、という意味なのであとはどこかに落ちているだろう、と。NPしか判っていないって事は(枝刈りの方法はあるんだろうけれど)基本的に総当たり戦、という意味になる。
fjの教祖様
Re:n bit で表現できる全てのビットパターンを… (スコア:1)
うん、だから「9bitsみたいに中途半端な長さで最短の表を見つけようとする時には関係あるかもしれないが」と書いたようにその問題なら関係あるかもね。でもここではちょっと違ってて、7bytesくらい無駄でもビット演算とマスクでやるよか速かったり短かったりすればOK、でも一般化はしたい。という方向を指向してるんだ。だからnを2mに切り上げて問題が9bitsでも16bitsの値とテーブルでOKなんだ。
＞いくつか例外的にPで済む場合があるのだけれど、確かそのためには解が一通りでは駄目だった気が...基本的に総当たり戦
いまいち意味が掴めないけど次の日記 [srad.jp]も読んでくだされ。少なくとも8,16,32bitsの場合には探索無しで求まってるから。んで、これが例外的な一パターンでも簡単で一般化された(しかも実行時計算ではない)解法なので俺的にはOK。
Re:n bit で表現できる全てのビットパターンを… (スコア:1)
そして、8bits ならば必要なビット長は 256+8-1=263bitあるはずだし、32bitに至っては 4G+31 bitになるはずだ。
というわけで、ここで求めているものが『何を目標にしているのやら』よく判らない。
fjの教祖様
Re:n bit で表現できる全てのビットパターンを… (スコア:1)
# パターンのサイズでわかると思うがなー。