A pixmap shall be turned from black to white, turning all pixels to white in the process.  But for optical reasons this shall *not* happen linearly, starting at the top and continuing line by line to the bottom:

```python
for y in range(height):
  for x in range(width):
     setBit(x, y)
```

Instead it shall be done by a systematic dithering routine which selects the coordinates on which pixels are to be set in a precise pattern so that the geometrical distance between two consecutive pixels is large and a specific optical effect results.

The following diagrams show the order of the coordinates the algorithm shall produce:

2×2:
```
1 3
4 2
```
4×4:
```
 1  9  3 11
13  5 15  7
 4 12  2 10
16  8 14  6
```
8×8:
```
 1  33   9  41   3  35  11  43 
49  17  57  25  51  19  59  27 
13  45   5  37  15  47   7  39 
61  29  53  21  63  31  55  23 
 4  36  12  44   2  34  10  42 
52  20  60  28  50  18  58  26 
16  48   8  40  14  46   6  38 
64  32  56  24  62  30  54  22 
```
The pattern continues like that for each square pixmap with a width and height of a power of two (16, 32, 64, …).

But the width and the height of the pixmap can be arbitrary positive numbers.  If the pixmap's width and/or height are not a power of two, the coordinates the algorithm  would produce outside of the pixmap are skipped:

3×3:
```
1 6 3
8 5 9
4 7 2   
```
6×5:
```
 1 16  6 21  3 18
25 10 28 13 26 11
 8 23  5 20  9 24
29 14 27 12 30 15
 4 19  7 22  2 17
```
Write an algorithm which produces the coordinates of the dithering for a given width and height.

To pass the Python test cases, write a *generator* ```dithering()``` which yields coordinate tuples:
```python
g = dithering(6, 5)
for i in range(7):
  print g.next()
```
Will print:
```
(0, 0)
(4, 4)
(4, 0)
(0, 4)
(2, 2)
(2, 0)
(2, 4)
```

Difficulty: MEDIUM

Starter code:
def dithering(width, height):
	

Solutions:
def dithering(width, height, x=0, y=0, c=1):
	if width <= c and height <= c:
		if x < width and y < height:
			yield (x, y)
		return
	for (u, v) in ((0, 0), (c, c), (c, 0), (0, c)):
		for (p, q) in dithering(width, height, x + u, y + v, c + c):
			yield (p, q)


def dithering(width, height):
	size = 1
	while width > size or height > size:
		size *= 2
	if size == 1:
		yield (0, 0)
	else:
		for (x, y) in dithering(size / 2, size / 2):
			for t in ((x, y), (x + size / 2, y + size / 2), (x + size / 2, y), (x, y + size / 2)):
				if t[0] < width and t[1] < height:
					yield t


from math import *

def dithering(x, y):

	def di2(x):
		if x == 1:
			for i in [(0, 0), (1, 1), (1, 0), (0, 1)]:
				yield i
		else:
			for (i, j) in di2(x - 1):
				for (a, b) in di2(1):
					yield (i + a * 2 ** (x - 1), j + b * 2 ** (x - 1))
	for i in di2(int(ceil(log(max(x, y), 2)))):
		if i[0] < x and i[1] < y:
			yield i


from math import ceil, log2

def dithering(width, height):
	pow2dim = max((ceil(log2(x)) for x in [width, height]))
	pos = [0] * pow2dim
	for _ in range((2 ** pow2dim) ** 2):
		(x, y) = (0, 0)
		for idx in range(pow2dim):
			if pos[idx] in [1, 2]:
				x += 2 ** (pow2dim - idx - 1)
			if pos[idx] in [1, 3]:
				y += 2 ** (pow2dim - idx - 1)
		if x < width and y < height:
			yield (x, y)
		for idx in range(pow2dim):
			pos[idx] = (pos[idx] + 1) % 4
			if pos[idx] > 0:
				break


from math import ceil, log2

