桁上げ伝播長 - 初学者の箸置

加算器の高速化、というとハードウェアの教科書ではお馴染みのテーマで、よく知られたcarry lookaheadとか、carry飛ばしまくる block skipとか,選ばれるのは一人だけの一子相伝 Carry selectとか、carry operatorで縮退していくタイプのKogge-Stone, Brent-Kungの類とか、かなり奥が深い。しかし結局は並列計算が困難なcarry(桁上げ)伝播を如何に切り刻むか、が肝になってくる。
そんな中でcarry伝播の完了を検出することで「加速できるとこは加速しちゃおう」という発想（同期設計では微妙だけど。。。）の方法もあって、これ何かに使えないかなーとか考えてるんだけど、その前提になっている「連続するcarry伝播長の平均値は、√n程度」（うろ覚え、後で確認する)というのが「ホンマですか？」と気になってくる。妙に気になる。で、pythonさんに聞いてみる*1

class binary(list):
    def __init__(self, value):
	self.value = value
	self.bin   = []
	for shift in xrange(32):
	    self.bin.append((value >> shift) &1)

    def __getitem__(self, index):
	if index in xrange(0, 32):
	    return self.bin[index]
	else:
	    return 0

    def __setitem__(self, index, value):
	if index in xrange(0, 32):
	    self.bin[index] = value
	    return self.bin[index]
	else:
	    return 0

def add(a, b):
    bin_a, bin_b = binary(a), binary(b)

    prev_c =  c = 0
    #s = 0

    counter = 0
    max = 0
    for i in xrange(32):
	_a, _b = bin_a[i], bin_b[i]

	#s = (_a ^ _b) ^ c
	c = (_a & _b) | ((_a ^ _b) & c)
	#print _a, _b, "=", s, c

	if c:
	    counter += 1
	else:
	    if counter > max:
		max = counter
	    counter = 0
    return max

if __name__ == "__main__":
    for bits in xrange(2, 16+1):
	upper   = 2**bits
	bitseq  = [add(x,y) for x in xrange(upper) for y in xrange(upper)]
	length  = float(len(bitseq))
	total   = sum(bitseq)
	avg     = total/length
	hist    = [bitseq.count(i) for i in xrange(bits+1)]

	print "= %dbits =" % bits
	print avg
	print sum([(x-avg)**2 for x in bitseq]) / length
	print hist

結果が以下。

= 2bits =
0.625
0.609375
[9, 4, 3]
= 3bits =
1.046875
1.16967773438
[27, 16, 12, 9]
= 4bits =
1.48046875
1.79649353027
[81, 61, 51, 36, 27]
= 5bits =
1.90234375
2.44358825684
[243, 226, 213, 153, 108, 81]
= 6bits =
2.30517578125
3.09094977379
[729, 820, 855, 666, 459, 324, 243]
= 7bits =
2.68310546875
3.72489523888
[2187, 2929, 3357, 2835, 1998, 1377, 972, 729]
= 8bits =
3.03663635254
4.34129388607
[6561, 10336, 12972, 11691, 8748, 5994, 4131, 2916, 2187]
= 9bits =
3.36557388306
4.93467314934
[19683, 36124, 49485, 47421, 37503, 26244, 17982, 12393, 8748, 6561]
= 10bits =
3.67217254639
5.50429979049
[59049, 125269, 186846, 190089, 156843, 114696, 78732, 53946, 37179, 26244, 19683]

残りはまださすがに終わんない。あくまで平均が、と言うだけなんだけど、たしかにこれは。。。。