アルゴリズムイントロダクション 練習問題5.1-2

問題：

RANDOM(0,1) に対する呼び出しだけを用いて手続き RANDOM(a,b) を実現せよ。実現された手続きの平均実行時間を a と b の関数として表現せよ。

RANDOM(a,b) とは、a<=x<=bな整数xをランダムに返す関数です。
とりあえず実装まで。

発想：

• RANDOM(a,b)を実現するのはRANDOM(0,n)を実現するのと同値だからこれをやる
• nが2の累乗ならばRANDOM(0,1)をln(n)回やればOKなんだけどなぁ・・・
• あ、無効な値になってしまったときはもう1回やればいいや！

import java.util.Random;

public class Utility {
	// This method means Random(0, 1)
	public static int randomZeroOne() {
		Random random = new Random();
		int result = random.nextInt(2);
		return result;
	}
	
	public static int log2(int n) {
		if (n <= 0) {
			throw new IllegalArgumentException();
		}
		int result = (int) Math.ceil(Math.log(n) / Math.log(2) );
		return result;
	}
	
	public static int random(int a, int b) {
		if (a >= b || a < 0) {
			throw new IllegalArgumentException();
		}
		int result = 0;
		int m = log2(b - a);
		while (true) {
			for (int i = 0; i < m; i++) {
				result += randomZeroOne() * Math.pow(2, i);
			}
			result += a;
			if (result <= b) {
				return result;
			} else {
				result = 0;
			}
		}
	}
}

import com.gmail.seizans.algorithm.Utility;
import static org.hamcrest.CoreMatchers.is;
import static com.gmail.seizans.algorithm.Utility.log2;

public class UtilityTest {
	@Test
	public void log2Test() throws Exception {
		assertThat(log2(1), is(0) );
		assertThat(log2(2), is(1) );
		assertThat(log2(3), is(2) );
		assertThat(log2(4), is(2) );
		assertThat(log2(5), is(3) );
		assertThat(log2(6), is(3) );
		assertThat(log2(7), is(3) );
		assertThat(log2(8), is(3) );
	}
	
	@Test
	public void randomTest() throws Exception {
		int a = 20;
		int b = 30;
		boolean isOk = true;
		int numberOfTrials = 50;
		for (int i = 0; i < numberOfTrials; i++) {
			int r = Utility.random(a, b);
			if (r < a || b < r) {
				isOk = false;
			}
			System.out.println(r);
		}
		assertTrue(isOk);
	}
}

とりあえず動いているかのように見える。
しょっぱい点に気づかれたら教えてくださいませ。どうか。