zeen · December 4, 2010 02:52
diff --git a/gistfile1.txt b/gistfile1.txt
 I have DNS records with weights. Need to select/sort randomly by weight. Problem: Distribution of the random variable I have is undefined.

 Current plan:
 Get random number X = N uniformly random bits from rand(0,1)<0.5 (von Neumann's fair coin from unfair).
 2^N >= sum(weights). X <= sum(weights). X would be uniform over sum(weights). Right?
 Select kth number from list such that sum(Weight1...Weightk)>X.

 1. Is this correct?
 2. Is there a better way (I'd like to minimize rand() calls and processing in general)?
 3. von Neumann's fair coin method works with two coin tosses for every fair toss. Can I reuse the last toss of the old pair in the next? That would cut rand() down by half.
	I have DNS records with weights. Need to select/sort randomly by weight. Problem: Distribution of the random variable I have is undefined.

	Current plan:
	Get random number X = N uniformly random bits from rand(0,1)<0.5 (von Neumann's fair coin from unfair).
	2^N >= sum(weights). X <= sum(weights). X would be uniform over sum(weights). Right?
	Select kth number from list such that sum(Weight1...Weightk)>X.

	1. Is this correct?
	2. Is there a better way (I'd like to minimize rand() calls and processing in general)?
	3. von Neumann's fair coin method works with two coin tosses for every fair toss. Can I reuse the last toss of the old pair in the next? That would cut rand() down by half.