Ch2.4.1 & 2.4.2 Division Algorithms

Integer Long Division Algorithm

We start with two examples using basic R commands.
Then we use an algorithm that performs basic division on integers \( a \) and \( b \), returning the quotient and a remainder.
In figure below, \( a/b \) is computed using long division, where \( a = 300 \) and \( b = 7 \).

title

Example 1: Use R Commands

Consider \( 300/7 \)

title

300/7

[1] 42.85714

7*(300/7 - 42)

[1] 6

Example 1: Use R Commands

Consider \( 300/7 \)

title

floor(300/7)

[1] 42

300 %% 7

[1] 6

Example 2: Use R Commands

Consider \( 487/32 \)

title

R commands

floor(487/32)

[1] 15

487 %% 32

[1] 7

Understanding Multiplication & Division

title

Division reverses process of multiplication.
Multiplication is a shortcut to addition, successively adding blocks of numbers together to obtain result.
To reverse this for division, successively subtract off blocks of numbers.

Understanding Multiplication & Division

title

To find \( a \times b=c \), add blocks of size \( b \) together \( a \) times to obtain result \( c \).
To find \( c = a/b \), subtract blocks of size \( b \) from \( a \) to obtain \( c \).
Here remainder is zero.

Algorithm: naivediv

naivediv <- function (a, b) {
quot <- 0
r <- a
if(b == 0)
  stop (" Attempted division by 0")
while (r >= b) {
quot <- quot + 1
r <- r - b  }
return(list(quotient = quot, remainder = r))}

Algorithm: naivediv1

naivediv1 <- function (a, b) {
quot <- 0
r <- a
cat("r = ", r, "q = ", quot, "\n")
if(b == 0)
  stop (" Attempted division by 0")
while (r >= b) {
  quot <- quot + 1
  r <- r - b
  cat("r = ", r, "q = ", quot, "\n") }
return(list(quotient = quot, remainder = r))}

Understanding Multiplication & Division

title

To find quotient and remainder for \( 12/3 \):
Successively subtract blocks of size 3 a total of \( q = 4 \) times with remainder \( r = 0 \).

Example: Direct Approach

naivediv(12,3)

$quotient
[1] 4

$remainder
[1] 0

naivediv1(12,3)

r =  12 q =  0 
r =  9 q =  1 
r =  6 q =  2 
r =  3 q =  3 
r =  0 q =  4

$quotient
[1] 4

$remainder
[1] 0

Example: Direct Approach

naivediv(50,15)

$quotient
[1] 3

$remainder
[1] 5

naivediv1(50,15)

r =  50 q =  0 
r =  35 q =  1 
r =  20 q =  2 
r =  5 q =  3

$quotient
[1] 3

$remainder
[1] 5

Naive Algorithms

The simplest and most straightforward (naive) algorithms are the easiest to understand.
They help illustrate basic points in numerical analysis.
More sophisticated ones use numerical analysis concepts.
These provide faster, reliable, and more accurate results than the naive algorithms.

c(floor(300/7), 300 %% 7)

[1] 42  6

Our Naive Algorithm

Our naivediv is inefficient.
Loops \( \lfloor a/b \rfloor \) times.
That is a lot, and while this reduces when \( b \) is larger, it increases when \( a \) is larger.

floor(5/2)

[1] 2

naivediv1(5,2)

r =  5 q =  0 
r =  3 q =  1 
r =  1 q =  2

$quotient
[1] 2

$remainder
[1] 1

Algorithm: naivediv2

naivediv2 <- function (a, b) {
  quot <- 0
  r <- a
  cat("r = ", r, "q = ", quot, "\n")
  if(b == 0)
    stop (" Attempted division by 0")
  while (r >= b) {
    quot <- quot + 1
    r <- r - b
    cat("r = ", r, "q = ", quot, "\n") }
   }

Example: Direct Approach

naivediv2(25,2)

r =  25 q =  0 
r =  23 q =  1 
r =  21 q =  2 
r =  19 q =  3 
r =  17 q =  4 
r =  15 q =  5 
r =  13 q =  6 
r =  11 q =  7 
r =  9 q =  8 
r =  7 q =  9 
r =  5 q =  10 
r =  3 q =  11 
r =  1 q =  12

naivediv2(487,32)

r =  487 q =  0 
r =  455 q =  1 
r =  423 q =  2 
r =  391 q =  3 
r =  359 q =  4 
r =  327 q =  5 
r =  295 q =  6 
r =  263 q =  7 
r =  231 q =  8 
r =  199 q =  9 
r =  167 q =  10 
r =  135 q =  11 
r =  103 q =  12 
r =  71 q =  13 
r =  39 q =  14 
r =  7 q =  15

More sophisticated Approach

To reduce operation count, we revisit the mathematical process and seek to better understand steps.
Is there a way to rearrange the operations in a way that is more efficient and/or accurate?
Is there a way to make use of the way R processes integers in order to improve efficiency and accuracy?

