Math Detours · Grade 8 · Connections · 15

Squash eight numbers into a few

Replace pairs of numbers by their average and half their difference. Throw away the small differences and you can still rebuild a recognisable copy from far fewer numbers.

Name ____________________Date ____________

Tonight's idea

A sound, or a row of pixels in a photo, is a list of numbers. Neighbours are usually close, like 4, 6 or 10, 12. Can such a list be stored with less?

Take a pair \(x, y\) and swap it for its average and half its difference:

\[a = \frac{x + y}{2}, \qquad d = \frac{x - y}{2}.\] Nothing is lost, because \(x = a + d\) and \(y = a - d\).

Do this to every pair. Then do it again to the averages only, and again, until one average is left. Eight numbers become one average and seven differences. That is still eight numbers, so nothing is saved yet. The saving comes when the list is smooth: many differences are small, and you can call them 0 and rebuild a close copy.

This is the Haar transform. It builds a list out of flat steps, called Haar wavelets, instead of the smooth sine waves used to describe musical notes.

flat (1 of these) wide step (1) half step (2) narrow step (4)
Eight building blocks: the average scales the flat one, and each difference scales one step.

Watch one: 4, 6, 10, 12, 8, 6, 5, 5

Round 1. The pairs are \((4, 6)\), \((10, 12)\), \((8, 6)\), \((5, 5)\). Averages: 5, 11, 7, 5. Differences: \(-1, -1, 1, 0\). For example \((4 - 6)/2 = -1\).

Round 2. Pair up the averages: \((5, 11)\) and \((7, 5)\). Averages: 8, 6. Differences: \(-3, 1\). Round 3. One pair left, \((8, 6)\). Average 7, difference 1.

The transform is the last average followed by the differences, newest first: \[7 \;\big|\; 1 \;\big|\; {-3},\ 1 \;\big|\; {-1},\ -1,\ 1,\ 0.\] The 7 is the average of all eight numbers. To rebuild, run the rounds backwards using \(a + d\) and \(a - d\): 7 and 1 give \(8, 6\). Then 8 with \(-3\) gives \(5, 11\), and 6 with 1 gives \(7, 5\). One more round returns the original list. Following the first number down: \(7 + 1 - 3 - 1 = 4\).

Your turn

  1. A transform reads \(10 \;\big|\; 2 \;\big|\; 1,\ -1 \;\big|\; 0,\ 1,\ 0,\ -2\). Rebuild the eight numbers, one round at a time.
  2. Find the full transform of the steady climb 2, 4, 6, 8, 10, 12, 14, 16. What happens to the size of the differences from round to round?
  3. Take the transform from the worked example and change every difference of size 1 or less to 0. (a) How many nonzero numbers are left? (b) Rebuild the eight numbers. (c) Compare with the original list. What is the largest error?
  4. (a) Find the full transform of 2, 2, 2, 2, 10, 10, 10, 10. How many of its eight numbers are not zero? (b) Do the same for 2, 2, 2, 2, 2, 10, 10, 10, where the jump comes one place later. (c) If you store only the nonzero numbers from (b) and rebuild, is the jump blurred?

Stretch: how bad can it get?

In exercise 3 each dropped difference had size 1 or less, yet one error was 2. With eight numbers, what is the largest error that dropping differences of size 1 or less could ever cause? Explain why, and find a list of eight numbers where it happens. What would the answer be for sixteen numbers?

Answers

  1. 10 with 2 gives \(12, 8\). Then 12 with 1 gives \(13, 11\), and 8 with \(-1\) gives \(7, 9\). Last round: 13 with 0 gives \(13, 13\); 11 with 1 gives \(12, 10\); 7 with 0 gives \(7, 7\); 9 with \(-2\) gives \(7, 11\). The list is 13, 13, 12, 10, 7, 7, 7, 11.
  2. Round 1: averages 3, 7, 11, 15 and differences \(-1, -1, -1, -1\). Round 2: averages 5, 13 and differences \(-2, -2\). Round 3: average 9 and difference \(-4\). The transform is \(9 \;\big|\; {-4} \;\big|\; {-2},\ -2 \;\big|\; {-1},\ -1,\ -1,\ -1\). The differences double each round, because each round compares averages that sit twice as far apart. A smooth list has small differences in round 1, but not always in the later rounds.
  3. (a) Two: the average 7 and the difference \(-3\). The transform is now \(7 \;\big|\; 0 \;\big|\; {-3},\ 0 \;\big|\; 0,\ 0,\ 0,\ 0\). (b) 7 with 0 gives \(7, 7\). Then 7 with \(-3\) gives \(4, 10\), and 7 with 0 gives \(7, 7\). Every last-round difference is 0, so each number is just repeated: 4, 4, 10, 10, 7, 7, 7, 7. (c) The original was 4, 6, 10, 12, 8, 6, 5, 5, so the errors are 0, 2, 0, 2, 1, 1, 2, 2. The largest is 2. Two numbers in place of eight give a rough copy with the right overall shape. (A real system must also record which positions the kept numbers came from.)
  4. (a) Round 1: averages 2, 2, 10, 10, differences all 0. Round 2: averages 2, 10, differences 0, 0. Round 3: average 6, difference \(-4\). Transform \(6 \;\big|\; {-4} \;\big|\; 0,\ 0 \;\big|\; 0,\ 0,\ 0,\ 0\): two nonzero numbers. (b) Round 1: averages 2, 2, 6, 10, differences \(0, 0, -4, 0\). Round 2: averages 2, 8, differences \(0, -2\). Round 3: average 5, difference \(-3\). Transform \(5 \;\big|\; {-3} \;\big|\; 0,\ -2 \;\big|\; 0,\ 0,\ -4,\ 0\): four nonzero numbers. (c) No. The numbers you left out were already 0, so the rebuilt list is exactly the original and the jump is as sharp as ever. The blocks are steps themselves, so a sudden jump costs them only a few numbers.

Stretch. The largest error is 3. Each rebuilt number is the overall average plus or minus one difference from each round, as in \(7 + 1 - 3 - 1 = 4\). With eight numbers there are three rounds, so at most three dropped differences touch any one number, and the error is at most \(1 + 1 + 1 = 3\). It happens for 10, 8, 8, 6, 8, 6, 6, 4, whose transform is \(7 \;\big|\; 1 \;\big|\; 1,\ 1 \;\big|\; 1,\ 1,\ 1,\ 1\). Dropping every difference leaves eight 7s, and the first number is off by 3. Sixteen numbers need four rounds, so the largest error is 4. Small errors can pile up, which is why exercise 3 gave an error of 2.

← PreviousNext: Find the hidden shape →