Algorithm Implementation and Performance Analysis for Generating Unique Random Numbers from 1 to 100 in JavaScript

Introduction

Generating unique random numbers is a common yet critical requirement in JavaScript programming, particularly in scenarios such as game development, data sampling, and test case generation. Based on highly-rated answers from Stack Overflow, this paper provides an in-depth analysis of two primary implementation methods, with extended discussions grounded in computer science principles.

Iterative Algorithm Based on Array Checking

The first method employs a straightforward iterative strategy, generating random numbers in a loop and checking for uniqueness. Below is the core algorithm implementation:

var arr = [];
while(arr.length < 8){
    var r = Math.floor(Math.random() * 100) + 1;
    if(arr.indexOf(r) === -1) arr.push(r);
}
console.log(arr);

Algorithm Complexity Analysis

This algorithm has a time complexity of O(n²), where n is the number of random numbers to generate. Each new random number requires traversing the existing array to check for duplicates, leading to significant performance degradation as n approaches 100. The space complexity is O(n), as only the result array needs to be stored.

Implementation of the Fisher-Yates Shuffle Algorithm

The second method is based on the classic Fisher-Yates shuffle algorithm, which first generates a complete sequence of numbers, then randomly sorts them and takes the first n elements:

function generateUniqueRandom(count, max) {
    var arr = Array.from({length: max}, (_, i) => i + 1);
    for (let i = arr.length - 1; i > 0; i--) {
        const j = Math.floor(Math.random() * (i + 1));
        [arr[i], arr[j]] = [arr[j], arr[i]];
    }
    return arr.slice(0, count);
}

console.log(generateUniqueRandom(8, 100));

Performance Comparison and Applicable Scenarios

When the number of random numbers needed is small (e.g., n < 20), the iterative algorithm is more concise and efficient. However, for larger n, the shuffle algorithm's time complexity of O(n) is significantly better than the iterative algorithm's O(n²). According to data from the reference article, selecting 8 unique numbers from 1 to 100 offers approximately C(100,8) ≈ 1.86×10¹¹ possible combinations, ensuring sufficient randomness.

Mathematical Principles Extension

The core of random number generation relies on the assumption of uniform distribution. JavaScript's Math.random() function is based on a pseudo-random number generator and, while it does not provide true randomness, is sufficient for most application scenarios. For cryptographically secure scenarios, it is recommended to use the crypto.getRandomValues() method from the Web Crypto API.

Practical Application Optimization

For production environments, it is advisable to add boundary checks and optimizations for handling duplicate generations. For instance, when the number of random numbers needed is close to the total available, a reverse strategy can be employed by removing selected elements from the complete set to avoid the risk of infinite loops.

Conclusion

Both algorithms have their respective advantages and disadvantages. Developers should choose the appropriate method based on specific requirements. For small-scale data, the iterative algorithm is simple and intuitive; for large-scale or performance-sensitive scenarios, the shuffle algorithm is more reliable. Understanding the mathematical principles and performance characteristics behind the algorithms aids in making better technical decisions in practical projects.