An algorithm that returns a number between 0-1, each successive number will be divided by two

montjet 0
Viewed 28

I am looking at this code challenge:

Write a function that takes one integer argument (index), which will return a number in the range 0-1. The returned number can be derived by successively splitting ranges into smaller ranges, each time selecting the largest available range, giving precedence to the right most range when tied. The number of splits corresponds to the argument. The offset where the last split occurred should be returned.

Here follows a visualisation of how the expected results are produced for the first few values for the index argument:

enter image description here

If possible, the function should be O(1).

I can understand the logic that is performed here, but I can't see how this could possibly be done in O(1). How could that be achieved?

math algorithm
1 Answers

You could look at how these fractions are expressed as a division of two integers. The sequence then is:

1, 1/2, 3/4, 1/4, 7/8, 5/8, 3/8, 1/8, 15/16, 13/16, 11/16, 9/16, 7/16...

There is a pattern here that looks like this:

Denominator: = 2⌈log2(1 + )⌉ or in other words, the least power of 2 that is greater than the given index

Numerator: = 1 + 2[ ⊻ (−1)] where ⊻ is the XOR operator. In other words, flip all bits of the index, and append a 1-bit at the right.

Here is a JavaScript snippet that produces the results for the first 16 values:

for (let i = 0; i < 16; i++) {
    let d = 1 << Math.ceil(Math.log2(i + 1));
    let n = 1 + 2 * (i ^ (d - 1));
    console.log(`${i}: ${n}/${d} = ${n/d}`);
}

trincot0
Related