/*
 * Copyright (C) 2015 Imran Mammadli
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package math.random.uniform;

import java.util.Random;

// Implement a random number generator that generates a random integer i between
// A and B, inclusive, given a random number generator that produces either zero 
// or one with equal probability? All generated values should be equally likely.
public class Solution1
{
	/**
	 * 
	 * @time <i>O(log<sub>2</sub>(b-a))</i>
	 * @space <i>O(1)</i>
	 **/
	public static long generateRandom(long a, long b) throws IllegalArgumentException
	{
		if (a < 0 || b < 0)
		{
			throw new IllegalArgumentException("Both arguments must be positive.");
		}
		
		long result;
		long range = Math.abs(a - b);
		Random rand = new Random();
		
		do
		{
			result = 0;
			
			for (long i = range; i > 0; i >>= 1)
			{
				int digit = rand.nextInt(2);
				result = (result << 1) | digit;
			}
		}
		while (result >= range);
		
		return result + a;
	}
}