Skip to content

Integer Representations ​

Theorem 1 ​

  • For any integer b>1 (the base) and any positive integer n, there is a unique representation:
n=akbk+ak−1bk−1+⋯+a1b+a0

where:

  • k≥0 is an integer (the highest power of b in the representation).
  • a0,a1,…,ak are digits, each satisfying 0≤ai<b.
  • ak≠0 (so the first digit is not zero, ensuring uniqueness).

💡

Theorem 1 is called the base b expansion of n

Expansions ​

  • Decimal: b = 10
  • Binary : b = 2
  • hexadecimal: b = 16
  • Octal: b = 8

Base conversion ​

  1. First, divide n by b to obtain a quotient and remainder, that is,
n=bq0+a0 , where 0≤a0<b
  1. The remainder, a0, is the rightmost digit in the base b expansion of n. Next, divide q0 by b to obtain
q0=bq1+a1 , where 0≤a1<b
  1. a1 is the second digit from the right in the base b expansion of n
  2. Continue this process until we obtain a quotient equal to zero.

image.png

Algorithm ​

image.png

Conversion between 2, 16 and 8 expansions ​

  • Each octal digit corresponds to a block of three binary digits
  • Each hexadecimal digit corresponds to a block of four binary digits

Algorithms for Integer Operations ​

✅

The algorithms for performing operations with integers using their binary expansions are extremely important in computer arithmetic

Throughout this discussion, suppose that the binary expansions of a and b are

a=(an−1an−2...a1a0)2,b=(bn−1bn−2...b1b0)2

so that a and b each have n bits

Addition algorithm ​

  1. To add a and b, first add their rightmost bits. This gives
a0+b0=c0⋅2+s0
  • where
    • s0 is the rightmost bit (LSB) in the binary expansion of a + b
    • c0 is the carry, which is either 0 or 1
  1. Then add the next pair of bits and the carry,
a1+b1+c0=c1⋅2+s1
  • where
    • s1 is the next bit (from the right) in the binary expansion of a + b
    • c1 is carry
  1. Continue this process
  2. At the last stage,
an−1+bn−1+cn−2=cn−1⋅2+sn−1
  • Then, the leading bit of the sum is sn=cn−1

✅

a+b=(snsn−1sn−2...s1s0)2

image.png

Multiplication algorithm ​

  • Using the distributive law, we see that
ab=a(b020+b121+⋯+bn−12n−1)=a(b020)+a(b121)+⋯+a(bn−12n−1)
  • We first note that:
    • abj=a if bj=1
    • abj=0 if bj=0
  1. Each time we multiply a term by 2, we shift its binary expansion one place to the left and add a zero at the tail end of the expansion:
a⋅21=a<<1a⋅2n=a<<n
  1. Consequently, we can get (abj)2j by shifting the binary expansion of abj j places to the left, that
(abj)2j=(abj)<<j
  1. Finally, we get ab by adding the n integers abj2j, j = 0, 1, 2, ... , n − 1.
  • Pseudocode

image.png

Algorithm for DIV and MOD ​

image.png

  • This algorithm takes O(qloga) bit operations

Modular Exponentiation ​

  • How to find efficiently without using an excessive amount of memory for
bn mod m -- where b, n and m are large integers
  • Some thought,
    1. It is impractical to first compute bn and then find its remainder when divided by m, because bn can be a huge number
    2. We can apply Corollary 2 of Theorem 5 at [4.1] Divisibility and Modular which is
(ab) mod m=((a mod m)(b mod m)) mod m

Then, we have (Recall that 1≤b<m)

bk+1 mod m=b(bk mod m) mod m

However, this approach is impractical because it requires n − 1 multiplications of integers and n might be huge.

Fast modular exponentiation algorithm ​

  • Note that, If we use the base 2 expansion of n, then
bn=bak−1⋅2k−1+...a1⋅2+a0=bak−1⋅2k−1⋅...⋅ba1⋅2⋅ba0
  • This shows that to compute bn, we need only compute the values of
    • b,b2,(b2)2=b4,(b4)2=b8,...,(b2n)2=b2k
  • The algorithm successively finds
    • b mod m,
    • b2 mod m,
    • b4 mod m, ... ,
    • b2k−1 mod m and
    • multiplies together those terms b2j mod m where aj=1

image.png

Cantor Expansion ​

Definition ​

A Cantor expansion represents a non-negative integer as

n=akk!+ak−1(k−1)!+⋯+a22!+a11!

where

0≤ai≤ifor i=1,2,…,k

This representation is also known as the factorial number system.


Properties ​

1. Uniqueness ​

Every non-negative integer has a unique Cantor expansion.

2. Mixed radix system ​

Cantor expansion is not a fixed-base system. The radix at position i is (i+1).

3. Bounded digits ​

Each coefficient has a strict bound:

  • a1∈{0,1}
  • a2∈{0,1,2}
  • …
  • ak∈{0,1,…,k}

Finding the Cantor Expansion ​

Algorithm ​

Given an integer N:

  1. Find the largest k such that k!≤N
  2. Computeak=⌊Nk!⌋
  3. UpdateN←N−akk!
  4. Repeat for (k−1)!,(k−2)!,…,1!

Example ​

Find the Cantor expansion of 1000.

(1,2,1,2,2,0)

Why Cantor Expansion Works ​

Because

1!+2!+⋯+k!<(k+1)!

this guarantees:

  • No overlap between representations
  • Each sequence (a1,…,ak) maps to a distinct integer

Built with ❤️ and curiosity