Contents

Big Number Conversion

from math import floor, log2

Conversion to Decimal

In this notebook, we will use iterations to convert numbers with arbitrary size.

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?

Definition 3 (Binary numbers)

Given a binary string of an arbitrarily length \(k\),

\[ b_{k-1}\circ \dots \circ b_1\circ b_0, \]

the decimal number is given by the formula

(6)\[ 2^0 \cdot b_0 + 2^1 \cdot b_1 + \dots + 2^{k-1} \cdot b_{k-1}. \]

In mathematics, we use the summation notation to write the above formula (6):

(7)\[ \sum_{i=0}^{k-1} 2^i \cdot b_{i}. \]

In a program, the formula can be implemented as a for loop:

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

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

\[\begin{split} \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} \end{split}\]

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 + int(bit)  # iteration
    return decimal

The algorithm implements the same formula factorized as follows:

(8)\[\begin{split} \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} \end{split}\]

Exercise Write your own converter binary_to_decimal below. Make it as efficient as possible.

def binary_to_decimal(binary_str):
    # YOUR CODE HERE
    raise NotImplementedError()
    return decimal

Hint

You can choose one of the two implementations above but take the time to type in the code instead of copy-and-paste.

# tests
import numpy as np


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. \]

The International Standard Book Number (ISBN) uses an undecimal digit.

Exercise In the following code, assign to decimal the integer represented by an undecimal string of arbitrary length.

Hint

Write a conditional to

  1. check if a digit is (capital) 'X', and if so,

  2. convert the digit to the integer value 10.

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

# 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
from ipywidgets import interact

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 (8), where the braces indicate the value of decimal at different times:

\[\begin{split} \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} \end{split}\]

  • \(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)))

Exercise Explain what the expression 1 + (decimal and floor(log2(decimal))) calculates. In particular, explain the purpose of the logical and operation in the expression?

YOUR ANSWER HERE

Decimal-to-Undecimal

Exercise Assign to undecimal_str the undecimal string that represents a non-negative integer decimal of any size.

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

# 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
from ipywidgets import interact


@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)))

Timer (Optional)

Benchmark

Recall the two versions of binary-to-decimal converters defined at the beginning of the lab:

binary_to_decimal_v1??

binary_to_decimal_v2??

How to compare their speed?

We can use the time module.

import time

time.localtime()

time.struct_time(tm_year=2021, tm_mon=11, tm_mday=19, tm_hour=12, tm_min=9, tm_sec=26, tm_wday=4, tm_yday=323, tm_isdst=0)

We can also format the current local time to a more easily readable string:

time.strftime("%a, %d %b %Y %H:%M:%S", time.localtime())

'Fri, 19 Nov 2021 12:09:26'

How to implement a timer?

The idea is to record the start time and end time, and then compute their difference:

start = time.localtime()
...  # code to be timed
end = time.localtime()
end - start

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-22-d4f1c4d1fdf3> in <module>
      2  # code to be timed
      3 end = time.localtime()
----> 4 end - start

TypeError: unsupported operand type(s) for -: 'time.struct_time' and 'time.struct_time'

Unfortunately, the above code fails because - is note defined for the time object time.struct_time.

How to compute the difference in time?

Instead of implementing - for time.struct_time, a simpler solution is to use time.time(), which returns the current time as a floating point number.

time.time()

1637294966.3099682

This is the number of seconds elapsed after certain epoch (a point in time). For linux/unix, the time module uses the unix epoch, which is January 1, 1970, 00:00:00 (UTC):

time.strftime(
    "%a, %d %b %Y %H:%M:%S +0000 ", time.gmtime(0)
)  # Convert zero seconds to UTC time

'Thu, 01 Jan 1970 00:00:00 +0000 '

The following code implements the timer:

def time_b2d(binary_to_decimal, binary_str):
    """Return the time in secs for running binary_to_decimal on binary_str."""
    start = time.time()
    decimal = binary_to_decimal(binary_str)
    end = time.time()
    return end - start

In the following, t1 and t2 keeps the time it takes for binary_to_decimal_v1 and binary_to_decimal_v2 to run on the same input byte binary_str.

if input("Ready? [Y/n]").lower() != "n":
    binary_str = "1" * 8
    t1 = time_b2d(binary_to_decimal_v1, binary_str)
    t2 = time_b2d(binary_to_decimal_v2, binary_str)
    print(f"t1 = {t1:.3g}s\nt2 = {t2:.3g}s\nt1/t2 = {t1/t2:.3g}")

Exercise (Optional) Observe the difference in speeds for longer binary_str, e.g., with binary_str = '1' * 100000. Is the ratio t1/t2 of the running times roughly the same regardless of the input length?

There can be variations in the running time due to many factors. To measure the typical performance, we should run the code multiple times and report the total or average running time. The following is the modified timer:

def time_b2d(binary_to_decimal, binary_str, n_iters):
    """Return the time in secs for running binary_to_decimal on binary_str."""
    start = time.time()
    for i in range(n_iters):
        decimal = binary_to_decimal(binary_str)
    end = time.time()
    return end - start

To compare:

if input("Ready? [Y/n]").lower() != "n":
    binary_str = "1" * 8
    n_iters = 100
    t1 = time_b2d(binary_to_decimal_v1, binary_str, n_iters)
    t2 = time_b2d(binary_to_decimal_v2, binary_str, n_iters)
    print(f"t1 = {t1:.3g}s\nt2 = {t2:.3g}s\nt1/t2 = {t1/t2:.3g}")

Exercise (Optional) Increase the number of iterations until you get can a variation in t1/t2 less than 0.2 in two consecutive runs most of the time.

Indeed, IPython has a built-in magic to time an execution:

%%timeit
binary_to_decimal_v1("1" * 8)

2.52 µs ± 15.2 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

%%timeit
binary_to_decimal_v2("1" * 8)

966 ns ± 4.76 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

Note that the numbers of loops are decided automatically.

Alarm clock

How to set an alarm in python to go off after certain time?

We can write a loop like the following:

duration = int(input("How many seconds to wait?"))
start = time.time()
while time.time() - start <= duration:
    pass
print("Time's up!")

A simpler way is to use time.sleep:

time.sleep(int(input("How many seconds to wait?")))
time.sleep?

How to play a sound when time is up?

To play a beep sound in jupyter notebook, we can use the jupyter_beeper module:

import jupyter_beeper

beeper = jupyter_beeper.Beeper()


def alarm(seconds):
    time.sleep(seconds)
    beeper.beep()

To set the alarm to 3 seconds after now:

alarm(int(input("How many seconds to wait?")))

Notice that the alarm is blocking the execution. To avoid that, we need to run it as a thread:

import threading


def background_alarm(seconds):
    threading.Thread(target=alarm, args=(seconds,)).start()

To set two alarms simultaneously:

background_alarm(int(input("How many seconds to wait?")))
background_alarm(int(input("How many seconds to wait?")))

Exercise (Optional) Modify alarm to give 3 consecutive beeps in 1 second interval after a duration (in seconds) specified by the user.