verilogでの平方根の計算

モンテカルロ囲碁を作成する上で、いづれUCB1を計算しないといけないのですが、

ucb1=勝率 + c * sqrt( 2 * log(全試行数)/その手の試行数)

要するに、勝率と分散の和を「次にシミュレーションする順位」に利用する
（衆院選の比例名簿の順番みたいなもの）

logのことは後回しで、平方根をverilogで計算する方法を調べました。
http://www.green.dti.ne.jp/hwv348/hw/sqrt.html
こちらを参考に入力16bit、出力8bitで単純化して

なかなか効率の良い手法で、短いシーケンスで値が求まりますね(^^)
FPGAが乗算器を持っているという前提ですが、

x=sqrt(y)になるxを与えられたときにyを&h80とまず仮定して、
x*xがyを越えたときはyを大きく減らしつつ、基本的にyを少しづつ増やしていく
ビットをうまく使って、急速に正解に収束するようです。

// 平方根演算器

module sqrt (sout, sin, clk);

	output [7:0] sout;     // 演算結果出力
	output [15:0] sin;      // 入力
	input  clk;
	reg [7:0] sout;    // 演算結果
	reg [15:0] sin;    // 入力
	reg [3:0] bpos;

	wire over= (sout * sout) > sin; // 推定値が大きすぎるフラグ

	initial begin
		sin=25*25;
		sout= 8'h80;//推定値
		bpos=7;
	end

	always @(posedge clk)
	begin
		if(over) sout[bpos]<=0;//推定値が大きすぎるので減らす

		if(bpos>0)
		begin
			sout[bpos-1]<=1;		// 次の推定値
			bpos=bpos-1;
		end
	end

endmodule

625(25^2)の平方根を求める様子

C:\iv\mayu>vvp a.out
VCD info: dumpfile mayu.vcd opened for output.
 0 sin=  625 sout=128
 1 sin=  625 sout= 64
 3 sin=  625 sout= 32
 5 sin=  625 sout= 16
 7 sin=  625 sout= 24
 9 sin=  625 sout= 28
11 sin=  625 sout= 26
13 sin=  625 sout= 25

平方根を求めるだけでもクロックがけっこう入りますけど、
その間に別のシミュレーションをさせれば、
レイテンシ隠蔽できると思います

参考元に乗算器を使わない手法も解説してあった。こっちの方がいいですね

// 平方根演算器
module sqrt (sout, sin, clk);

	output [7:0] sout;     // 演算結果出力
	output [15:0] sin;      // 入力
	input  clk;
	reg [7:0] sout;    // 演算結果
	reg [15:0] sin;    // 入力

	reg [7:0] mod;
	reg [3:0] step;

	initial begin
		sin=66*66;
		sout <= 0;
		mod <= 0;
		step<= 0;
	end

	wire [1:0] add= sin >> (14 - step * 2);	// 降ろしてくる数（an に相当）

	always @(posedge clk)
	begin
		if(step<=7) begin
			if({mod, add} >= {sout, 2'b01}) begin   // 解に１を立てられるか？
				sout<= {sout, 1'b1};                // ＯＫなら、解に１を立てて、
				mod <= {mod, add} - {sout, 2'b01};  // 次の余りを計算
			end
			else begin                  // 解に１が立たない場合
				sout<= {sout, 1'b0};    // 解には０をセットして、
				mod <= {mod, add};      // 次の余りを計算
			end
			step<= step + 1;	// 次のステップへ
		end
	end
endmodule