Big Number Conversion

from __init__ import install_dependencies

await install_dependencies()

from inspect import getsource
from math import floor, log2

import numpy as np
from ipywidgets import interact

%reload_ext divewidgets

An int can be arbitrarily large because it is represented similarly to a string of digits. More precisely, as shown in the source code, an integer consists of a collection of fixed-length unsigned integers to store the digits, along with another unsigned integer to store the number of digits, sign and other flags.^[1] Integer operations such as subtraction often has to iterate through all the digits, as shown in the code.^[2]

Similarly in this notebook, we will use iterations to convert non-negative integers with arbitrary size.

Conversion to Decimal¶

Binary-to-Decimal¶

In a previous lab, we considered converting a byte string to decimal. What about converting a binary string of arbitrary length to decimal?

The simplest way is to use int constructor:

int("0" * 4 + "1" * 4, base=2)

But how is int constructor implemented?

In mathematics, we use the summation notation to write the above formula (2) concisely as

\sum_{i=0}^{k-1} 2^i \cdot b_i,

(3)

i.e., the sum of $2^i \cdot b_i$ for $i$ taking an integer value from 0 to $k-1$ .

This can be implemented using a for loop:

def binary_to_decimal_v1(binary_str):
    k = len(binary_str)
    decimal = 0  # initialization
    for i in range(k):  # iteration
        decimal += 2**i * (1 if binary_str[(k - 1) - i] == "1" else 0)
    return decimal


binary_to_decimal_v1("0" * 4 + "1" * 4)

Note that $b_i$ is given by binary_str[(k-1)-i] for different index i as shown below:

\begin{array}{c|c:c:c:c|} \texttt{binary\_str} & b_{k-1} & b_{k-2} & \dots & b_0\\ \text{indexing} & [0] & [1] & \dots & [k-1] \end{array}

(4)

The following is another way to write the for loop.

def binary_to_decimal_v2(binary_str):
    decimal = 0  # initialization
    for bit in binary_str:
        decimal = decimal * 2 + (1 if bit == "1" else 0)  # iteration
    return decimal


binary_to_decimal_v2("0" * 4 + "1" * 4)

The algorithm implements the same formula factorized as follows:

\begin{aligned} \sum_{i=0}^{k-1} 2^i \cdot b_{i} &= \left(\sum_{i=1}^{k-1} 2^i \cdot b_{i}\right) + b_0\\ &= \left(\sum_{i=1}^{k-1} 2^{i-1} \cdot b_{i}\right)\times 2 + b_0 \\ &= \left(\sum_{j=0}^{k-2} 2^{j} \cdot b_{j+1}\right)\times 2 + b_0 && \text{with $j=i-1$} \\ &= \underbrace{(\dots (\underbrace{(\underbrace{\overbrace{0}^{\text{initialization}\kern-2em}\times 2 + b_{k-1}}_{\text{first iteration} }) \times 2 + b_{k-2}}_{\text{second iteration} }) \dots )\times 2 + b_0}_{\text{last iteration} }.\end{aligned}

(5)

YOUR ANSWER HERE

def binary_to_decimal(binary_str):
    k = len(binary_str)
    decimal = 0
    # YOUR CODE HERE
    raise NotImplementedError
    return decimal

Source

# test validity
assert getsource(binary_to_decimal).find("for") < 0  # no for
assert getsource(binary_to_decimal).find("int") < 0  # no int
assert getsource(binary_to_decimal).find("while") > 0  # use while

# tests
def test_binary_to_decimal(decimal, binary_str):
    decimal_ = binary_to_decimal(binary_str)
    correct = isinstance(decimal_, int) and decimal_ == decimal
    if not correct:
        print(f"{binary_str} should give {decimal} not {decimal_}.")
    assert correct


test_binary_to_decimal(0, "0")
test_binary_to_decimal(255, "11111111")
test_binary_to_decimal(52154, "1100101110111010")
test_binary_to_decimal(3430, "110101100110")

# binary-to-decimal converter
from ipywidgets import interact

bits = ["0", "1"]


@interact(binary_str="1011")
def convert_byte_to_decimal(binary_str):
    for bit in binary_str:
        if bit not in bits:
            print("Not a binary string.")
            break
    else:
        print("decimal:", binary_to_decimal(binary_str))

Undecimal-to-Decimal¶

A base-11 number system is called an undecimal system. The digits range from 0 to 10 with 10 denoted as X:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, X.

(6)

