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

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

Expand Messages
  • 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 1 of 9 , May 10, 2013
    • 0 Attachment
      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 2 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.