Numeric Algorithms

Number Representation

Question: How many symbols do we need to represent any number? There are infinitely many numbers, but we cannot have infinitely many symbols. Thus, we need a finite number of symbols that allows us to represent every conceivable number. For most of the world, that finite number is ten:

Number systems that use ten symbols to represent all numbers are called decimal number systems, or base-10 systems. In the Western decimal number system, ten symbols (called the Hindu-Arabic numerals) are used to represent every conceivable number. The number of unique symbols used in a numbering system to represent a number in that system is called the base or radix of the numbering system. For example, with the decimal system, the radix is ${10.}$ For the ancient Mayans, the radix was ${20}$ (called a vigesimal system). For the Babylonians, the radix was ${60}$ (called a base-60 system).

To understand how the base works, we'll consider the decimal system. First, we have enough symbols to represent the numbers zero through nine:

The symbols above, however, hide a critical fact: They all have an infinite amount of "slots" or "places", immediately to the left, occupied by a zero:

When we reach the number nine, we've run out of unique symbols. So to represent the number ten, we go to the slot on the left (occupied by a zero), and increment it by ${1:}$

Once we get to nineteen, we increment the slot again:

Because there are ten symbols, and for each of these ten we can assign one of the ten symbols immediately to its left, we have ${10 \times 10 = 10^2 = 100}$ unique symbols. This allows us to represent numbers from zero (${0}$) to ninety-nine (${99}$).

Once we reach ${99,}$ we've run out of symbols for the second slot, so we turn to the third slot: ${100.}$ Now we have ${10 \times 10 \times 10 = 10^3 = 1000}$ unique symbols. This allows us to count from zero to nine hundred and ninety-nine (${999}$). Once we've reached ${999,}$ the process continues. We go to the fourth slot, giving us ${10^4}$ unique symbols. Once that's run out we go to the fifth—${10^5}$ unique symbols; then the sixth—${10^6}$ unique symbols; seventh—${10^7;}$ eighth—${10^8;}$ ad infinitum.

So, we have a way to generate unique symbols. But using this approach, we have a problem: How do we ensure that someone seeing ${67}$ doesn't interpret it as ${6}$ and ${7?}$ This is accomplished by everyone agreeing to intrepret the second position as indicating how many times we've used up symbols for the first position. For example, in the case of ${67,}$ we interpet the ${6}$ as: "We've run through the symbols ${0~1~2~3~4~5~6~7~8~9}$ six times in the first position." With the ${7}$ included, the number ${67}$ translates to "Six of the ten symbols and seven of the symbols":

When we see ${826,}$ we think: "Eight of ten of the ten symbols, two of ten of the symbols, and six of the symbols:"

This process continues over and over, embodying the following pattern:

where ${k}$ and ${s_i}$ are positive integers. Each of the terms above is called a place, and they are multiples of ten. For example, ${s_2 \times 10^2}$ is the tenth's place, ${s_3 \times 10^3}$ is the hundredth's place, and so on. The term ${s_0}$ is often called the one's place, and it is mathematically denoted ${s_0 \times 10^0:}$

Primality Tests

Suppose we're given a number ${n.}$ We want to answer the following question: Is ${n}$ a prime number?

Recall the definition for a prime number. ${n}$ is a prime number only if it satisfies the following propositions:

1. ${n}$ is a natural number,
2. ${n}$ is greater than ${1,}$ and
3. ${n}$ consists of only two divisors: ${n}$ and ${1.}$

We denote the set of primes with the symbol ${\mathbb{P}.}$ The set below illustrates this, listing the first twenty-four prime numbers, with ellipses to indicate more:

Algorithms that determine whether a given number ${n}$ is a prime number are called primality tests. These algorithms are immensely important in cryptography. Cryptography itself is what ensures sensitive data like passwords, text messages, emails, and credit card numbers stay secure as they are transmitted across networks.

fn brute_force_primality_test(int n):
	if (n < 2): return "n is not prime";
	else:
	for (int i = 2; i < n - 1; i++):
		if (n % i == 0): return "n is not prime";
	return "n is prime";

trial_division_primality(int n):
	if (n < 2): return "n is not prime";
	else:
		for (int i = 2; i < (sqrt(n)); i++):
			if n % i == 0:
				return "n is not prime";
		return "n is prime";

trial_division_primality(int n):
	if (n < 2): return "n is not prime";
	else:
		for (int i = 2; i*i < n; i++):
			if n % i == 0:
				return "n is not prime";
		return "n is prime";

Prime Factorization

Closely related to primality tests is prime factorization—expressing a number as a product of their prime factors. For example, the number ${12}$ in terms of its prime factors is:

We can visualize prime factorization in terms of a tree. For example, the prime factors of ${100.}$ We start with ${2,}$ the first prime number. Since ${100}$ is divisible by ${2,}$ we get ${50:}$

Then we consider the prime factors of ${50.}$ We start again with ${2,}$ and we see that ${50}$ is also divisible by ${50:}$

Then we look at ${25.}$ We go back to testing ${2.}$ ${25}$ is not divisible by ${2,}$ so we consider the next prime number, ${3.}$ ${25}$ is not divisible by ${3,}$ so test the next prime number, ${5.}$ Here, ${25}$ is divisible by ${5:}$

