What is efficient number system conversion for big integers?

Правка en5, от ATSTNG, 2021-09-18 01:20:22

Number system conversion algorithm is well-known and taught in almost every basic programming course. To get $$$y_b = x_{10}$$$ (number $$$y$$$ written in base $$$b$$$ equal to number $$$x$$$ base $$$10$$$) we have to iteratively chop the lowest digit in base $$$b$$$ from number $$$x$$$ using division and remainder operators:

def naive_conversion(x, base):
    y = ""
    while x > 0:
        y = str(x % base) + y
        x //= base

    return y

This works in $$$\mathcal{O}(\log x)$$$ for all $$$x$$$ that fit into machine word $$$(\log x < w)$$$. However this becomes inacceptably slow when we consider numbers of length $$$n$$$ that is large enough and we cannot use $$$\mathcal{O}(1)$$$ division. Let's define $$$n$$$ as length of converted number $$$x$$$ in some number system $$$(w \ll \log x = n)$$$. Still, base of number systems $$$b$$$ and all digits in it can be stored in usual integer. So we can implement conversion above in $$$\mathcal{O}(n^2)$$$ with some efficient implementation of big-number-by-small-number division.

This operation is commonly required when you are trying to print big integers in base $$$10$$$ that are stored by big integer library in binary notation. To overcome this some competitive programming libraries use base $$$10^9$$$ to print numbers in base $$$10$$$ digit-by-digit without complicated conversion. But this is just a trick for common number presentation. But how to generally approach this problem and be able to quickly convert big integers to any number system?

We are given big integer $$$x_b$$$ and another number system base $$$c$$$. We have to find $$$y$$$ such that $$$y_c = x_b$$$. $$$f(x_b, c) = y_c$$$. Suppose $$$x_b$$$ has length $$$n$$$ and $$$y_c$$$ will have length $$$m$$$.

Best aproach that I can think of is divide and conquer. Main problem with abritrary bases is that many digits in $$$x$$$ can affect many digits in $$$y$$$. To overcome this we can choose $$$p \approx \frac{m}{2}$$$ and represent $$$x_b = L_b \cdot c^p + R_b$$$, where $$$R_b < c^p$$$. In such form we can see that $$$L$$$ part can only affect higher half of digits of $$$y$$$ and $$$R$$$ part can only affect lower half of digits. Now we can safely split our number into two, solve problem recursively obtaining $$$f(L_b, c) = L'_c$$$ and $$$f(R_b, c) = R'_c$$$ and finally concatenate parts $$$y_c = L'_c \cdot c^p + R'_c$$$.

To split $$$x_b$$$ into $$$L_b, R_b$$$ we can use division and remainder. Assuming that big integer divmod can be implemented in $$$\mathcal{O}(n \log n)$$$ whole recursive calculation of $$$f(x_b, c)$$$ can be done in $$$\mathcal{O}(n \log^2 n)$$$.

def fastbase(x, b, order=-1):
    if order == -1:
        order = 1
        while b**(order+1) <= x:
            order *= 2

    if order == 0:
        return str(x)

    sep = b ** order

    hi, lo = divmod(x, sep)

    return fastbase(hi, b, order//2) + fastbase(lo, b, order//2)

In this implementation $$$m$$$ is naively estimated as lowest possible power of two, but then extra leading zeroes must be stripped.

We made some benchmarking in Kotlin and in Python. This algorithm appears to be somewhat competitive with built-in algorithms in Kotlin, however in Python3 this works even faster.

Benchmark code in Python3
Local testing results

Blazing fast conversions to binary formats (and powers of binary) show that numbers are stored in binary.

Are there any well-knows algorithms? What algorithms are used in standard libraries? Are there any better solutions?

Теги big integers

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en5 Английский ATSTNG 2021-09-18 01:20:22 0 (published)
en4 Английский ATSTNG 2021-09-18 01:19:22 7 Tiny change: 'ber system.\n\nWe need are given' -> 'ber system?\n\nWe are given' (saved to drafts)
en3 Английский ATSTNG 2021-09-18 01:16:52 0 (published)
en2 Английский ATSTNG 2021-09-18 01:16:00 3799 Tiny change: 'ulate $c^p}$ and calc' -> 'ulate $c^p$ and calc'
en1 Английский ATSTNG 2021-09-18 00:09:43 1759 Initial revision (saved to drafts)