Byte order

[Frank Adams]

In article <17312 at rochester.ARPA> crowl at rochester.UUCP (Lawrence Crowl) writes:
>>I wrote:
>>>CHALLENGE:  Come up with a scheme for representing numbers, and a sorting
>>>scheme in which numbers sort naturally.  Your scheme must deal with variable
>>>length character strings and variable size numbers.  That is, you cannot
>>>require strings to be padded with nulls, or numbers to be padded with zeros.
>
>Arch D. Robison wrote:
>>...       -4 = AAAAZ   -3 = AAAZ   -2 = AAZ   -1 = AZ 
>>  0 = M    1 = Z        2 = ZZ      3 = ZZZ    4 = ZZZZ ...
>>
>
>An interesting solution.  I totally failed to consider unary notations.  Just
>to keep the answers honest, I will add the requirement that some efficient
>form of representation be used.  Radix notation is efficient, but you are not
>required to use it.  For extra credit, extend your notation to deal with
>non-integral values.  This is easy under current notation if the integral
>part is the same.

Basically, you use a unary notation (pure or modified) to indicate how long
the number is, and the number follows.  Using the scheme above, 257 would
be ZZZ257.  One and a half would be Z15.  This is essentially floating point
notation.

This has to be modified a bit to deal with negative numbers.  One possibility
is to allocate separate "exponent" spaces for positive and negative numbers.
E.g., for positive numbers, the exponents are:

...     -4 = NNNNT   -3 = NNNT   -2 = NNT   -1 = NT
0 = T    1 = ZT       2 = ZZT     3 = ZZZT   4 = ZZZZT

For negative numbers, the exponents are:

...     -4 = MMMMG   -3 = MMMG   -2 = MMG   -1 = MG
0 = G    1 = AG       2 = AAG     3 = AAAG   4 = AAAAG

Also, for negative numbers, the digits should be in (9's) complement form.
Thus -1 would be AG8.  A special notation, e.g. NA, is required for zero.

This can of course be done somewhat better.  A higher radix can be used, and
the exponent encoding can be further optimized.  But the point is to describe
the approach, not to work out all the details.

Frank Adams                           ihnp4!philabs!pwa-b!mmintl!franka
Multimate International    52 Oakland Ave North    E. Hartford, CT 06108