4
\$\begingroup\$

Von Neumann extraction is a technique to remove bias from a source of entropy. You extract an unbiased array of bits from a biased one by comparing pairs of consecutive bits in the array and returning the first one when they are different, or nothing when they are the same. The extracted array will be smaller than the source array, but will be more balanced in terms of overall 0s and 1s.

To accomplish this in JavaScript I ended up writing two extraction methods: one for extracting a bit (given an array and an index) and one for extracting an entire array (given an array). The code appears to work as desired, but I'd love to hear any insights or suggestions related to best practices, naming conventions, performance concerns, or problematic edge cases.

Here's my bit-extraction method:

function extractBitFromArray(arr, i) {
    var a = arr[i];
    var b = arr[i + 1];
    return (a ^ b ? a : null);
}

And here's my array-extraction method:

function extractUnbiasedArray(randomArray){
    var extractedArray = [];
    for (var i = 0; i + 1 < randomArray.length; i += 2) {
        var extracted = extractBitFromArray(randomArray, i);
        if (extracted !== null) {
            extractedArray.push(+extracted);
        }
    }
    return extractedArray;
}

For the sake of completion, here are some analogous dummy functions used to generate a biased but still pseudorandom array:

function getBiasedArray(length){
    var randomArray = [];
    for (var i = 0; i < length; i++) {
        randomArray.push(getBiasedBit());
    }
    return randomArray;
}
function getBiasedBit() {
    return +(Math.pow(Math.random(), Math.random()) > Math.random());
}

Example of how the functions would be used:

var randomArray = getBiasedArray(5000);
var extractedArray = extractedUnbiasedArray(randomArray);

I have a fiddle demonstrating how the technique works, but it's polluted with logging and metrics, and doesn't have all the logic encapsulated into functions; I'd rather any critiques be directed to the above code rather than the code in the fiddle: http://jsfiddle.net/thriggle/Ljojyn6p/

\$\endgroup\$
2
\$\begingroup\$

Your code looks quite clean and I have just a few observations, mainly regarding readability.

First it lacks comments, that is especially important in your case because the matter is not that common. In your question you separately gave all needed information to understand what and how it is processed, but these explanations should be included in the code, even if in a less detailed fashion.

Naming conventions respect standards but I'd suggest a different choice about what you named "bit". Technically speaking you're not managing bits but numbers, even if they only take values of 0 or 1: so at a first view it's a bit (!) confusing and you'd better using something like "digit" or "val", or somewhat else not too much related to a (here falsy) javascript type.

Yet about this fact that data are not really bits I was surprised you're using a bitwise operator in return (a ^ b ? a : null);. Maybe I'm missing some subtility but for what I can understand this XOR can be simply expressed as return (a != b ? a : null);.
Though I'm not pretty sure, it might be less detrimental to performance.

The only real fault against best practices is in your for (var i = 0; i + 1 < randomArray.length; i += 2): this way randomArray.length is evaluated for each step. The right way is for (var i = 0, l = randomArray.length; i + 1 < l; i += 2), so evaluating randomArray.length only once.

Last observation, you may save some variables and reduce the code length each time a variable is used only once, like here:

var a = arr[i];
var b = arr[i + 1];
return (a ^ b ? a : null);

that can be written:

var a = arr[i];
return (a ^ arr[i + 1] ? a : null);

(note that I only dropped the b var: also dropping a would cause arr[i] to be evaluated twice)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.