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

問題

0と1をそれぞれ確率1/2で出力する問題を考える。利用できるのは0か1かを出力する手続きBIASED-RANDOMである。BIASED-RANDOMは1を確率p、0を確率1-pで出力する(0

やっぱり実装まで。期待実行時間は出していない。あと証明もまだ(これはたぶんすぐできる)。
発想

• PK戦のサドンデスで、先攻が勝ったら1、後攻が勝ったら0を返すとすればよい

public class Utility {
	public static boolean randomBoolean() {
		boolean a = true;
		boolean b = true;
		double p = 0.7;		// Any p is OK. s.t. 0 < p < 1
		while (!(a ^ b) ) {
			a = randomBooleanByProbability(p);
			b = randomBooleanByProbability(p);
		}
		return a;
	}

	// BIASED-RANDOM
	public static boolean randomBooleanByProbability(double p) {
		if (Math.random() < p ) return true;
		else return false;
	}
}

import static org.junit.Assert.*;
import org.junit.Test;
import com.gmail.seizans.algorithm.Utility;

public class UtilityTest {
	@Test
	public void randomBooleanTest() throws Exception {
		int numberOfTrials = 20000;
		double minProb = 0.95;
		double maxProb = 1.05;
		int counter = 0;
		boolean isOk = false;
		for (int i = 0; i < numberOfTrials; i++) {
			if (Utility.randomBoolean() ) counter++;
		}
		if (numberOfTrials * minProb < counter * 2 && counter * 2 < numberOfTrials * maxProb ) {
			isOk = true;
		}
		assertTrue(isOk);
	}
	
	@Test
	public void randomBooleanByProbabilityTest() throws Exception {
		double p = 0.66666;
		int numberOfTrials = 20000;
		double minProb = 0.95;
		double maxProb = 1.05;
		boolean isOk = false;
		int counter = 0;
		for (int i = 0; i < numberOfTrials; i++) {
			if (Utility.randomBooleanByProbability(p) ) counter++;
		}
		if (p * numberOfTrials * minProb < counter && counter < p * numberOfTrials * maxProb) {
			isOk = true;
		}
		assertTrue(isOk);
	}
}

アルゴリズムイントロダクション 練習問題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);
	}
}

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