Re: Representation of integers

Discussion in 'C Programming' started by Shao Miller, Jan 17, 2013.

  1. Shao Miller

    Shao Miller Guest

    On Sep 16 2003, 8:55 am, Chuck Falconer ("CBFalconer") wrote:
    > "Kevin D. Quitt" wrote:
    >> Jack Klein <> wrote:

    >
    >> > 1 For unsigned integer types other than unsigned char, the bits
    >> > of the object representation shall be divided into two groups:
    >> > value bits and padding bits (there need not be any of the
    >> > latter). If there are N value bits, each bit shall represent a
    >> > different power of 2 between 1 and 2N-1, so that objects of
    >> > that type shall be capable of representing values from 0 to 2N
    >> > - 1 using a pure binary representation; this shall be known as
    >> > the value representation. The values of any padding bits are
    >> > unspecified.

    >
    >> Damn - there goes my hope to port C99 to my ternary computer.

    >
    > No, you can do it. You may have to restrict the actual trits you
    > use. The problem is similar to implementing BCD arithmetic on
    > hexadecimal units. :) For example excess 3 encoding will use
    > the hex values 3 through 0x0c only, and others will be trap
    > values.
    >
    > You may lose some efficiency though. :-[


    Is there nothing in the Standard that prevents you from using trits to
    emulate bits?

    --
    - Shao Miller
    --
    "Thank you for the kind words; those are the kind of words I like to hear.

    Cheerily," -- Richard Harter
     
    Shao Miller, Jan 17, 2013
    #1
    1. Advertising

  2. Shao Miller

    Shao Miller Guest

    On 1/16/2013 19:53, Robert Wessel wrote:
    > On Wed, 16 Jan 2013 19:41:40 -0500, Shao Miller
    > <> wrote:
    >
    >>
    >> On Sep 16 2003, 8:55 am, Chuck Falconer ("CBFalconer") wrote:
    >>> "Kevin D. Quitt" wrote:
    >>>> Jack Klein <> wrote:
    >>>
    >>>>> 1 For unsigned integer types other than unsigned char, the bits
    >>>>> of the object representation shall be divided into two groups:
    >>>>> value bits and padding bits (there need not be any of the
    >>>>> latter). If there are N value bits, each bit shall represent a
    >>>>> different power of 2 between 1 and 2N-1, so that objects of
    >>>>> that type shall be capable of representing values from 0 to 2N
    >>>>> - 1 using a pure binary representation; this shall be known as
    >>>>> the value representation. The values of any padding bits are
    >>>>> unspecified.
    >>>
    >>>> Damn - there goes my hope to port C99 to my ternary computer.
    >>>
    >>> No, you can do it. You may have to restrict the actual trits you
    >>> use. The problem is similar to implementing BCD arithmetic on
    >>> hexadecimal units. :) For example excess 3 encoding will use
    >>> the hex values 3 through 0x0c only, and others will be trap
    >>> values.
    >>>
    >>> You may lose some efficiency though. :-[

    >>
    >> Is there nothing in the Standard that prevents you from using trits to
    >> emulate bits?

    >
    >
    > No, emulate all you want, so long as the abstract machine appears to
    > be binary. So you might use six trits to emulate a C byte/char, and
    > some of the capacity will go wasted. Note that if you use six trits
    > to emulate a byte, you cannot then emulate a short with 11 trits (of
    > course you could do the reverse, emulate bytes by breaking a short in
    > half as needed).
    >


    Interesting!

    > And I don't think there's any prohibition against trinary FP, just the
    > integer stuff has to look binary (but you still have to allow your
    > floats to be accessed as chars - but they could be trinary).
    >


    I didn't grok this last paragraph. You're saying the FP could be
    represented "internally" with trinary, but reading the bytes would have
    to convert to some kind of binary form, right?

    --
    - Shao Miller
    --
    "Thank you for the kind words; those are the kind of words I like to hear.

    Cheerily," -- Richard Harter
     
    Shao Miller, Jan 17, 2013
    #2
    1. Advertising

  3. Shao Miller <> writes:
    > On Sep 16 2003, 8:55 am, Chuck Falconer ("CBFalconer") wrote:

    [...]
    >> No, you can do it. You may have to restrict the actual trits you
    >> use. The problem is similar to implementing BCD arithmetic on
    >> hexadecimal units. :) For example excess 3 encoding will use
    >> the hex values 3 through 0x0c only, and others will be trap
    >> values.
    >>
    >> You may lose some efficiency though. :-[

    >
    > Is there nothing in the Standard that prevents you from using trits to
    > emulate bits?


    Did you notice that you're replying to an article that's nearly 10 years
    old? (The poster was a former regular here who has since passed away.)

    This isn't a criticism, BTW, it's just a little odd.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    Working, but not speaking, for JetHead Development, Inc.
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
     
    Keith Thompson, Jan 17, 2013
    #3
  4. Keith Thompson <> wrote:

    (snip)
    >> Is there nothing in the Standard that prevents you from using trits to
    >> emulate bits?


    > Did you notice that you're replying to an article that's nearly 10 years
    > old? (The poster was a former regular here who has since passed away.)


    > This isn't a criticism, BTW, it's just a little odd.


    I have had my news reader forget which posts it had read, and start
    getting old ones. Once in a while, I reply to one before noticing.

    -- glen
     
    glen herrmannsfeldt, Jan 17, 2013
    #4
  5. Shao Miller

    Shao Miller Guest

    On 1/16/2013 22:16, Keith Thompson wrote:
    > Shao Miller <> writes:
    >> On Sep 16 2003, 8:55 am, Chuck Falconer ("CBFalconer") wrote:

    > [...]
    >>> No, you can do it. You may have to restrict the actual trits you
    >>> use. The problem is similar to implementing BCD arithmetic on
    >>> hexadecimal units. :) For example excess 3 encoding will use
    >>> the hex values 3 through 0x0c only, and others will be trap
    >>> values.
    >>>
    >>> You may lose some efficiency though. :-[

    >>
    >> Is there nothing in the Standard that prevents you from using trits to
    >> emulate bits?

    >
    > Did you notice that you're replying to an article that's nearly 10 years
    > old? (The poster was a former regular here who has since passed away.)
    >
    > This isn't a criticism, BTW, it's just a little odd.
    >


    Oh. Yes, I had noticed. The name rung a bell, but I'm sorry to read
    that. Thanks for letting me know. I thought maybe a long-term reader
    might remember that particular discussion and remember relevant,
    subsequent discussion, too. (Glen Herrmannsfeldt was involved in this
    discussion, for example.)

    --
    - Shao Miller
    --
    "Thank you for the kind words; those are the kind of words I like to hear.

    Cheerily," -- Richard Harter
     
    Shao Miller, Jan 17, 2013
    #5
  6. Shao Miller

    Shao Miller Guest

    On 1/17/2013 00:22, Robert Wessel wrote:
    > On Wed, 16 Jan 2013 20:11:21 -0500, Shao Miller
    > <> wrote:
    >
    >> On 1/16/2013 19:53, Robert Wessel wrote:
    >>> On Wed, 16 Jan 2013 19:41:40 -0500, Shao Miller
    >>> <> wrote:
    >>>
    >>>>
    >>>> On Sep 16 2003, 8:55 am, Chuck Falconer ("CBFalconer") wrote:
    >>>>> "Kevin D. Quitt" wrote:
    >>>>>> Jack Klein <> wrote:
    >>>>>
    >>>>>>> 1 For unsigned integer types other than unsigned char, the bits
    >>>>>>> of the object representation shall be divided into two groups:
    >>>>>>> value bits and padding bits (there need not be any of the
    >>>>>>> latter). If there are N value bits, each bit shall represent a
    >>>>>>> different power of 2 between 1 and 2N-1, so that objects of
    >>>>>>> that type shall be capable of representing values from 0 to 2N
    >>>>>>> - 1 using a pure binary representation; this shall be known as
    >>>>>>> the value representation. The values of any padding bits are
    >>>>>>> unspecified.
    >>>>>
    >>>>>> Damn - there goes my hope to port C99 to my ternary computer.
    >>>>>
    >>>>> No, you can do it. You may have to restrict the actual trits you
    >>>>> use. The problem is similar to implementing BCD arithmetic on
    >>>>> hexadecimal units. :) For example excess 3 encoding will use
    >>>>> the hex values 3 through 0x0c only, and others will be trap
    >>>>> values.
    >>>>>
    >>>>> You may lose some efficiency though. :-[
    >>>>
    >>>> Is there nothing in the Standard that prevents you from using trits to
    >>>> emulate bits?
    >>>
    >>>
    >>> No, emulate all you want, so long as the abstract machine appears to
    >>> be binary. So you might use six trits to emulate a C byte/char, and
    >>> some of the capacity will go wasted. Note that if you use six trits
    >>> to emulate a byte, you cannot then emulate a short with 11 trits (of
    >>> course you could do the reverse, emulate bytes by breaking a short in
    >>> half as needed).
    >>>

    >>
    >> Interesting!
    >>
    >>> And I don't think there's any prohibition against trinary FP, just the
    >>> integer stuff has to look binary (but you still have to allow your
    >>> floats to be accessed as chars - but they could be trinary).
    >>>

    >>
    >> I didn't grok this last paragraph. You're saying the FP could be
    >> represented "internally" with trinary, but reading the bytes would have
    >> to convert to some kind of binary form, right?

    >
    > It would still need to have a binary representation when accessed as
    > chars, but it doesn't have to be a binary FP number. Base-16 or
    > base-10 or for that matter base-3 would be fine.
    >


    Ok, I think I understand what you mean by "binary FP number".

    Suppose the emulation was quite wasteful and that using the trit value 2
    (for {0, 1, 2}-style ternary) rarely appeared. Suppose the trits of an
    uninitialized 'unsigned char' object were all 2s. What might you call
    such a representation? It doesn't represent a valid 'unsigned char'
    value, which is represented by a pure binary notation[6.2.6.1p3]. It
    probably shouldn't be considered an object representation, because that
    definition doesn't seem to apply to an 'unsigned char'[6.2.6.1p4] ("any
    other object type").

    "3.5
    1 bit
    unit of data storage in the execution environment large enough to
    hold an object that may have one of two values"

    Would a trit qualify as a "bit", given this definition of the latter?

    --
    - Shao Miller
    --
    "Thank you for the kind words; those are the kind of words I like to hear.

    Cheerily," -- Richard Harter
     
    Shao Miller, Jan 17, 2013
    #6
  7. Shao Miller <> wrote:

    (snip, someone wrote)

    >>>> No, emulate all you want, so long as the abstract machine appears to
    >>>> be binary. So you might use six trits to emulate a C byte/char, and
    >>>> some of the capacity will go wasted. Note that if you use six trits
    >>>> to emulate a byte, you cannot then emulate a short with 11 trits (of
    >>>> course you could do the reverse, emulate bytes by breaking a short in
    >>>> half as needed).


    As I understand it, unsigned arithmetic has to be modulo some power of
    two. I believe that this requirement wasn't in K&R C, but was added with
    ANSI C89. Also, positive values of signed integers have to have the same
    representation as that value in the unsigned representation.

    Seems to me that every operation on a non-binary unsigned integer value
    has to be followed by the appropriate modulo operation to follow the
    standard. Either you have to restrict signed values to a smaller
    (than half) the range, or do a similar modulo operation on them.

    >>> I didn't grok this last paragraph. You're saying the FP could be
    >>> represented "internally" with trinary, but reading the bytes would have
    >>> to convert to some kind of binary form, right?


    >> It would still need to have a binary representation when accessed as
    >> chars, but it doesn't have to be a binary FP number. Base-16 or
    >> base-10 or for that matter base-3 would be fine.


    > Ok, I think I understand what you mean by "binary FP number".


    In the case of floating point, binary means that the exponent is
    considered to be an exponent of the base 2. That can be true even
    if the representation isn't binary, or vice versa. IBM starting with
    S/360 has used a base 16 floating point format, more recently added
    IEEE to ESA/390, and even more recently a very efficient coding for
    decimal floating point. All three have a binary representation, but
    the meaning of the individual bits is different. The decimal floating
    point forms are now part of the IEEE standard.

    > Suppose the emulation was quite wasteful and that using the trit value 2
    > (for {0, 1, 2}-style ternary) rarely appeared. Suppose the trits of an
    > uninitialized 'unsigned char' object were all 2s. What might you call
    > such a representation? It doesn't represent a valid 'unsigned char'
    > value, which is represented by a pure binary notation[6.2.6.1p3]. It
    > probably shouldn't be considered an object representation, because that
    > definition doesn't seem to apply to an 'unsigned char'[6.2.6.1p4] ("any
    > other object type").


    Yes, things get complicated at that point.

    -- glen
     
    glen herrmannsfeldt, Jan 18, 2013
    #7
  8. glen herrmannsfeldt <> writes:
    <snip>
    > As I understand it, unsigned arithmetic has to be modulo some power of
    > two. I believe that this requirement wasn't in K&R C, but was added with
    > ANSI C89.


    No, it was there in K&R C (and it was explicitly modulo 2^wordsize).
    Very early did not even have unsigned types, so the question is moot.

    <snip>
    --
    Ben.
     
    Ben Bacarisse, Jan 18, 2013
    #8
  9. Ben Bacarisse <> wrote:
    > glen herrmannsfeldt <> writes:
    > <snip>
    >> As I understand it, unsigned arithmetic has to be modulo some power of
    >> two. I believe that this requirement wasn't in K&R C, but was added with
    >> ANSI C89.


    > No, it was there in K&R C (and it was explicitly modulo 2^wordsize).
    > Very early did not even have unsigned types, so the question is moot.


    I can't find my K&R1 right now, but I thought it allowed for
    signed decimal, at least.

    That is much easier if you either remove the modulo 2^wordsize
    requirement or the requirement that the positive signed
    integers have the same representation as the unsigned integers
    with the same value.

    -- glen
     
    glen herrmannsfeldt, Jan 18, 2013
    #9
  10. glen herrmannsfeldt <> writes:

    > Ben Bacarisse <> wrote:
    >> glen herrmannsfeldt <> writes:
    >> <snip>
    >>> As I understand it, unsigned arithmetic has to be modulo some power of
    >>> two. I believe that this requirement wasn't in K&R C, but was added with
    >>> ANSI C89.

    >
    >> No, it was there in K&R C (and it was explicitly modulo 2^wordsize).
    >> Very early did not even have unsigned types, so the question is moot.

    >
    > I can't find my K&R1 right now, but I thought it allowed for
    > signed decimal, at least.


    The wording about unsigned is on page 34:

    "unsigned numbers obey the laws of arithmetic modulo 2^n, where n is
    the number of bits in an int..."

    This does not disallow decimal ints but it makes it seem unlikely that
    there were being considered. The wording could, very easily, have
    avoided referring to the number of bits in a (signed) int.

    > That is much easier if you either remove the modulo 2^wordsize
    > requirement or the requirement that the positive signed
    > integers have the same representation as the unsigned integers
    > with the same value.


    I don't think it's ruled out, but there's other evidence that it was not
    being consider in any serious way. For example, K&R C has no prototypes
    and no way to write an unsigned integer, so you'd have to write
    f((unsigned)42) to avoid passing a decimal int. I think if K&R had been
    seriously considering signed and unsigned ints that don't share the same
    representation for shared values, I think there would have been a
    notation for an unsigned constant.

    And what is "the number if bits" in a signed decimal int? Taken
    literally, it would be very hard or impossible to write certain unsigned
    values since there might be no int value what would convert to the
    required unsigned value. It would be a mess!

    --
    Ben.
     
    Ben Bacarisse, Jan 18, 2013
    #10
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Mantorok Redgormor

    Representation of integers

    Mantorok Redgormor, Sep 13, 2003, in forum: C Programming
    Replies:
    10
    Views:
    637
    Kevin D. Quitt
    Sep 17, 2003
  2. Mantorok Redgormor

    displaying underlying representation of integers

    Mantorok Redgormor, Sep 26, 2003, in forum: C Programming
    Replies:
    5
    Views:
    360
  3. Mantorok Redgormor

    representation of integers(again) very annoying..

    Mantorok Redgormor, Oct 13, 2003, in forum: C Programming
    Replies:
    4
    Views:
    469
    Barry Schwarz
    Oct 14, 2003
  4. =?iso-8859-9?Q?Tongu=E7?= Yumruk

    Bitmask representation of integers

    =?iso-8859-9?Q?Tongu=E7?= Yumruk, Oct 8, 2003, in forum: Python
    Replies:
    3
    Views:
    887
    Scott David Daniels
    Oct 8, 2003
  5. Guest
    Replies:
    3
    Views:
    382
    Cameron Laird
    Sep 9, 2004
Loading...

Share This Page