Finally, we have ${5,}$ which leads to:

Once we've reached the factor ${1,}$ we know we've found the prime factors.

Implementing the procedure above in pseudocode:

int factors[100];
int exponents[100];
int length = 0;
fn primeFactors(int m) -> void:
	int d = 2;
	while (m > 1):
		int k = 0;
		while (m % d == 0):
			m = m / d;
			k++;
		if (k > 0):
			length++;
			factors[length] = d;
			exponents[length] = k;
		d++;

In the pseudocode above, the factors[] array will hold the prime factors we find, and the exponents[] array will hold the exponents we find. Let's run through the code above with a simple example. Suppose we want to find the prime factors of ${24.}$ First, we call primeFactors(24):

primeFactors(24):
	int m = 24;
	int d = 2;

We then reach while-loop-1. Here, the test condition is (m > 1). In this case, 24 > 1, so we proceed:

primeFactors(24):
	int m = 24;
	int d = 2;
		while (m > 1):
		int k = 0;

We then encounter our while-loop-2. The test condition here is (m % d == 0). In this case, (24 % 2 == 0) is true, so we proceed:

primeFactors(24):
	int m = 24;
	int d = 2;
	while (m > 1):
		int k = 0;
		while (m % d == 0):
				m = m / d; m = 24 / 2 = 12
				k++; k = 1

Given that m = 12, while-loop-2's condition is still true, so we execute again:

primeFactors(24):
	int m = 24;
	int d = 2;
	while (m > 1):
		int k = 0;
		while (m % d == 0):
				m = 12
				k = 1
				m = m / d; m = 12 / 2 = 6
				k++; k = 2

Once more our test condition is true, so we execute again

primeFactors(24):
	int m = 24;
	int d = 2;
	while (m > 1):
		int k = 0;
		while (m % d == 0):
				m = 6
				k = 2
				m = m / d;
				m = 6 / 2 = 3
				k++;
				k = 3

Going back to while-loop-2, the test condition returns false—(3 % 2 != 0). So, we go to the next line in while-loop-1. In this case, it's an if-statement, whose test condition is true:

primeFactors(24):
	int m = 24;
	int d = 2;
	while (m > 1):
		int k = 0;
		while (m % d == 0):
			m = m / d;
			k++;
			k = 3
			if (k > 0):
				factors[length] = d;
				factors[0] = 2
				exponents[length] = k;
				exponents[0] = 3
				length++ factors = 1
			d++; d = 3

Now m = 3, and we go back to while-loop-1's test condition. Here, we see that m > 1 == 3 > 1, which is true. So, we again execute while-loop-1's body. We set int k = 0, and reach while-loop-2. Here, we see that m % d == 0 is true—3 % 3 == 0. So, we proceed executing while-loop-2's body:

primeFactors(24):
	int m = 24;
	int d = 2;
		while (m > 1):
			int k = 0;
			while (m % d == 0):
				m = m / d; m = 3 / 3 = 1
				k++; k = 1

Now, with m = 1, while-loop-2's condition is false, so we exit while-loop-2 and continue with the rest of the statements in while-loop-1. We see that k > 0 ${\equiv}$ 1 > 0, so we execute the if-block:

primeFactors(24):
	int m = 24;
	int d = 2;
		while (m > 1):
			int k = 0;
			while (m % d == 0):
				m = m / d;
				k++;
			k = 1
			if (k > 0):
				length = 1
				factors[length] = d;
				factors[1] = 3;
				exponents[length] = k;
				exponents[1] = 1;
				length++ length = 2
			d++; d = 4

With m = 1, our while-loop-1's condition is false, and we have finished. With the data from these two arrays, we have:

${24 = 2^3 \times 3^1}$

Which is, in fact, the prime factorization of ${24.}$ Intuitive as this algorithm is, it performs poorly in terms of time complexity. The worst case scenario in this case is when m is a prime number. If we call primeFactors(23), for example, we would have to increment ${d}$ all the way up to ${23.}$ This leaves us with a time complexity of ${O(n).}$

Bitwise Operations

For most developers, the bitwise operations are the least used. They can, however, come in very handy with certain problems. To begin, let's review these operations:

Let's see some examples. For the bitwise-AND:

Notice that we get 1 if, and only if, we have 1 & 1. Otherwise, it's 0. Furthermore, if we converted the binary numbers above into decimal, we get:

$\texttt{5 \&{} 7 = 5}$ Now let's see the bitwise-OR:

In contrast to the bitwise-AND, for the bitwise-OR we get 0 if, and only if, we have 0 | 0. Otherwise, get 1. Thus, we have:

$\texttt{5 | 7 = 7}$

Closely related is the bitwise-XOR. This is essentially bitwise-OR, but with one restriction: We can't have two 1s. In other words, we get 1 if, and only if, we have exactly one 1:

Thus, we have: $\texttt{5 \^{} 7 = 2}$

Next, the bitwise-NOT. Unlike the previous operators, bitwise-NOT is a unary operator—it applies to only one operand. Thus:

This yields: $\texttt{\~{} 7 = 120}$