ATSTNG's blog

What is efficient number system conversion for big integers?
By ATSTNG, history, 3 years ago, In English

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?

  • Vote: I like it
  • +39
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ATSTNG (previous revision, new revision, compare).

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This is actually how it's implemented in the GNU Multi-Precision library (see the mpn_dc_get_str function which is called for long numbers). I'm not aware of any faster algorithms. I'm not exactly sure how fast is GMP's division.

However, CPython's divmod is quadratic, as well as its conversion routine. But as the base is about $$$2^{30}$$$ or $$$2^{60}$$$, both are still quite fast.

Both GMP and CPython store numbers in binary-like formats.

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thank you for useful links.

    For a long time I had intuitive feeling that I am missing something on this topic. But it seems I'm not.

    Also these design solutions for enterprise high-efficiency libs seem really questionable for me. It costs one extra if call on already heavy quadratic routine to make the most heavy of them way faster. It seems that some of libraries are tuned for "mid-size" big integers (like preferring Toom-Cook multiplication to FFT), but still is it really worth to leave them unimplemented?

    → Reply