Loading ...
Sorry, an error occurred while loading the content.
 

RE: [cosmacelf] Assembly language Challenge - Sign/Magnitude Compares - Clarification

Expand Messages
  • bill rowe
    Charles pointed out a couple of issues: there s a typo where i wrote rR8 instead of R8 and i used the term jlti4 to mean the 32 bit compare without explaining
    Message 1 of 9 , May 9, 2013
    Charles pointed out a couple of issues: there's a typo where i wrote rR8 instead of R8 and i used the term jlti4 to mean the 32 bit compare without explaining what I was doing.  

    I redid the code in the attachment actually duplicating the 32 bit compare so you can see the whole messy glory.  The .lst file was assembled with the excellent AS assembler by Alfred Arnold:



    To: cosmacelf@yahoogroups.com; bill_rowe_ottawa@...; bill.rowe.ottawa@...
    From: bill_rowe_ottawa@...
    Date: Thu, 9 May 2013 11:42:58 -0400
    Subject: [cosmacelf] Assembly language Challenge - Sign/Magnitude Compares [1 Attachment]

     
    [Attachment(s) from bill rowe included below]
    Floating point numbers are represented as sign+magnitude rather than the two's complement used for integers.  
    The details are a bit messy but basically, the 32 bits in a float are divided as S-EEEEEEEE-MMMMMMMMMMMMMMMMMMMMMMM 
    where S is the sign, 0 for positive, 1 for negative, EE...EE is an 8 bit exponent, and MM...MM is a 23 bit magnitude(see note 1) 

    One characteristic of this representation is that if one or both of the numbers is positive, you can do a standard 32 bit integer compare and trust the result.  If BOTH of the numbers are negative, you can still do an integer compare but you have to reverse the operands.  

    The assembly code for the 32 bit integer and float compares is below.  A float compare is almost 70 bytes total because of repeating the integer compare with the operands reversed.  The challenge is to reduce this. Execution time is less significant, you could use registers 14 or 15 if you needed them.  Bonus points if the reduction improves the 32 bit integer compare.  I already have special cases for equal/not equal and zero compares but if there any other special cases that would be good.  
    Sample positive and negative floats are one=0x3f800000, minus one is 0xbf800000.  You can see that the two are the same except for the sign bit and if you did a signed integer compare you'd get a correct result.

    (because outlook seems to mungle my email sometimes I've attached the code as well as including it in the email)
    To do a 32 bit integer compare for a jump-if-A-less-than-B, the code is about 28 bytes long(here A is in R8:R9 and B is in R10:R11

    ;signed comparison(less than) of two long integers - subtract R10:R11 from R8:R9 and jump if borrow 
    dec sp ;make a work area
    glo 11 ;lowest order byte
    str sp 
    glo 9
    sm
    ghi 11
    str sp
    ghi 9
    smb          ;that's a standard signed subtraction of one reg
    glo 10 ;lowest order byte of the top register
    str sp 
    glo 8
    smb
    ghi 10
    str sp
    ghi 8
    smb          ;that's a standard signed subtraction of a double register
    ghi 8 ;
    xor           ;sets the top bit if the signs are different
    inc sp ;release the work area
    shlc          ;the original df is now in bit 0 and df=1 if signs were different
    lsnf ;bypass the flip if signs were the same
    xri 01     ;invert original df if signs were different
    shrc           ;put it back in df
    LBNF label  ;execute 

    To do a float comparison, I have to check the signs before comparing and, if both are negative, reverse the operands.

    ;jump if float reg R8:R9< float reg R10:R11
    ghi rR8 ;see if first arg is -v
    shl
    lbnf $$comp ;if at least 1 reg positive, just compare
    ghi R10 ;check 2nd reg
    shl
    lbdf $$rcomp
    $$comp: jltI4 R8:R9,R10:R11,label ;as long as one register is +v
    lbr $$done
    $$rcomp: jltI4 R10:R11,R8:R9,label ;reverse the order of the operands
    $$done:

    (note 1) floats are "normalized" by shifting the magnitude left until bit 23 is 1 and adjusting the exponent then, since bit 23 is always 1, it's stripped off and used to hold one of the exponent bits.  The exponent is carried as excess 127 i.e. 2^0 is carried as 127 and 2^-1 is carried as 126.  See https://en.wikipedia.org/wiki/Floating_point#Internal_representation



  • Kevin
    When a number cannot be represented in floating point, it is called denormalized . Values having a magnitude too small to be represented (between the interval
    Message 2 of 9 , May 10, 2013
      When a number cannot be represented in floating point, it is called "denormalized". Values having a magnitude too small to be represented (between the interval -fmin and +fmin) are termed "subnormal". A calculation that results in a subnormal value is termed an "underflow".

      You have two easy options:

      1. Terminate the calculation with an underflow error.
      2. Use zero in place of the subnormal value (called "flush to zero") and set an "inexact" and "underflow" flag.

      A third, more complicated, option exists:

      3. Complicate your code to handle subnormal values and set an "inexact" and "underflow" flag. This is arguably not worth the effort as you have already lost precision, but allows both gradual underflow and gradual loss of precision.

      Similar options exists for overflow computations.


      --- In cosmacelf@yahoogroups.com, bill rowe <bill_rowe_ottawa@...> wrote:
      >
      > right. for purposes of the sign/magnitude compare though, this doesn't matter. There is a further complication with numbers that are too small to be normalized but I'm cheerfully ignoring them.
      >
      > To: cosmacelf@yahoogroups.com
      > From: old_computers@...
      > Date: Thu, 9 May 2013 19:44:26 -0500
      > Subject: Re: [cosmacelf] Assembly language Challenge - Sign/Magnitude Compares
      >
      >
      >
      >
      >
      >
      >
      >
      >
      >
      >
      >
      >
      >
      >
      >
      >
      >
      >
      >
      >
      >
      >
      >
      >
      >
      > On May 9, 2013, at 10:42 AM, bill rowe wrote:
      >
      >
      >
      > > (note 1) floats are "normalized" by shifting the magnitude left
      >
      > > until bit 23 is 1 and adjusting the exponent then, since bit 23 is
      >
      > > always 1, it's stripped off and used to hold one of the exponent
      >
      > > bits. The exponent is carried as excess 127 i.e. 2^0 is carried as
      >
      > > 127 and 2^-1 is carried as 1 26.
      >
      >
      >
      > So since the high-order bit of the mantissa is *always* one in a
      >
      > normalized floating point number, that one is *not* stored. The way
      >
      > I understand is that this meant the mantissa is virtually 24 bits
      >
      > worth with 8 bits for the exponent.
      >
      >
      >
      > ??????
      >
      >
      >
      > --
      >
      > +----------------------------------------+
      >
      > |.....Charles and Francis Richmond.......|
      >
      > |........................................|
      >
      > |..plano dot net at aquaporin4 dot com...|
      >
      > +----------------------------------------+
      >
    • Kevin
      When a number cannot be represented in floating point, it is called denormalized . Values having a magnitude too small to be represented (between the interval
      Message 3 of 9 , May 10, 2013
        When a number cannot be represented in floating point, it is called "denormalized". Values having a magnitude too small to be represented (between the interval -fmin and +fmin) are termed "subnormal". A calculation that results in a subnormal value is termed an "underflow".

        You have two easy options:

        1. Terminate the calculation with an underflow error.
        2. Use zero in place of the subnormal value (called "flush to zero") and set an "inexact" and "underflow" flag.

        A third, more complicated, option exists:

        3. Complicate your code to handle subnormal values and set an "inexact" and "underflow" flag. This is arguably not worth the effort as you have already lost precision, but allows both gradual underflow and gradual loss of precision.

        Similar options exists for overflow computations.


        --- In cosmacelf@yahoogroups.com, bill rowe <bill_rowe_ottawa@...> wrote:
        >
        > right. for purposes of the sign/magnitude compare though, this doesn't matter. There is a further complication with numbers that are too small to be normalized but I'm cheerfully ignoring them.
        >
        >
        > On May 9, 2013, at 10:42 AM, bill rowe wrote:
        > > (note 1) floats are "normalized" by shifting the magnitude left
        >
        > > until bit 23 is 1 and adjusting the exponent then, since bit 23 is
        >
        > > always 1, it's stripped off and used to hold one of the exponent
        >
        > > bits. The exponent is carried as excess 127 i.e. 2^0 is carried as
        >
        > > 127 and 2^-1 is carried as 1 26.
        >
        >
        >
        > So since the high-order bit of the mantissa is *always* one in a
        >
        > normalized floating point number, that one is *not* stored. The way
        >
        > I understand is that this meant the mantissa is virtually 24 bits
        >
        > worth with 8 bits for the exponent.
        >
        >
        >
        > ??????
      • bill rowe
        Thanks. I may try out the flush to zero if i can detect the case. I do have to do something because I suspect there are situations where the code would
        Message 4 of 9 , May 10, 2013
          Thanks.  I may try out the "flush to zero" if i can detect the case.  I do have to do something because I suspect there are situations where the code would actually loop trying to get a bit into position 23!


          To: cosmacelf@yahoogroups.com
          From: kriceslo@...
          Date: Fri, 10 May 2013 07:59:58 +0000
          Subject: [cosmacelf] Re: Assembly language Challenge - Sign/Magnitude Compares

           
          When a number cannot be represented in floating point, it is called "denormalized". Values having a magnitude too small to be represented (between the interval -fmin and +fmin) are termed "subnormal". A calculation that results in a subnormal value is termed an "underflow".

          You have two easy options:

          1. Terminate the calculation with an underflow error.
          2. Use zero in place of the subnormal value (called "flush to zero") and set an "inexact" and "underflow" flag.

          A third, more complicated, option exists:

          3. Complicate your code to handle subnormal values and set an "inexact" and "underflow" flag. This is arguably not worth the effort as you have already lost precision, but allows both gradual underflow and gradual loss of precision.

          Similar options exists for overflow computations.

          --- In cosmacelf@yahoogroups.com, bill rowe <bill_rowe_ottawa@...> wrote:
          >
          > right. for purposes of the sign/magnitude compare though, this doesn't matter. There is a further complication with numbers that are too small to be normalized but I'm cheerfully ignoring them.
          >
          > To: cosmacelf@yahoogroups.com
          > From: old_computers@...
          > Date: Thu, 9 May 2013 19:44:26 -0500
          > Subject: Re: [cosmacelf] Assembly language Challenge - Sign/Magnitude Compares
          >
          >
          >
          >
          >
          >
          >
          >
          >
          >
          >
          >
          >
          >
          >
          >
          >
          >
          >
          >
          >
          >
          >
          >
          >
          >
          > On May 9, 2013, at 10:42 AM, bill rowe wrote:
          >
          >
          >
          > > (note 1) floats are "normalized" by shifting the magnitude left
          >
          > > until bit 23 is 1 and adjusting the exponent then, since bit 23 is
          >
          > > always 1, it's stripped off and used to hold one of the exponent
          >
          > > bits. The exponent is carried as excess 127 i.e. 2^0 is carried as
          >
          > > 127 and 2^-1 is carried as 1 26.
          >
          >
          >
          > So since the high-order bit of the mantissa is *always* one in a
          >
          > normalized floating point number, that one is *not* stored. The way
          >
          > I understand is that this meant the mantissa is virtually 24 bits
          >
          > worth with 8 bits for the exponent.
          >
          >
          >
          > ??????
          >
          >
          >
          > --
          >
          > +----------------------------------------+
          >
          > |.....Charles and Francis Richmond.......|
          >
          > |........................................|
          >
          > |..plano dot net at aquaporin4 dot com...|
          >
          > +----------------------------------------+
          >


        • Charles Richmond
          There can also be problems when adding two floating point values which differ by a large amount. One value will have to be shifted until the exponents match,
          Message 5 of 9 , May 10, 2013
            There can also be problems when adding two floating point values
            which differ by a large amount. One value will have to be shifted
            until the exponents match, and then the mantissas added. Sometimes
            the smaller number shifts away *all* of its digits!!! So it becomes
            just adding in a zero.

            This is a reason for using double precision for the calculations, to
            give more digits in the mantissa.

            On May 10, 2013, at 4:34 AM, Kevin wrote:

            > When a number cannot be represented in floating point, it is called
            > "denormalized". Values having a magnitude too small to be
            > represented (between the interval -fmin and +fmin) are termed
            > "subnormal". A calculation that results in a subnormal value is
            > termed an "underflow".
            >
            > You have two easy options:
            >
            > 1. Terminate the calculation with an underflow error.
            > 2. Use zero in place of the subnormal value (called "flush to
            > zero") and set an "inexact" and "underflow" flag.
            >
            > A third, more complicated, option exists:
            >
            > 3. Complicate your code to handle subnormal values and set an
            > "inexact" and "underflow" flag. This is arguably not worth the
            > effort as you have already lost precision, but allows both gradual
            > underflow and gradual loss of precision.
            >
            > Similar options exists for overflow computations.
            >
            > --- In cosmacelf@yahoogroups.com, bill rowe <bill_rowe_ottawa@...>
            > wrote:
            > >
            > > right. for purposes of the sign/magnitude compare though, this
            > doesn't matter. There is a further complication with numbers that
            > are too small to be normalized but I'm cheerfully ignoring them.
            > >
            > >
            > > On May 9, 2013, at 10:42 AM, bill rowe wrote:
            > > > (note 1) floats are "normalized" by shifting the magnitude left
            > >
            > > > until bit 23 is 1 and adjusting the exponent then, since bit 23 is
            > >
            > > > always 1, it's stripped off and used to hold one of the exponent
            > >
            > > > bits. The exponent is carried as excess 127 i.e. 2^0 is carried as
            > >
            > > > 127 and 2^-1 is carried as 1 26.
            > >
            > >
            > >
            > > So since the high-order bit of the mantissa is *always* one in a
            > >
            > > normalized floating point number, that one is *not* stored. The way
            > >
            > > I understand is that this meant the mantissa is virtually 24 bits
            > >
            > > worth with 8 bits for the exponent.
            > >
            > >
            > >
            > > ??????
            >
            >
            > <!-- #ygrp-mkp { border: 1px solid #d8d8d8; font-family: Arial;
            > margin: 10px 0; padding: 0 10px; } #ygrp-mkp hr { border: 1px solid
            > #d8d8d8; } #ygrp-mkp #hd { color: #628c2a; font-size: 85%; font-
            > weight: 700; line-height: 122%; margin: 10px 0; } #ygrp-mkp #ads
            > { margin-bottom: 10px; } #ygrp-mkp .ad { padding: 0 0; } #ygrp-
            > mkp .ad p { margin: 0; } #ygrp-mkp .ad a { color: #0000ff; text-
            > decoration: none; } #ygrp-sponsor #ygrp-lc { font-family: Arial; }
            > #ygrp-sponsor #ygrp-lc #hd { margin: 10px 0px; font-weight: 700;
            > font-size: 78%; line-height: 122%; } #ygrp-sponsor #ygrp-lc .ad
            > { margin-bottom: 10px; padding: 0 0; } #actions { font-family:
            > Verdana; font-size: 11px; padding: 10px 0; } #activity { background-
            > color: #e0ecee; float: left; font-family: Verdana; font-size: 10px;
            > padding: 10px; } #activity span { font-weight: 700; } #activity
            > span:first-child { text-transform: uppercase; } #activity span a
            > { color: #5085b6; text-decoration: none; } #activity span span
            > { color: #ff7900; } #activity span .underline { text-decoration:
            > underline; } .attach { clear: both; display: table; font-family:
            > Arial; font-size: 12px; padding: 10px 0; width: 400px; } .attach
            > div a { text-decoration: none; } .attach img { border: none;
            > padding-right: 5px; } .attach label { display: block; margin-
            > bottom: 5px; } .attach label a { text-decoration: none; }
            > blockquote { margin: 0 0 0 4px; } .bold { font-family: Arial; font-
            > size: 13px; font-weight: 700; } .bold a { text-decoration: none; }
            > dd.last p a { font-family: Verdana; font-weight: 700; } dd.last p
            > span { margin-right: 10px; font-family: Verdana; font-weight:
            > 700; } dd.last p span.yshortcuts { margin-right: 0; } div.attach-
            > table div div a { text-decoration: none; } div.attach-table
            > { width: 400px; } div.file-title a, div.file-title a:active,
            > div.file-title a:hover, div.file-title a:visited { text-decoration:
            > none; } div.photo-title a, div.photo-title a:active, div.photo-
            > title a:hover, div.photo-title a:visited { text-decoration: none; }
            > div#ygrp-mlmsg #ygrp-msg p a span.yshortcuts { font-family:
            > Verdana; font-size: 10px; font-weight: normal; } .green { color:
            > #628c2a; } .MsoNormal { margin: 0 0 0 0; } o { font-size: 0; }
            > #photos div { float: left; width: 72px; } #photos div div { border:
            > 1px solid #666666; height: 62px; overflow: hidden; width: 62px; }
            > #photos div label { color: #666666; font-size: 10px; overflow:
            > hidden; text-align: center; white-space: nowrap; width: 64px; }
            > #reco-category { font-size: 77%; } #reco-desc { font-size:
            > 77%; } .replbq { margin: 4px; } #ygrp-actbar div a:first-child { /*
            > border-right: 0px solid #000;*/ margin-right: 2px; padding-right:
            > 5px; } #ygrp-mlmsg { font-size: 13px; font-family: Arial,
            > helvetica,clean, sans-serif; *font-size: small; *font: x-small; }
            > #ygrp-mlmsg table { font-size: inherit; font: 100%; } #ygrp-mlmsg
            > select, input, textarea { font: 99% Arial, Helvetica, clean, sans-
            > serif; } #ygrp-mlmsg pre, code { font:115% monospace; *font-size:
            > 100%; } #ygrp-mlmsg * { line-height: 1.22em; } #ygrp-mlmsg #logo
            > { padding-bottom: 10px; } #ygrp-msg p a { font-family: Verdana; }
            > #ygrp-msg p#attach-count span { color: #1E66AE; font-weight: 700; }
            > #ygrp-reco #reco-head { color: #ff7900; font-weight: 700; } #ygrp-
            > reco { margin-bottom: 20px; padding: 0px; } #ygrp-sponsor #ov li a
            > { font-size: 130%; text-decoration: none; } #ygrp-sponsor #ov li
            > { font-size: 77%; list-style-type: square; padding: 6px 0; } #ygrp-
            > sponsor #ov ul { margin: 0; padding: 0 0 0 8px; } #ygrp-text { font-
            > family: Georgia; } #ygrp-text p { margin: 0 0 1em 0; } #ygrp-text
            > tt { font-size: 120%; } #ygrp-vital ul li:last-child { border-
            > right: none !important; } -->

            --
            +----------------------------------------+
            |.....Charles and Francis Richmond.......|
            |........................................|
            |..plano dot net at aquaporin4 dot com...|
            +----------------------------------------+
          • bill rowe
            Ok, here is my 1st entry in the inaugural assembly language challenge. I ve attached the code rather than laying it out in the email. Both the float compare
            Message 6 of 9 , May 11, 2013
            Ok, here is my 1st entry in the inaugural assembly language challenge.  I've attached the code rather than laying it out in the email.

            Both the float compare and the underlying 32 bit integer subtractions behave differently depending on the signs of the operands.  It occurred to me that if the signs are different I don't have to actually do the compare because one is clearly less than the other!  I moved the sign tests all to the front of the code which let me take them out of the subtractions.

            The new routine is 59 bytes instead of 69 and, for random input, it should be noticeably quicker since the signs are checked early.  It has the effect of introducing some more branching around but there you go.

            I was thinking of some way of reversing the subtraction using the sd and sdb instructions but i haven't worked that through.

            To: cosmacelf@yahoogroups.com; bill.rowe.ottawa@...
            From: bill_rowe_ottawa@...
            Date: Thu, 9 May 2013 21:04:37 -0400
            Subject: RE: [cosmacelf] Assembly language Challenge - Sign/Magnitude Compares - Clarification [2 Attachments]

             
            [Attachment(s) from bill rowe included below]
            Charles pointed out a couple of issues: there's a typo where i wrote rR8 instead of R8 and i used the term jlti4 to mean the 32 bit compare without explaining what I was doing.  

            I redid the code in the attachment actually duplicating the 32 bit compare so you can see the whole messy glory.  The .lst file was assembled with the excellent AS assembler by Alfred Arnold:



            To: cosmacelf@yahoogroups.com; bill_rowe_ottawa@...; bill.rowe.ottawa@...
            From: bill_rowe_ottawa@...
            Date: Thu, 9 May 2013 11:42:58 -0400
            Subject: [cosmacelf] Assembly language Challenge - Sign/Magnitude Compares [1 Attachment]

             
            [Attachment(s) from bill rowe included below]
            Floating point numbers are represented as sign+magnitude rather than the two's complement used for integers.  
            The details are a bit messy but basically, the 32 bits in a float are divided as S-EEEEEEEE-MMMMMMMMMMMMMMMMMMMMMMM 
            where S is the sign, 0 for positive, 1 for negative, EE...EE is an 8 bit exponent, and MM...MM is a 23 bit magnitude(see note 1) 

            One characteristic of this representation is that if one or both of the numbers is positive, you can do a standard 32 bit integer compare and trust the result.  If BOTH of the numbers are negative, you can still do an integer compare but you have to reverse the operands.  

            The assembly code for the 32 bit integer and float compares is below.  A float compare is almost 70 bytes total because of repeating the integer compare with the operands reversed.  The challenge is to reduce this. Execution time is less significant, you could use registers 14 or 15 if you needed them.  Bonus points if the reduction improves the 32 bit integer compare.  I already have special cases for equal/not equal and zero compares but if there any other special cases that would be good.  
            Sample positive and negative floats are one=0x3f800000, minus one is 0xbf800000.  You can see that the two are the same except for the sign bit and if you did a signed integer compare you'd get a correct result.

            (because outlook seems to mungle my email sometimes I've attached the code as well as including it in the email)
            To do a 32 bit integer compare for a jump-if-A-less-than-B, the code is about 28 bytes long(here A is in R8:R9 and B is in R10:R11

            ;signed comparison(less than) of two long integers - subtract R10:R11 from R8:R9 and jump if borrow 
            dec sp ;make a work area
            glo 11 ;lowest order byte
            str sp 
            glo 9
            sm
            ghi 11
            str sp
            ghi 9
            smb          ;that's a standard signed subtraction of one reg
            glo 10 ;lowest order byte of the top register
            str sp 
            glo 8
            smb
            ghi 10
            str sp
            ghi 8
            smb          ;that's a standard signed subtraction of a double register
            ghi 8 ;
            xor           ;sets the top bit if the signs are different
            inc sp ;release the work area
            shlc          ;the original df is now in bit 0 and df=1 if signs were different
            lsnf ;bypass the flip if signs were the same
            xri 01     ;invert original df if signs were different
            shrc           ;put it back in df
            LBNF label  ;execute 

            To do a float comparison, I have to check the signs before comparing and, if both are negative, reverse the operands.

            ;jump if float reg R8:R9< float reg R10:R11
            ghi rR8 ;see if first arg is -v
            shl
            lbnf $$comp ;if at least 1 reg positive, just compare
            ghi R10 ;check 2nd reg
            shl
            lbdf $$rcomp
            $$comp: jltI4 R8:R9,R10:R11,label ;as long as one register is +v
            lbr $$done
            $$rcomp: jltI4 R10:R11,R8:R9,label ;reverse the order of the operands
            $$done:

            (note 1) floats are "normalized" by shifting the magnitude left until bit 23 is 1 and adjusting the exponent then, since bit 23 is always 1, it's stripped off and used to hold one of the exponent bits.  The exponent is carried as excess 127 i.e. 2^0 is carried as 127 and 2^-1 is carried as 126.  See https://en.wikipedia.org/wiki/Floating_point#Internal_representation




          Your message has been successfully submitted and would be delivered to recipients shortly.