janmr blog

Multiple-Precision Number Representation

Let us consider a common way to represent non-negative integers. An integer u0u \geq 0 will be represented in radix b2b \geq 2 using the notation

u=(un1u1u0)b=k=0n1ukbk,0ukb1.u = (u_{n-1} \ldots u_1 u_0)_b = \sum_{k=0}^{n-1} u_k b^k, \quad 0 \leq u_k \leq b-1.

We will call uu an nn-digit number and u0,u1,u_0, u_1, \ldots its digits. Zero will be represented with no digits, 0=()b0 = ()_b. Observe that

u((b1)(b1)(b1))b=k=0n1(b1)bk=bn1u \leq ((b-1) \ldots (b-1) (b-1))_b = \sum_{k=0}^{n-1} (b-1) b^k = b^n - 1

for any n0n \geq 0.

Unless stated otherwise we will always have that the most-significant digit is non-zero, that is, un10u_{n-1} \neq 0 for n1n \geq 1. This assumption has some important consequences. First, that

u(100)b=bn1u \geq (1 0 \ldots 0)_b = b^{n-1}

for any n1n \geq 1. Secondly, that each non-negative integer has a unique representation, that is, to each number u0u \geq 0 and radix b2b \geq 2 corresponds exactly one n0n \geq 0 and digits u0,u1,,un1u_0, u_1, \ldots, u_{n-1} such that u=(un1u1u0)bu = (u_{n-1} \ldots u_1 u_0)_b. Thirdly, that

bn1u<bnn1logb(u)<nlogb(u)=n1.b^{n-1} \leq u < b^n \quad \Leftrightarrow \quad n-1 \leq \log_b(u) < n \quad \Leftrightarrow \quad \lfloor \log_b(u) \rfloor = n-1.

This last relation can be quite useful since the number of needed digits can be found, given uu and bb. For instance, the fact that log2(1317803400)+1=31\lfloor \log_2(1317803400) \rfloor + 1 = 31 means that the number 1317803400 can be represented using 31 binary digits.