def dithering(width, height):
	size = ceil(log2(max(width, height)))
	grid = [(0, 0), (1, 1), (1, 0), (0, 1)]
	add = 2
	for i in range(size - 1):
		g = []
		for gg in grid:
			g.append(gg)
			g.append((gg[0] + add, gg[1] + add))
			g.append((gg[0] + add, gg[1]))
			g.append((gg[0], gg[1] + add))
		grid = g
		add *= 2
	for i in range(len(grid) - 1, -1, -1):
		if grid[i][0] >= width or grid[i][1] >= height:
			del grid[i]
	return iter(grid)


from itertools import cycle
from math import log2, ceil

def dithering(h, w):

	def rec(x, y, d, sendIt=True):
		d >>= 1
		if d:
			for g in cycle((rec(x + d * dx, y + d * dy, d, i) for (i, (dx, dy)) in enumerate([(0, 0), (1, 1), (1, 0), (0, 1)]))):
				yield next(g)
		else:
			yield (x, y)
	for (x, y) in rec(0, 0, 2 ** ceil(log2(max(w, h)))):
		if 0 <= x < h and 0 <= y < w:
			yield (x, y)


def gen_id():
	i = 1
	while True:
		yield i
		i += 1

def dithering(width, height):
	result = []
	pix_map = []
	max_step = 1
	while max_step <= max(width - 1, height - 1):
		max_step *= 2
	for i in range(height):
		temp_list = [0] * width
		pix_map.append(temp_list)
	start = (0, 0)
	recursion(result, 1, max_step, start, pix_map)
	for i in result:
		yield i

def recursion(result, step, max_step, start, pix_map):
	if step * 2 <= max_step:
		recursion(result, step * 2, max_step, (start[0], start[1]), pix_map)
		recursion(result, step * 2, max_step, (start[0] + step, start[1] + step), pix_map)
		recursion(result, step * 2, max_step, (start[0], start[1] + step), pix_map)
		recursion(result, step * 2, max_step, (start[0] + step, start[1]), pix_map)
	if len(pix_map) > start[0] and len(pix_map[start[0]]) > start[1] and (pix_map[start[0]][start[1]] == 0):
		pix_map[start[0]][start[1]] = num_gen.__next__()
		result.append((start[1], start[0]))
	if len(pix_map) > start[0] + step and len(pix_map[start[0]]) > start[1] + step and (pix_map[start[0] + step][start[1] + step] == 0):
		pix_map[start[0] + step][start[1] + step] = num_gen.__next__()
		result.append((start[1] + step, start[0] + step))
	if len(pix_map) > start[0] and len(pix_map[start[0]]) > start[1] + step and (pix_map[start[0]][start[1] + step] == 0):
		pix_map[start[0]][start[1] + step] = num_gen.__next__()
		result.append((start[1] + step, start[0]))
	if len(pix_map) > start[0] + step and len(pix_map[start[0]]) > start[1] and (pix_map[start[0] + step][start[1]] == 0):
		pix_map[start[0] + step][start[1]] = num_gen.__next__()
		result.append((start[1], start[0] + step))
num_gen = gen_id()


def dithering(width, height):

	def rec(v, x, y):
		if not (x < width and y < height):
			return
		if not (x + v < width or y + v < height):
			yield (x, y)
			return
		for k in rec(2 * v, x, y):
			yield k
		for k in rec(2 * v, x + v, y + v):
			yield k
		for k in rec(2 * v, x + v, y):
			yield k
		for k in rec(2 * v, x, y + v):
			yield k
	for k in rec(1, 0, 0):
		yield k


import math

def dithering(width, height):
	d = int(math.pow(2, math.ceil(math.log(max(width, height), 2))))
	return ((x, y) for (x, y) in _dithering(d) if x < width and y < height)

def _dithering(d):
	if d == 1:
		yield (0, 0)
		return
	fac = d // 2
	for (x, y) in _dithering(d >> 1):
		yield (x, y)
		yield (x + fac, y + fac)
		yield (x + fac, y)
		yield (x, y + fac)