Ch1.3.1 Summation Algorithms

Choice of Algorithm Matters

When we write programs, we implement a particular algorithm to perform a task.
Some algorithms are faster and more accurate than others for the same task.
Speed can be measured by clock time, iteration count, flop count, etc.
Accuracy can be measured by absolute error, relative error, precision, etc. (Ch2.1)

Summation Algorithms

Adding up numbers seems like an important but basic task.
We will look at several algorithms for summations.
What could possibly make one algorithm better than another?

\[ x_1 + x_2 + \cdots + x_n = \sum_{i=1}^n x_i \]

Naive Sum: Straightforward Approach

Given a vector x of data values, the naive approach is to add successive terms, one at a time, in the order that they appear in x.

naivesum1 <- function(x) {
  s <- 0
  n <- length(x)

  for(i in 1:n)
    s <- s + x[i]
  return(s)
}

x <- c(1,1,3,5,8,13,21,34)

Naive Sum: Straightforward Approach

naivesum1 <- function(x) {
  s <- 0
  n <- length(x)

  for(i in 1:n)
    s <- s + x[i]
  return(s)
}

x <- c(1,1,3,5,8,13,21,34)

naivesum1(x)

[1] 86

Naive Sum: Straightforward Approach

naivesum2 <- function(x) {
  s <- 0
  n <- length(x)

  for(i in 1:n){
    s <- s + x[i]
    cat("i = ", i,",", "s = ", s, "\n")}
  return(s)
}

x <- c(1,1,3,5,8,13,21,34)

naivesum2(x)

i =  1 , s =  1 
i =  2 , s =  2 
i =  3 , s =  5 
i =  4 , s =  10 
i =  5 , s =  18 
i =  6 , s =  31 
i =  7 , s =  52 
i =  8 , s =  86

[1] 86

Naive Sum: Discussion

naivesum1 <- function(x) {
  s <- 0
  n <- length(x)

  for(i in 1:n)
    s <- s + x[i]
  return(s)
}

x <- c(1,1,3,5,8,13,21,34)

naivesum1(x)

[1] 86

Check i = n to exit from loop (we will not address this)
Small number may not contribute when added to large number (more later)

Naive Sum: Reduce flop count by 1

naivesum1<-function(x){
  s <- 0
  n <- length(x)

  for(i in 1:n)
    s <- s + x[i]
  return(s)
}

x <- c(1,1,3,5,8,13,21,34)

naivesum1(x)

[1] 86

naivesum3<-function(x){
  s <- x[1]
  n <- length(x)

  for(i in 2:n)
    s <- s + x[i]
  return(s)
}

x <- c(1,1,3,5,8,13,21,34)

naivesum3(x)

[1] 86

Sort Sum: More accurate, more operations

naivesum1<-function(x){
  s <- 0
  n <- length(x)

  for(i in 1:n)
    s <- s + x[i]
  return(s)
}

x<-c(20,0.01,3.14,8)

naivesum1(x)

[1] 31.15

naivesum4<-function(x){
  y <- sort(x)
  s <- 0
  n <- length(y)

  for(i in 1:n)
    s <- s + y[i]
  return(s)
}

x<-c(20,0.01,3.14,8)

naivesum4(x)

[1] 31.15

Pairwise Sum: Successive Grouping

Addition is associative, so can regroup terms to add.
Group and move upwards through tree in figure below

Fig 1.4: Move up through tree

Eqn1.2: Move up through tree Fig 1.4: Move up through tree

Pairwise Sum: Successive Grouping

Recursively call pwisesum (one addition flop each)

pwisesum <- function(x) {
n <- length(x)

if(n == 1)
    return(x)
m = floor(n / 2)
return(pwisesum(x[1:m]) + pwisesum(x[(m + 1):n]))
}

x <- c(1,1,3,5,8,13,21,34)
pwisesum(x)

[1] 86

Kahan Sum

Part of a larger script not shown; see book.
s = running total, t = temporary value, comp = compensation.

kahansum <- function(x) {
    comp <- s <- 0
    n <- length(x)

    for(i in 1:n) {
        y <- x[i] - comp
        t <- x[i] + s
        comp <- (t - s) - y
        s <- t
    }
    return(s)
}

Kahan Sum

Mathematically, the running sum should be the actual running sum and the compensation should always be 0.
With machine computation, this may not be the case.

kahansum <- function(x) {
    comp <- s <- 0
    n <- length(x)

    for(i in 1:n) {
        y <- x[i] - comp
        t <- x[i] + s
        comp <- (t - s) - y
        s <- t }
    return(s)
}

Kahan Sum

kahansum <- function(x) {
    comp <- s <- 0
    n <- length(x)

    for(i in 1:n) {
        y <- x[i] - comp
        t <- x[i] + s
        comp <- (t - s) - y
        s <- t }
    return(s)
}

x <- c(1,1,3,5,8,13,21,34)
kahansum(x)

[1] 86

The Sum Function

Summations are essential to scientific computation.
Most, if not all, computational software packages have a built-in summation function.
These are typically robust, fast and accurate.

x <- c(1,1,3,5,8,13,21,34)
sum(x)

[1] 86