Julia: digits() is much slower than base() for large numbers

[wirelyre]

a = factorial(BigInt(15_000));

@time digits(a);
    # 0.937261 seconds (505.16 k allocations: 636.025 MiB, 5.58% gc time)
@time reverse(Vector{Char}(base(10, a))) .- '0';
    # 0.004019 seconds (39 allocations: 980.672 KiB)

char_to_digit(c) = if c<='9' c-'0' else c-'W' end
@time digits(a, 30);
    # 0.651652 seconds (341.99 k allocations: 430.588 MiB, 6.39% gc time)
@time char_to_digit.(reverse(Vector{Char}(base(30, a))));
    # 0.004130 seconds (38 allocations: 679.469 KiB)

It might be possible to beat a round-trip through String. (It might not, because base calls out to GMP, which has direct access to bigint internals and a high compiler optimization level.)

GMP uses a recursive divide-and-conquer algorithm by computing square powers of base, then dividing by the largest power first. Having split the input into two, each half is reduced using the next-largest power of base. This process is repeated until the input is small, at which point the naïve divide/modulus algorithm takes over.

GMP also has specialization on base-10 conversions.

julia> versioninfo()
Julia Version 0.6.3
Commit d55cadc350 (2018-05-28 20:20 UTC)
Platform Info:
  OS: macOS (x86_64-apple-darwin14.5.0)
  CPU: Intel(R) Core(TM) i5-3210M CPU @ 2.50GHz
  WORD_SIZE: 64
  BLAS: libopenblas (USE64BITINT DYNAMIC_ARCH NO_AFFINITY Sandybridge)
  LAPACK: libopenblas64_
  LIBM: libopenlibm
  LLVM: libLLVM-3.9.1 (ORCJIT, ivybridge)

[StefanKarpinski]

Sounds like a great relatively standalone project that someone could tackle. @wirelyre, you seem fairly knowledgable—would you be interested in tackling it?

[mbauman]

What would your use-case here be? Are you using all the digits? Or just accessing a few of them? Here'd be another option if it's the latter:

struct Digits{T<:Integer} <: AbstractVector{Int}
    d::T
end
Base.size(d::Digits) = (ndigits(d.d),)
Base.getindex(d::Digits{T}, i::Int) where {T} = rem(div(d.d, T(10)^(i-1)), 10)

Of course, more optimizations can be had here, it needs bounds checks, etc, etc.

[wirelyre]

@mbauman That's very clean and neat. Unfortunately I need to access all the digits. I came across the time difference when migrating to digits made one of my Project Euler solutions about 50% slower.

Not unusably slow, mind. Just thought I'd file an issue since there's an asymptotically better algorithm.

[StefanKarpinski]

Closed by https://github.com/JuliaLang/julia/pull/37075.