title: An efficient integer one dimensional dithering function?
body: <p>I've been playing with LEDs a lot recently, powered by 8-bit micro controllers. Sometimes it's necessary to use purely software implementations of Pulse Width Modulation to control LED brightness - that is turning the light on and off rapidly varying the ratio of time on and off. This works great until I get down to about 5% brightness, where the strobing starts looking uncomfortably flickery to the eye.</p>
  
  <p>Implementing the PWM as a loop, it steps through each number from 0-255 setting the light on or off for that moment. A light which is set at the 20 value will be on for the first 20 loops then turned off.</p>
  
  <p>I'm looking for a good function which will shuffle around those numbers, so instead of looping through 0, 1, 2, 3... my loop could sample semi-randomly from the pool of possibilities. The aggregate brightness over time is the same, but a light at 20 brightness value may switch on and off a dozen or so times spread across 256 loops instead of just lighting once then turning off for most of the loop. This reduces the flickering effect even if the loop runs slightly slower.</p>
  
  <p>A good dithering function would need to return every number in the 8-bit range when called with every 8-bit number. It would therefore also need to produce no duplicate numbers - not random, just shuffled. It's best if it tends not to put similar numbers together in sequence - the difference between each number aught to be high - ideally about 64-127 I figure.</p>
  
  <p>The limitations are also interesting - it's a time critical application. Addition, subtraction, and bitwise operations cost 1 arbitrary unit of time, multiplication costs 2 units, and division costs 4 units. Floats are out of the questions, and the costs roughly double for every multiple of 8 bits used in an intermediate number. Lookup tables are possible, but would use roughly half of the total memory capacity of the device - so fast algorithms are best for reusability, but good quality slow algorithms are also very useful when there's space to precompute.</p>
  
  <p>Thanks for helping me out with any ideas or musings. :)</p>