Arrays and Iteration

Array Sum (Linear Scan)

Walk an array once, accumulating each element into a running total. This is the canonical single-pass linear scan and the simplest possible loop invariant: after step i, total equals the sum of arr(1..i).

Algorithm

The canonical input from the lesson spec is arr = [3, 1, 4, 1, 5, 9, 2, 6]. After eight passes the running total is 31.

linear scan Visit each element exactly once in index order.
running total `total` accumulates the sum as the loop advances.

Basic Implementation

basic.f90
Replay: real traced execution (multi-file project)
program array_sum
    implicit none
    integer :: arr(8) = [3, 1, 4, 1, 5, 9, 2, 6]
    integer :: total, i
    total = 0
    do i = 1, 8
        total = total + arr(i)
    end do
    print '(I0)', total
end program array_sum

  1. arr ← [3, 1, 4, 1, 5, 9, 2, 6]

    2implicit none3integer :: arr(8) = [3, 1, 4, 1, 5, 9, 2, 6]4integer :: total, i
    values this step[3, 1, 4, 1, 5, 9, 2, 6]arr

  2. total ← 0

    4integer :: total, i5total = 06do i = 1, 8
    values this step0total[3, 1, 4, 1, 5, 9, 2, 6]arr

  3. total ← 3

    6do i = 1, 87    total = total + arr(i)8end do
    values this step0 → 3total1i3arr(i)

  4. total ← 4

    6do i = 1, 87    total = total + arr(i)8end do
    values this step3 → 4total2i1arr(i)

  5. total ← 8

    6do i = 1, 87    total = total + arr(i)8end do
    values this step4 → 8total3i4arr(i)

  6. total ← 9

    6do i = 1, 87    total = total + arr(i)8end do
    values this step8 → 9total4i1arr(i)

  7. total ← 14

    6do i = 1, 87    total = total + arr(i)8end do
    values this step9 → 14total5i5arr(i)

  8. total ← 23

    6do i = 1, 87    total = total + arr(i)8end do
    values this step14 → 23total6i9arr(i)

  9. total ← 25

    6do i = 1, 87    total = total + arr(i)8end do
    values this step23 → 25total7i2arr(i)

  10. total ← 31

    6do i = 1, 87    total = total + arr(i)8end do
    values this step25 → 31total8i6arr(i)

  11. stdout ← 31

    8    end do9    print '(I0)', total10end program array_sum
    values this step31stdout31total

Trace Output

trace.f90
Replay: real traced execution (multi-file project)
program array_sum_trace
    implicit none
    integer :: arr(8) = [3, 1, 4, 1, 5, 9, 2, 6]
    integer :: total, i, before
    total = 0
    do i = 1, 8
        before = total
        total = total + arr(i)
        print '(A,I0,A,I0,A,I0,A,I0,A,I0)', 'step ', i, &
            ': arr(', i, ')=', arr(i), ' total ', before, ' -> ', total
    end do
    print '(A,I0)', 'final total = ', total
end program array_sum_trace

  1. total ← 3, stdout ← step 1: arr(1)=3 total 0 -> 3

    7before = total8total = total + arr(i)9print '(A,I0,A,I0,A,I0,A,I0,A,I0)', 'step ', i, &
    values this step3totalstep 1: arr(1)=3 total 0 -> 3stdout0before3arr(i)

  2. total ← 4, stdout ← step 2: arr(2)=1 total 3 -> 4

    7before = total8total = total + arr(i)9print '(A,I0,A,I0,A,I0,A,I0,A,I0)', 'step ', i, &
    values this step4totalstep 2: arr(2)=1 total 3 -> 4stdout3before1arr(i)

  3. total ← 8, stdout ← step 3: arr(3)=4 total 4 -> 8

    7before = total8total = total + arr(i)9print '(A,I0,A,I0,A,I0,A,I0,A,I0)', 'step ', i, &
    values this step8totalstep 3: arr(3)=4 total 4 -> 8stdout4before4arr(i)

  4. total ← 9, stdout ← step 4: arr(4)=1 total 8 -> 9

    7before = total8total = total + arr(i)9print '(A,I0,A,I0,A,I0,A,I0,A,I0)', 'step ', i, &
    values this step9totalstep 4: arr(4)=1 total 8 -> 9stdout8before1arr(i)

  5. total ← 14, stdout ← step 5: arr(5)=5 total 9 -> 14

    7before = total8total = total + arr(i)9print '(A,I0,A,I0,A,I0,A,I0,A,I0)', 'step ', i, &
    values this step14totalstep 5: arr(5)=5 total 9 -> 14stdout9before5arr(i)

  6. total ← 23, stdout ← step 6: arr(6)=9 total 14 -> 23

    7before = total8total = total + arr(i)9print '(A,I0,A,I0,A,I0,A,I0,A,I0)', 'step ', i, &
    values this step23totalstep 6: arr(6)=9 total 14 -> 23stdout14before9arr(i)

  7. total ← 25, stdout ← step 7: arr(7)=2 total 23 -> 25

    7before = total8total = total + arr(i)9print '(A,I0,A,I0,A,I0,A,I0,A,I0)', 'step ', i, &
    values this step25totalstep 7: arr(7)=2 total 23 -> 25stdout23before2arr(i)

  8. total ← 31, stdout ← step 8: arr(8)=6 total 25 -> 31

    7before = total8total = total + arr(i)9print '(A,I0,A,I0,A,I0,A,I0,A,I0)', 'step ', i, &
    values this step31totalstep 8: arr(8)=6 total 25 -> 31stdout25before6arr(i)

  9. stdout ← final total = 31

    11    end do12    print '(A,I0)', 'final total = ', total13end program array_sum_trace
    values this stepfinal total = 31stdout31total

Complexity

  • Time: O(n)
  • Space: O(1)

Implementation notes

  • Fortran: use an explicit do i = 1, 8 loop. Calling sum(arr) would hide the iteration the lesson is teaching.
  • The replay shows i, arr(i), and total before and after each addition, matching the lesson spec's state-transition table. The trace variant prints step i: arr(i)=V total B -> T for each visit and a closing final total = 31 summary.