Quilted Dies of CPU & RAM

[Dave Long]

> Interesting.  Ward Cunningham is currently using bit-reversed counters
> in his Bynase code for PDM [0] --- he's doing the equivalent of a
> fixed dither pattern in the time domain rather than just doing the
> delta-sigma thing.

Gradients work pretty well for simplistic goal seeking.  It's possible  
to use the statistics of sums of random numbers to create  
bacterium-like foo-taxis using a pair of motors instead of a flagellum.  
  (I believe current understanding is that the flagellum has a true  
rotary driver, and is stranded, like a rope -- so rotation in the  
aligned sense produces propulsion, but rotation counter to that  
separates the strands and produces a tumble.  Operations Research at  
the microbial level pretty much consists of deciding between "stay the  
course" and "try something new")

Any idea why he's using the reversed counter instead of an LFSR to  
dither?

[On an older page, he mentions that tiny12s don't have a "register  
based jump instruction".  I generally use table-driven state machines  
on the tiny13s (there not being room for much else), with dynamic  
linkage via PUSH/RET, which seems simple enough to work on just about  
any AVR]

> My current best approaches to this in software are
>
>   unsigned char spec_binc(unsigned char acc) {
>     unsigned char mask;
>     for (mask = 0x80; mask & acc; mask >>= 1)
>       acc ^= mask;
>     return mask | acc;
>   }

The worst case doesn't matter so much, as it only occurs once every 256  
increments.  Half the time, it's only the first bit that flips, which I  
think comes down to:

ldi mask, 0x80
mov t0, mask
and t0, acc
brz (taken)
or acc, mask

or about 6 clocks, giving an average cost of close to 13.

>   unsigned char table16[] = { 0x08, 0x09, 0x0a, 0x0b,  0x0c, 0x0d,  
> 0x0e, 0x0f,
>                               0x04, 0x05, 0x06, 0x07,  0x02, 0x03,  
> 0x01, 0x00 };
>
>   unsigned char table16_reverse_counter(unsigned char input) {
>     unsigned char lefthalf = input >> 4;
>     unsigned char nextleft = table16[lefthalf];
>     unsigned char righthalf = input & 0x0f;
>     unsigned char nextright = (nextleft ? righthalf :  
> table16[righthalf]);
>     return ((unsigned char)(nextleft << 4) | nextright);
>   }
>
> which I think can be better both in the average case and the worst
> case if you avoid doing address arithmetic

What does gcc generate for this?  Doing it by hand, I'd need 8 clocks  
worth of LSR and LSL for shifting lefthalf/nextleft, 2 clocks for the  
ANDI and OR on righthalf, and 3 more clocks (avg) for the two lookups.   
That's already more expensive, without even handling the conditional.

If there's a way to do multiple shifts, then the following fixed-time  
algorithm (using boolean smears a la APL*) would be competitive, but as  
it stands the eight places worth of ASR take more than half the budget.

def revinc8(x):
         y = x                   & 0xff          # 1     1110....
         y &= (y>>1)             + 0x80          # 3     11100...
         y &= (y>>2)             + 0xc0          # 4     1110000.
         y &= (y>>4)             + 0xf0          # 6     11100000
         m = (y >> 1)            + 0x80          # 1     11110000
         return (x ^ m)          & 0xff          # 1     0001....

-Dave

:: :: ::

* smearing is one of the oldest techniques in CS.  To digress a bit,  
I'd mentioned being surprised at finding out how elegantly the idea of  
a while-loop consisting of a (one hopes) finite sequence of operations  
followed by an infinite tail of identity ops (f**0, where f**1 is our  
original op) worked in J:

"J, Dijkstra, while-loops, and infinity"
http://lists.canonical.org/pipermail/kragen-discuss/2003-February/ 
000897.html

Well, it seems that it wasn't just pure coincidence: Iverson, who  
originated the APL family of array languages, is also apparently known  
in mathematical circles for introducing the "Iverson bracket" notation,  
in which suitable use of boolean expressions allow one to express  
finite summations and integrals as more readily manipulated infinite  
ones.  (similar to how wavefunctions are integrated over all of space,  
but, at the classical scale, are really only concerned with points  
thereof).  It seems like an obvious improvement these days, but that  
may just be the influence of several decades of computers.

But it turns out it works in theory as well as in practice, and Kleene,  
by 1952, used zero to both (a) absorb multiplications and (b) preserve  
additions, in order to define the μ operator for minimization.  In APL  
terms, it was a product scan followed by a sum reduction (+/*\), which  
meant that the first solution (first zero bit after a string of ones,  
just as in the reverse adder above) would cause its success to  
propagate (0*X=0) through the remainder of the naturals.  Adding up  
that initial string of ones then ignores the infinite tail of zeros  
(X+0=X), yielding the first natural with a solution.

http://en.wikipedia.org/wiki/Mu_operator

[ Knuth finds even deeper roots here, tracing it back to an Italian  
HAKMEM of the 1830's exploring the use of expressions of the form  
0**0**x:
Donald Knuth, "Two Notes on Notation", American Mathematical Monthly,  
Volume 99, Number 5, May 1992, pp. 403-422.  
http://arxiv.org/PS_cache/math/pdf/9205/9205211.pdf]