Re: Writing SM/REM and FM/MOD

From	anton@mips.complang.tuwien.ac.at (Anton Ertl)
Newsgroups	comp.lang.forth
Subject	Re: Writing SM/REM and FM/MOD
Date	2015-04-22 13:43 +0000
Organization	Institut fuer Computersprachen, Technische Universitaet Wien
Message-ID	<2015Apr22.154302@mips.complang.tuwien.ac.at> (permalink)
References	<8a492bc8-9c9e-465b-95e4-7d9b986ff583@googlegroups.com>

Show all headers | View raw

Julian Fondren <julian.fondren@gmail.com> writes:
>I can perform division with repeated subtraction (using subtract-with-carry to
>divide a 64-bit dividend by a 32-bit divisor), but what do I do about negative
>numbers?

: bla { d1 d2 -- }
  d1 s>d d2 fm/mod d1 . d2 . ." fm/mod quot=" . ."   mod=" .  5 spaces
  d1 s>d d2 sm/rem d1 . d2 . ." fm/rem quot=" . ."   rem=" . ;
 7  3 bla 
-7  3 bla 
 7 -3 bla 
-7 -3 bla 

outputs:

7 3 fm/mod quot=2   mod=1      7 3 fm/rem quot=2   rem=1  ok
-7 3 fm/mod quot=-3   mod=2      -7 3 fm/rem quot=-2   rem=-1  ok
7 -3 fm/mod quot=-3   mod=-2      7 -3 fm/rem quot=-2   rem=1  ok
-7 -3 fm/mod quot=2   mod=-1      -7 -3 fm/rem quot=2   rem=-1  ok

>  My education takes me as a far as, for ratios, "if they're both
>negative, that cancels out - they are now both positive; if one is negative,
>normalize the ratio so that only the numerator is negative; if the ratio is
>reduced [i.e., if division is performed], the result has the sign of the
>numerator."  Which doesn't cover the sign of the remainder, which is apaprently
>not the same thing as the modulus, which is apparently controversial.

You can just look it up in the standard:

http://www.forth200x.org/documents/html/usage.html#usage:div

>Can someone clearly describe, or point me to a clear description, as to how one
>*implements* floored division vs. symmetric division?

Both in C and in Forth from the Gforth sources:

From kernel/prim.fs in Gforth:

: fm/mod  ( d1 n1 -- n2 n3 )
 dup >r dup 0< IF  negate >r dnegate r>  THEN
 over       0< IF  tuck + swap  THEN
 um/mod
 r> 0< IF  swap negate swap  THEN ;

: sm/rem  ( d1 n1 -- n2 n3 )
 over >r dup >r abs -rot
 dabs rot um/mod
 r> r@ xor 0< IF       negate       THEN
 r>        0< IF  swap negate swap  THEN ;

Or if you prefer it in C, from engine/support.c:

DCell smdiv (DCell num, Cell denom)
     /* symmetric divide procedure, mixed prec */
{
  DCell res;
  UDCell ures;
  UCell l, q, r;
  Cell h;
  Cell denomsign=denom;

  vm_d2twoCell(num,l,h);
  if (h < 0)
    num = dnegate (num);
  if (denomsign < 0)
    denom = -denom;
  ures = umdiv(D2UD(num), denom);
  vm_ud2twoCell(ures,q,r);
  if ((h^denomsign)<0) {
    q = -q;
    if (((Cell)q) > 0) /* note: == 0 is possible */
      throw(BALL_RESULTRANGE);
  } else {
    if (((Cell)q) < 0)
      throw(BALL_RESULTRANGE);
  }
  if (h<0)
    r = -r;
  vm_twoCell2d(q,r,res);
  return res;
}

DCell fmdiv (DCell num, Cell denom)
     /* floored divide procedure, mixed prec */
{
  /* I have this technique from Andrew Haley */
  DCell res;
  UDCell ures;
  Cell denomsign=denom;
  Cell numsign;
  UCell q,r;

  if (denom < 0) {
    denom = -denom;
    num = dnegate(num);
  }
  numsign = DHI(num);
  if (numsign < 0)
    DHI_IS(num,DHI(num)+denom);
  ures = umdiv(D2UD(num),denom);
  vm_ud2twoCell(ures,q,r);
  if ((numsign^((Cell)q)) < 0)
    throw(BALL_RESULTRANGE);
  if (denomsign<0)
    r = -r;
  vm_twoCell2d(q,r,res);
  return res;
}

