generating sorted random numbers without exponentiation involved?

Question

I am looking for a math equation or algorithm which can generate uniform random numbers in ascending order in the range [0,1] without the help of division operator. i am keen in skipping the division operation because i am implementing it in hardware. Thank you.

How do you represent these numbers? Or is it open for discussion as well? — amit, Nov 09 '13 at 11:24
@amit It will be fixed point fractional numbers in my hardware. But this representation will not affect the answer that i am looking for. — user_rak, Nov 09 '13 at 12:22
How many numbers do you want? Can't you just generate N random numbers and sort them in ascending order? Or generate kth random number in the range (k-1)th random number and 1? — Abhishek Bansal, Nov 09 '13 at 13:12
@AbhishekBansal (Ans-1)Say, 500numbers in 1 iteration and I might have N iterations. Anyway how many number of random numbers i want to generate will not alter the answer i am looking for. (Ans-2)Well, generating random number and sorting them is the conventional method. The idea here is to skip the sorting process. (Ans-3)If you can provide an example for generating kth random number without using division operator, then that will be the answer to my question. — user_rak, Nov 09 '13 at 13:50
@A.I.Breveleri i meant uniform distribution, to make it simpler i can say generate random numbers in ascending order. — user_rak, Nov 09 '13 at 14:03
What operators are allowed? remainder, multiplication, addition, subtraction? — Abhishek Bansal, Nov 09 '13 at 14:18
@AbhishekBansal ya, it can be useful only when i have a constant denominator value throughout my iteration, so that i can precompute. isn't it ? — user_rak, Nov 09 '13 at 15:01
@rakesh Wait a second, you're willing to accept remainder but not division? — pjs, Nov 09 '13 at 19:36
@pjs yes, mod function can be accomplished without the use of division operator. — user_rak, Nov 10 '13 at 13:20
@rakesh I thought that was only so for powers of 2, not in general. — pjs, Nov 10 '13 at 17:26
@pjs lets say we need to do (X mod Y), if(Y*N)=X then rem := 0; elsif(Y*N > X) then rem := X - (Y*(N-1)); where N = 1,2...N.I guess this is generic. right ? — user_rak, Nov 10 '13 at 18:20
@rakesh it may be generic, but I'd argue it's analogous to doing division by successive subtraction. "Should I subtract one Y, two Y's, three Y's,...?" I thought you were implying there was a way to do generic modulo operations without division that was still O(1). — pjs, Nov 10 '13 at 18:20
@pjs oh ya,I agree with you. BTW thanks for the clear answer to this post. — user_rak, Nov 10 '13 at 18:30
@rakesh I just wanted to check my understanding on the modulus. And you're most welcome, your question was a fun one - I had to think for a while on this one. — pjs, Nov 10 '13 at 18:34

pjs · Accepted Answer · 2013-11-12T00:32:15.953

Generating the numbers in ascending (or descending) order means generating them sequentially but with the right distribution. That, in turn, means we need to know the distribution of the minimum of a set of size N, and then at each stage we need to use conditioning to determine the next value based on what we've already seen. Mathematically these are both straightforward except for the issue of avoiding division.

You can generate the minimum of N uniform(0,1)'s from a single uniform(0,1) random number U using the algorithm min = 1 - U**(1/N), where ** denotes exponentiation. In other words, the complement of the N^th root of a uniform has the same distribution as the minimum of N uniforms over the range [0,1], which can then be scaled to any other interval length you like.

The conditioning aspect basically says that the k values already generated will have eaten up some portion of the original interval, and that what we now want is the minimum of N-k values, scaled to the remaining range.

Combining the two pieces yields the following logic. Generate the smallest of the N uniforms, scale it by the remaining interval length (1 the first time), and make that result the last value we have generated. Then generate the smallest of N-1 uniforms, scale it by the remaining interval length, and add it to the last one to give you your next value. Lather, rinse, repeat, until you have done them all. The following Ruby implementation gives distributionally correct results, assuming you have read in or specified N prior to this:

last_u = 0.0
N.downto(1) do |i|
  p last_u += (1.0 - last_u) * (1.0 - (rand ** (1.0/i)))
end

but we have that pesky i^th root which uses division. However, if we know N ahead of time, we can pre-calculate the inverses of the integers from 1 to N offline and table them.

last_u = 0.0
N.downto(1) do |i|
  p last_u += (1.0 - last_u) * (1.0 - (rand ** inverse[i]))
end

I don't know of any way get the correct distributional behavior sequentially without using exponentiation. If that's a show-stopper, you're going to have to give up on either the sequential nature of the process or the uniformity requirement.

score 2 · Answer 2 · answered Nov 09 '13 at 20:41

You can try so-called "stratified sampling", which means you divide the range into bins and then sample randomly from bins. A sample thus generated is more uniform (less clumping) than a sample generated from the entire interval. For this reason, stratified sampling reduces the variance of Monte Carlo estimates (I don't suppose that's important to you, but that's why the method was invented, as a reduction of variance method).

It is an interesting problem to generate numbers in order, but my guess is that to get a uniform distribution over the entire interval, you will have to apply some formulas which require more computation. If you want to minimize computation time, I suspect you cannot do better than generating a sample and then sorting it.

generating sorted random numbers without exponentiation involved?

2 Answers2

Linked