What is efficient number system conversion for big integers?

Правка en1, от ATSTNG, 2021-09-18 00:09:43

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.

Best aproach that I can think of is divide and conquer. We need are given big integer $$$x_b$$$ and another number system base $$$c$$$. We have to find $$$y$$$ such that $$$y_c = x_b$$$. Suppose $$$x_b$$$ has length $$$n$$$ and $$$y_c$$$ ahs length $$$m$$$.

Теги 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)