number_to_digits_subquadratic_algorithm_2.sf

#!/usr/bin/ruby

# Subquadratic algorithm for converting a given integer into a list of digits in a given base.

# Algorithm presented in the book:
#
#   Modern Computer Arithmetic
#           - by Richard P. Brent and Paul Zimmermann
#

func FastIntegerOutput(A, B) {

    # Find k such that B^(2k - 2) <= A < B^(2k)
    var k = (A.ilog(B)>>1 + 1)

    func (A,k) {

        if (A < B) {
            return [A]
        }

        if (B**(2*(k-1)) > A) {
            --k
        }

        #assert(B**(2*k - 2) <= A, [B,k, "#{B**(2*k - 2)} <= #{A}"])
        #assert(A < B**(2*k), [B,k, "#{A} < #{B**(2*k)}"])

        var (Q,R) = A.divmod(B**k)

        var t = (k+1)>>1
        var r = __FUNC__(R, t)
        var l = __FUNC__(Q, t)

        [l..., (k - r.len).of(0)..., r...]
    }(A,k)
}

say FastIntegerOutput(5040, 10)     #=> [5, 0, 4, 0]
say FastIntegerOutput(5040, 11)     #=> [3, 8, 7, 2]
say FastIntegerOutput(5040, 12)     #=> [2, 11, 0, 0]
say FastIntegerOutput(5040, 13)     #=> [2, 3, 10, 9]

for B in (2..100) {     # run some tests
    var N = 1e20.irand

    var a = N.digits(B)
    var b = FastIntegerOutput(N, B)

    assert_eq(a.flip, b)
}