Repeating strings efficiently

Recently, Michael Ficarra pointed me to an efficient algorithm for repeating a string several times. In this blog post, I explain how it works.

The algorithm makes use of the fact that natural numbers (non-negative integers) can be represented as sums of powers of two.

Natural numbers as sums of powers of two

You can express any natural number as a sum of powers of two. In fact, that’s what a number in binary notation is. The value of a sequence of n binary digits d_i

d_n-1d_n-2 ... d₀

is the sum

∑_{0 ≤ i < n} d_i × 2ⁱ = d₀ × 1 + d₁ × 2 + d₂ × 4 + ...

Each digit d_i is either one or zero. Therefore, each addend is either a power of two or it is zero.

The algorithm

Roughly, the algorithm iterates over the digits starting with d₀. After each iteration, it doubles str, the string to repeat. If the current digit is one then the current value of str is added to the result. In other words, if the digit d_i is one, 2ⁱ times str is added to the result. The algorithm, implemented in JavaScript and slightly edited, looks as follows.

    function stringRepeat(str, num) {
        num = Number(num);

        var result = '';
        while (true) {
            if (num & 1) { // (1)
                result += str;
            }
            num >>>= 1; // (2)
            if (num <= 0) break;
            str += str;
        }

        return result;
    }

In line 1, the bitwise And operator (&) [1] is used to extract the value of the digit at the current position. In line 2, the bitshift operator (>>>) [2] is used to shift the next digit to the least significant (rightmost) position.

Where a naive algorithm takes num steps to produce a result, this algorithm takes log₂(num) steps. As an aside, concatenating strings via the plus operator (+) has become fast on modern JavaScript engines [3].

ECMAScript 6’s String.prototype.repeat()

ECMAScript 6 will have a string method String.prototype.repeat() that produces the same results as the function stringRepeat. Mathias Bynens has written a spec-compliant polyfill that uses an algorithm similar to stringRepeat’s.

References

1. Binary bitwise operators in JavaScript
2. Integers and shift operators in JavaScript
3. String concatenation in JavaScript