Revisit Long Division Algorithm

title

Revisit Long Division Algorithm

title

1010 %% (100*6)

[1] 410

410 %% (50*6)

[1] 110

110 %% (10*6)

[1] 50

Revisit Long Division Algorithm

title

Successively apply \( d = 32q + r \)
Subtract \( q=0 \) blocks of 32 from \( r = 4 \)
Subtract \( q=1 \) blocks of 32 from \( r = 48 \)
Subtract \( q=5 \) blocks of 32 from \( r = 167 \)
Stop here, because \( q = 0 \) and \( r = 7 < 32 \)

More sophisticated Approach

Rather than use the digits of a decimal system, the book translates this process to bits of binary system.
The book then uses internal R bit shift functions for performing binary operations at each step of long division.

r <- bitwShiftL(r,1)
r <- r + bitwAnd(bitwShiftR(a,i),1)

The result is the longdiv algorithm that is generally a more efficient algorithm.
For example, longdiv(1000/3) loops 32 times, while naivediv(1000/3) loops 333 times.

Algorithm: longdiv1

longdiv1 <- function(a, b) {
quot <- 0
r <- 0
if(b == 0)
  stop (" Attempted division by 0")
for(i in 31:0) {
  r <- bitwShiftL(r, 1)
  r <- r + bitwAnd(bitwShiftR(a, i), 1)
  if(r >= b) {
    r <- r - b
    quot <- quot + bitwShiftL(1, i)}}
return(list(quotient = quot, remainder = r))}

Algorithm: longdiv1cat

longdiv1cat <- function(a,b){quot <- 0
r <- 0
cat("i =",0,"r= ", r," q = ", quot,"\n")
cat("i=",i,"r=",r,"bSLr1=",bitwShiftL(r,1),"\n")
r <- bitwShiftL (r, 1)
r <- r + bitwAnd(bitwShiftR(a, i), 1)
cat("i = ", i, "bSRai = ", bitwShiftR(a, i),
  "bwA = ",bitwAnd(bitwShiftR(a,i),1),"\n")
cat("i = ", i, "r = ", r, "\n")
if(r >= b) {
r <- r - b
cat("i=",i,"bSL1i=",bitwShiftL(1,i),"\n")
  quot <- quot + bitwShiftL (1, i)
  cat("i = ", i, "r = ", r, "q = ",quot,"\n") } 
  return(list(quotient=quot,remainder = r))}

Algorithm: longdiv1cat

title

Results of script for 9/4
See Week 6 folder.

floor(9/4)

[1] 2

9 %% 4

[1] 1

Algorithm: longdiv2

longdiv2 <- function(a, b) {
quot <- 0
r <- 0
count <- 0
if(b == 0)
  stop (" Attempted division by 0")
for(i in 31:0) {
  r <- bitwShiftL(r, 1)
  r <- r + bitwAnd(bitwShiftR(a, i), 1)
  count <- count + 1
  if(r >= b) {
    r <- r - b
    quot <- quot + bitwShiftL(1, i)}}
    count <- count + 1
return(list(quotient = quot, remainder = r, count = count))}

Algorithm: naivediv3

naivediv3 <- function (a, b) {
quot <- 0
r <- a
count <- 0
if(b == 0)
  stop (" Attempted division by 0")
while (r >= b) {
quot <- quot + 1
r <- r - b
count <- count + 1}
return(list(quotient = quot, remainder = r, count = count))}

Example: naivediv3 & longdiv2

naivediv3(1000,3)

$quotient
[1] 333

$remainder
[1] 1

$count
[1] 333

longdiv2(1000,3)

$quotient
[1] 333

$remainder
[1] 1

$count
[1] 33

Example: naivediv3 & longdiv2

naivediv3(487,32)

$quotient
[1] 15

$remainder
[1] 7

$count
[1] 15

longdiv2(487,32)

$quotient
[1] 15

$remainder
[1] 7

$count
[1] 33

Example: naivediv3 & longdiv2

naivediv3(44100,2)

$quotient
[1] 22050

$remainder
[1] 0

$count
[1] 22050

longdiv2(44100,2)

$quotient
[1] 22050

$remainder
[1] 0

$count
[1] 33

Numerical Analysis & Algorithms

The simplest and most straightforward (naive) algorithms are the easiest to understand.
They help illustrate basic points in numerical analysis.
More sophisticated ones use numerical analysis concepts.
These provide faster, reliable, and more accurate results than the naive algorithms.

c(floor(300/7), 300 %% 7)

[1] 42  6

Computer Arithmetic in Chapters 1 & 2

Arithmetic and numerical representation are essential to computational science and numerical analysis.
Summation (Ch1): Efficiency & accuracy; flops
Subtraction (Ch2): Cancellation error; rearrangement
Multiplication (Ch2): Floating point format, process leading digits and exponents on base.
Divison (Ch2): Division algorithm, efficiency; flops; binary integer format