- anton
-- 
M. Anton Ertl  http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
     New standard: http://www.forth200x.org/forth200x.html
   EuroForth 2014: http://www.euroforth.org/ef14/

Back to comp.lang.forth | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

Writing SM/REM and FM/MOD Julian Fondren <julian.fondren@gmail.com> - 2015-04-21 13:23 -0700
  Writing SM/REM and FM/MOD Mark Wills <markwills1970@gmail.com> - 2015-04-21 13:45 -0700
    Writing SM/REM and FM/MOD Mark Wills <markwills1970@gmail.com> - 2015-04-21 13:54 -0700
    Re: Writing SM/REM and FM/MOD Hans Bezemer <the.beez.speaks@gmail.com> - 2015-04-22 11:49 +0200
      Re: Writing SM/REM and FM/MOD Lars Brinkhoff <lars.spam@nocrew.org> - 2015-04-22 12:09 +0200
        Re: Writing SM/REM and FM/MOD anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-04-22 10:37 +0000
          Re: Writing SM/REM and FM/MOD Michael Barry <barrym95838@yahoo.com> - 2015-04-22 08:19 -0700
        Re: Writing SM/REM and FM/MOD Hans Bezemer <the.beez.speaks@gmail.com> - 2015-04-22 13:25 +0200
          Re: Writing SM/REM and FM/MOD Lars Brinkhoff <lars.spam@nocrew.org> - 2015-04-22 14:42 +0200
    Re: Writing SM/REM and FM/MOD foxaudioresearch@gmail.com - 2015-04-28 06:44 -0700
      Re: Writing SM/REM and FM/MOD Mark Wills <markwills1970@gmail.com> - 2015-04-28 07:27 -0700
  Re: Writing SM/REM and FM/MOD stephen@mpeforth.com (Stephen Pelc) - 2015-04-21 21:44 +0000
  Re: Writing SM/REM and FM/MOD "Rod Pemberton" <bork@lllljunkqwer.cpm> - 2015-04-21 18:32 -0400
    Re: Writing SM/REM and FM/MOD Julian Fondren <julian.fondren@gmail.com> - 2015-04-21 16:28 -0700
      Re: Writing SM/REM and FM/MOD "David N. Williams" <williams@umich.edu> - 2015-04-21 23:05 -0400
        Re: Writing SM/REM and FM/MOD "David N. Williams" <williams@umich.edu> - 2015-04-21 23:07 -0400
      Re: Writing SM/REM and FM/MOD krishna.myneni@ccreweb.org - 2015-04-22 18:15 -0700
  Re: Writing SM/REM and FM/MOD albert@spenarnc.xs4all.nl (Albert van der Horst) - 2015-04-22 00:19 +0000
    Re: Writing SM/REM and FM/MOD anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-04-22 12:54 +0000
      Re: Writing SM/REM and FM/MOD Hans Bezemer <the.beez.speaks@gmail.com> - 2015-04-22 16:50 +0200
        Re: Writing SM/REM and FM/MOD anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-04-22 15:29 +0000
        Re: Writing SM/REM and FM/MOD "Rod Pemberton" <bork@lllljunkqwer.cpm> - 2015-04-24 21:46 -0400
          Re: Writing SM/REM and FM/MOD Michael Barry <barrym95838@yahoo.com> - 2015-04-27 22:08 -0700
            Re: Writing SM/REM and FM/MOD "Rod Pemberton" <bork@lllljunkqwer.cpm> - 2015-04-28 03:24 -0400
    Re: Writing SM/REM and FM/MOD Julian Fondren <ayrnieu@gmail.com> - 2015-05-11 16:38 -0700
      Re: Writing SM/REM and FM/MOD albert@spenarnc.xs4all.nl (Albert van der Horst) - 2015-05-12 00:24 +0000
      Re: Writing SM/REM and FM/MOD anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-05-12 13:58 +0000
  Re: Writing SM/REM and FM/MOD anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-04-22 13:43 +0000

csiph-web