Representations found by the greedy algorithm

[Jonathan Post]

The way that I remember the Russian balanced trinary computing, the premise
was that 3 came closer to "e" than did 2, so trinary should in some sense be
closer to optimal than binary. I don't know the Russian for "flip-flap-flop"
as better than flip-flop, in circuitry.  The tale was that the advantage was
wasted in a clumsy representation of decimal in the new system. Of course,
that was a tale during the Cold War (say when I was at Caltech 1968-1973),
possibly promulgated as a joke by John Todd, Oliver Selfridge, or another
fiend of Alan Turing's,  and could easily have been disparagement, or
disinformation.

On 12/19/06, Edwin Clark <eclark at math.usf.edu> wrote:
>
>
> There is also something similiar called the non-adjacent form
> (NAF) of an integer--which is a representation of an integer
> to base 2, with "bits" 1,-1 and 0. Such a representation
> is unique if no two adjacent "bits" are nonzero. Years ago Joe
> Liang and I wrote some papers on error-correcting codes
> for arithmetic in which this idea appears. The number
> of non-zero "bits" in a NAF is an analogue of the Hamming
> weight of a binary number.  There are also generalizations
> to bases r > 2, but not quite as simple. Some of our work
> was covered in van Lint's hardback Springer yellow book on
> coding theory.
>
> So long ago I can barely recall what it was about.
>
> A google search on "non-adjacent form" will
> no doubt lead to better references.
>
> We also got a similar form for some bases for the Gaussian
> integers and other Euclidean rings. But I doubt if any of
> that is related to the current discussion.
>
>
>
> --Edwin
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20061220/df96139d/attachment-0003.htm>