For example, the International Standard Book Number (ISBN) uses an undecimal digit.

def undecimal_to_decimal(undecimal_str):
    # YOUR CODE HERE
    raise NotImplementedError
    return decimal

Source

# test validity
assert getsource(undecimal_to_decimal).find("int") < 0  # no int

# tests
def test_undecimal_to_decimal(decimal, undecimal_str):
    decimal_ = undecimal_to_decimal(undecimal_str)
    correct = isinstance(decimal_, int) and decimal_ == decimal
    if not correct:
        print(f"{undecimal_str} should give {decimal} not {decimal_}.")
    assert correct


test_undecimal_to_decimal(27558279079916281, "6662X0X584839464")
test_undecimal_to_decimal(23022771839270, "73769X2556695")
test_undecimal_to_decimal(161804347284488, "476129248X2067")

# undecimal-to-decimal calculator
undecimal_digits = [str(i) for i in range(10)] + ["X"]


@interact(undecimal_str="X")
def convert_undecimal_to_decimal(undecimal_str):
    for digit in undecimal_str:
        if digit not in undecimal_digits:
            print("Not an undecimal string.")
            break
    else:
        print("decimal:", undecimal_to_decimal(undecimal_str))

Conversion from Decimal¶

Consider the reverse process that converts a non-negative decimal number of arbitrary size to a string representation in another number system.

Decimal-to-Binary¶

The following code converts a decimal number to a binary string.

def decimal_to_binary(decimal):
    binary_str = str(decimal % 2)
    while decimal // 2:
        decimal //= 2
        binary_str = str(decimal % 2) + binary_str
    return binary_str

To understand the while loop, consider the same formula (5), where the braces indicate the value of decimal at different times:

\begin{aligned} \sum_{i=0}^{k-1} 2^i \cdot b_{i} &= \left(\sum_{i=0}^{k-2} 2^{i-2} \cdot b_{i-1}\right)\times 2 + b_0 \\ &= \underbrace{(\underbrace{ \dots (\underbrace{(0\times 2 + b_{k-1}) \times 2 + b_{k-2}}_{\text{right before the last iteration} } )\times 2 \dots + b_1}_{\text{right before the second iteration} })\times 2 + b_0}_{\text{right before the first iteration} }.\end{aligned}

(7)

$b_0$ is the remainder decimal % 2 right before the first iteration,
$b_1$ is the remainder decimal // 2 % 2 right before the second iteration, and
$b_{k-1}$ is the remainder decimal // 2 % 2 right before the last iteration.

We can also write a for loop instead of a while loop:

def decimal_to_binary(decimal):
    binary_str = ""
    num_bits = 1 + (decimal and floor(log2(decimal)))
    for i in range(num_bits):
        binary_str = str(decimal % 2) + binary_str
        decimal //= 2
    return binary_str

# decimal-to-binary calculator
@interact(decimal="11")
def convert_decimal_to_binary(decimal):
    if not decimal.isdigit():
        print("Not a non-negative integer.")
    else:
        print("binary:", decimal_to_binary(int(decimal)))

YOUR ANSWER HERE

Decimal-to-Undecimal¶

def decimal_to_undecimal(decimal):
    # YOUR CODE HERE
    raise NotImplementedError
    return undecimal_str

Source

# tests
def test_decimal_to_undecimal(undecimal, decimal):
    undecimal_ = decimal_to_undecimal(decimal)
    correct = isinstance(undecimal, str) and undecimal == undecimal_
    if not correct:
        print(
            f"{decimal} should be represented as the undecimal string {undecimal}, not {undecimal_}."
        )
    assert correct


test_decimal_to_undecimal("X", 10)
test_decimal_to_undecimal("0", 0)
test_decimal_to_undecimal("1752572309X478", 57983478668530)

# undecimal-to-decimal calculator
@interact(decimal="10")
def convert_decimal_to_undecimal(decimal):
    if not decimal.isdigit():
        print("Not a non-negative integer.")
    else:
        print("undecimal:", decimal_to_undecimal(int(decimal)))

Footnotes¶

The reality is that int still has a maximum. This is because the number of digits is stored using an unsigned integer of fixed size! (See the source code.)
↩
Note that the code implements the subtraction $a-b$ for non-negative integers $a$ and $b$ directly. It does not resort to addition $a+(-b)$ using the 2’s complement representation of $(-b)$ . In fact, the addition $a+(-b)$ is actually converted to $a-b$ as shown in here in the code.
↩