Changing numerical base and other math tools/functions

General Usage
,
1

Is there any packages to fast change numerical base, like to binary or octal, without using a custom function?

I have some algorithms that I coded myself, but definitely there is faster algorithms to do so. Any help?

I need a function to change a number’s base, do arithmetics with the number and if possible to analyze this number, like a function thats returns the 3° digit of the number etc.

Thanks!

2

Base is a property of how a number is displayed, not of of the number itself or of how you do arithmetic. You can display the digits of a number in any base you want using the digits function;

julia> digits(3234, base=3)
8-element Array{Int64,1}:
 0
 1
 2
 2
 0
 1
 1
 1

and you can parse a number from an arbitrary base using parse:

julia> parse(Int, "11102210", base=3)
3234
8 Likes
3

You can use the digits function for this, but it’s not optimal, because it calculates all the digits and puts them in a vector. Here’s a faster version:

function getdigit(n::Integer, digit::Integer; base=10)
    digit < 1 && error("Digit must be positive number.")
    m = (ndigits(n; base=base) - digit + 1)
    d = 0
    for i in 1:m
        n, d = divrem(n, base)
    end
    return d
end

Benchmark:

julia> N = 42570554
42570554

julia> digit = 3;

julia> @btime digits($N; base=10)[end-$digit+1]
  105.229 ns (1 allocation: 144 bytes)
5

julia> @btime getdigit($N, $digit; base=10)
  37.353 ns (0 allocations: 0 bytes)
5

Later digits is cheaper to calculate:

julia> digit = 14;

julia> base = 3;

julia> @btime digits($N; base=$base)[end-$digit+1]
  168.771 ns (1 allocation: 208 bytes)
0

julia> @btime getdigit($N, $digit; base=$base)
  33.449 ns (0 allocations: 0 bytes)
0

BTW: you can go even faster when base is a power of 2. I didn’t include that, but you can find out how by looking at Base.digits!

4

You can do better than this. Instead of repeated divrem, you can use one log, mod, and div to get arbitrary digits in O(1) (technically it’s something more complicated for BigInt, but it still should be exponentialy faster.)

5

I don’t immediately see how to use log, but here’s an O(1) version that is pretty fast:

function getdigit_(n::Integer, digit::Integer; base=10)
    digit < 1 && error("Digit must be positive number.")
    m = (ndigits(n; base=base) - digit + 1)
    d = divrem(n, base^(m-1))[1]
    return divrem(d, base)[2]
end

Edit: The above will fail in some cases, we must keep track of the integer type. Here’s better version, but it is still virtually untested, caveat emptor!

Also, note that it is O(1) in the selection of the digit, but not O(1) in the size of the number n.

function getdigit_(n::T, digit::Integer; base=10) where {T<:Integer}
    digit < 1 && error("Digit must be positive number.")
    m = (ndigits(n; base=base) - digit + 1)
    d = divrem(n, T(base)^(m-1))[1]
    return divrem(d, base)[2]
end

Notice for example the sign:

julia> getdigit_(-24234, 2)
-4
2 Likes
6

Oh good point. You only need log if you want the nth most significant digit.

7

So, actually, when the base is a power of 2, it is much faster to use digits (Edit: this happens for number types other than Int, so there is some weakness in how those are handled). So this fixes that, and is faster than digits also for power-of-2:


function getdigit(n::T, digit::Integer; base=10) where {T<:Integer}
    digit < 1 && error("Digit must be positive number.")
    if ispow2(base)
        return _getdigit_pow2(n, digit, base)
    end
    m = (ndigits(n; base=base) - digit + 1)
    d = divrem(n, T(base)^(m-1))[1]
    return divrem(d, base)[2]
end

function _getdigit_pow2(n::T, digit::Integer, base) where {T<:Integer}
    base = Int(base)
    m = (ndigits(n; base=base) - digit + 1)
    k = trailing_zeros(base)
    c = base - 1
    d = (abs(n) >> (k * (m - 1))) & c
    return copysign(d, n)
end

(Credit: the code in _getdigit_pow2 is directly based on code from Base.digits!)

Benchmark:

julia> N = rand(Int128)
103762535102034279391635081693314883948

julia> @btime digits($N; base=16)[end-6]
  189.805 ns (1 allocation: 336 bytes)
15

julia> @btime getdigit($N, 7; base=16)
  20.929 ns (0 allocations: 0 bytes)
15

Again, this is very untested, and probably has some issues.

1 Like