Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #38453 > unrolled thread

Writing SM/REM and FM/MOD

Back to article view | Back to comp.lang.forth

Contents

  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

Page 1 of 2  [1] 2  Next page →

#38453 — Writing SM/REM and FM/MOD

Hello clf,

I have about a week's worth of spare-time learning of ARM assembly under my
belt.  You can see some of the fruits of that at

http://minimaltype.com/13.txt
http://minimaltype.com/innerloops.txt

(13 preceded by 1.S, 2.S, 3.S, and so on, starting from hello world.)

Once I got to the level of 13.S, I started converting AvdH's yourforth from x86
to ARM.  For the most part, despite my knowing almost nothing at all about x86
assembler, this has been a real pleasure.  ARM assembler is really a joy to
work with, or at least I think so now after bashing my head against a few walls
early on.  Especially ARM's stack words and conditional instructions are very
clean and flexible.  The conversion to ARM assembly was also proceeding at a
pretty quick pace... until I hit the first word requiring division.

Which brings me to the subject of this post.

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?  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.

Can someone clearly describe, or point me to a clear description, as to how one
*implements* floored division vs. symmetric division?  Suppose I start out by
discarding signs and just repeatedly subtract numbers until I get a positive
quotient and remainder.  What do i then do to satisfy callers expecting foored
or symmetric division?  This has proven to be remarkably difficult to search
for.  Wikipedia literally just says that things "break down" when negative
numbers are involved.  yourforth just uses x86's idiv instruction.  An ARM
jonesforth that I've found has a division routine, but out of excessive
unconcern for ANS compatibility it doesn't identify what kind of a routine it
is.

I'm aware that this manner of division is going to be dreadfully slow.  For
known divisors I'll have a way to perform the division with multipication,
Otherwise this is fine for now.

And I feel compelled to add.. I'm not writing a Forth.  I'm porting a Forth.
Starting with yourforth as it's small and commented well enough to make up for
my not knowing x86.  I'm using gas as there's a convenient package of gcc for
Android, and as fasm doesn't seem to actually have arm binaries.


Thanks,
-- Julian

[toc] | [next] | [standalone]

#38456

Hi Julian

Have a look here: http://turboforth.net/source/Bank0/0-03-Math.html

Scroll down about 4 fifths towards the bottom. There you will find my floored division routine. It's written in TMS9900 assembler and heavily commented. Should suit you just fine. The TMS9900 does not have signed math so I have to set flags to remember the signs, perform an unsigned division then convert according to the signs. The 9900 has a DIV instruction which the ARM doesn't have so you'll need a little subroutine for that. Other than that it should be very easy to convert. 

Shout if anything doesn't make sense!

Regards

Mark

[toc] | [prev] | [next] | [standalone]

#38457

The ABS (absolute value) instruction possibly needs a little explanation, otherwise the code looks wrong.  ABS forces a value positive,  but sets <0 flag in the status register according to the sign of the value before the ABS instruction is executed.

[toc] | [prev] | [next] | [standalone]

#38479

Mark Wills wrote:

I dunno if that's what's needed here, but this is 4tH's implementation:

: 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
;

Hans Bezemer

[toc] | [prev] | [next] | [standalone]

#38481

Hans Bezemer <the.beez.speaks@gmail.com> writes:
> I dunno if that's what's needed here, but this is 4tH's implementation:
>
> : 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
> ;

For extra credit, implement UM/MOD in terms of U/MOD (single precision).

[toc] | [prev] | [next] | [standalone]

#38487

Lars Brinkhoff <lars.spam@nocrew.org> writes:
>For extra credit, implement UM/MOD in terms of U/MOD (single precision).

There are multiple ways to implement UM/MOD if you don't have an
instruction for it, depending on which instructions you have.  I
looked at that some time ago when we reimplemented division for Gforth
(for speed), and eventually settled for a restoring shift-and-subtract
algorithm for Alpha, and 1300+ lines of impenetrable C code (taken
from gcc) for other targets.  The shift-and-subtract algorithm may
also be faster for other targets without division instructions, like
ARM.

So your extra task is not a simple one.

- 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/

[toc] | [prev] | [next] | [standalone]

#38502

On Wednesday, April 22, 2015 at 3:51:02 AM UTC-7, Anton Ertl wrote:
> 
> There are multiple ways to implement UM/MOD if you don't have an
> instruction for it, depending on which instructions you have.  I
> looked at that some time ago when we reimplemented division for Gforth
> (for speed), and eventually settled for a restoring shift-and-subtract
> algorithm for Alpha, and 1300+ lines of impenetrable C code (taken
> from gcc) for other targets.  The shift-and-subtract algorithm may
> also be faster for other targets without division instructions, like
> ARM.
> 

This is so strange ... I was just participating in a similar discussion,
  but deep in the woods of retro-land:

http://forum.6502.org/viewtopic.php?f=9&t=1652&p=37734#p37060

I still feel far more comfortable there, but I'm working hard to try
  to become a more productive participant here, rather than a random
  sniper.

[toc] | [prev] | [next] | [standalone]

#38489

Lars Brinkhoff wrote:
> For extra credit, implement UM/MOD in terms of U/MOD (single precision).
I dunno U/MOD. Will this do?

0 constant u>d

: d2*+                                 ( ud n -- ud+n c )
  over highbit and >r >r 2dup d+ r> u>d d+ r>
;

: um/mod                               ( ud u1 -- u2 u3 )
  0 swap CELL-BITS 1+ 0
  do >r over r@ u< 0= or if r@ - 1 else 0 then d2*+ r> loop
  drop swap 1 rshift or swap
;

Gotta do your own thing for HIGHBIT and CELL-BITS. sorry.

Hans Bezemer

[toc] | [prev] | [next] | [standalone]

#38493

Hans Bezemer <the.beez.speaks@gmail.com> writes:
> 0 constant u>d
>
> : d2*+                                 ( ud n -- ud+n c )
>   over highbit and >r >r 2dup d+ r> u>d d+ r>
> ;
>
> : um/mod                               ( ud u1 -- u2 u3 )
>   0 swap CELL-BITS 1+ 0
>   do >r over r@ u< 0= or if r@ - 1 else 0 then d2*+ r> loop
>   drop swap 1 rshift or swap
> ;

Thanks, that's helpful!

[toc] | [prev] | [next] | [standalone]

#38689

On Tuesday, April 21, 2015 at 4:45:13 PM UTC-4, Mark Wills wrote:
> Hi Julian
> 
> Have a look here: http://turboforth.net/source/Bank0/0-03-Math.html
> 
> Scroll down about 4 fifths towards the bottom. There you will find my floored division routine. It's written in TMS9900 assembler and heavily commented. Should suit you just fine. The TMS9900 does not have signed math so I have to set flags to remember the signs, perform an unsigned division then convert according to the signs. The 9900 has a DIV instruction which the ARM doesn't have so you'll need a little subroutine for that. Other than that it should be very easy to convert. 
> 
> Shout if anything doesn't make sense!
> 
> Regards
> 
> Mark


Mark,

Those are nice looking code pages.  What did you use to write the HTML?

BF

[toc] | [prev] | [next] | [standalone]

#38691

On Tuesday, 28 April 2015 14:44:08 UTC+1, foxaudio...@gmail.com  wrote:
> On Tuesday, April 21, 2015 at 4:45:13 PM UTC-4, Mark Wills wrote:
> > Hi Julian
> > 
> > Have a look here: http://turboforth.net/source/Bank0/0-03-Math.html
> > 
> > Scroll down about 4 fifths towards the bottom. There you will find my floored division routine. It's written in TMS9900 assembler and heavily commented. Should suit you just fine. The TMS9900 does not have signed math so I have to set flags to remember the signs, perform an unsigned division then convert according to the signs. The 9900 has a DIV instruction which the ARM doesn't have so you'll need a little subroutine for that. Other than that it should be very easy to convert. 
> > 
> > Shout if anything doesn't make sense!
> > 
> > Regards
> > 
> > Mark
> 
> 
> Mark,
> 
> Those are nice looking code pages.  What did you use to write the HTML?
> 
> BF

Hi. It's a hand-written vb.net program that I wrote about 5 or 6 years
ago!

[toc] | [prev] | [next] | [standalone]

#38460

On Tue, 21 Apr 2015 13:23:08 -0700 (PDT), Julian Fondren
<julian.fondren@gmail.com> wrote:

>Can someone clearly describe, or point me to a clear description, as to how one
>*implements* floored division vs. symmetric division?  Suppose I start out by
>discarding signs and just repeatedly subtract numbers until I get a positive
>quotient and remainder.

See the "ARM System Developers Guide" by Sloss, Symes and Wright.

You also need to decide which of the many ARM instruction sets you
are talking about. Dealing with Cortex Ax is not the same as dealing
with Cortex-Mx or ARM7/9/11.

Stephen

-- 
Stephen Pelc, stephenXXX@mpeforth.com
MicroProcessor Engineering Ltd - More Real, Less Time
133 Hill Lane, Southampton SO15 5AF, England
tel: +44 (0)23 8063 1441, fax: +44 (0)23 8033 9691
web: http://www.mpeforth.com - free VFX Forth downloads

[toc] | [prev] | [next] | [standalone]

#38462

On Tue, 21 Apr 2015 16:23:08 -0400, Julian Fondren  
<julian.fondren@gmail.com> wrote:

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


"Google is your friend."

These links were all on the first page of results.
The first three go into some detail.  The last is a quick summary.

"Symmetric division considered harmful"  (for Forth-83)
http://www.nimblemachines.com/symmetric-division-considered-harmful/

"Excerpts from Forth Programmer's Handbook #2"
http://www.computer-solutions.co.uk/chipdev/fph-2.htm

"Signed Integer Division" (kForth)
http://ccreweb.org/software/kforth/kforth5.html

"Division" (ANSForth)
http://www.forth.org/ansforth/node5.html


Sigh, I need to read those too ...


Rod Pemberton

-- 
Cars kill more people than guns in the U.S.
Yet, no one is trying to take away your car.

[toc] | [prev] | [next] | [standalone]

#38465

On Tuesday, April 21, 2015 at 3:45:13 PM UTC-5, Mark Wills wrote:
> Hi Julian
> 
> Have a look here: http://turboforth.net/source/Bank0/0-03-Math.html

Cool, that's remarkably easy to read.


On Tuesday, April 21, 2015 at 4:44:18 PM UTC-5, Stephen Pelc wrote:
> See the "ARM System Developers Guide" by Sloss, Symes and Wright.

Thanks, this looks be generally useful, and especially useful when I want
better division, but of signed division it just says "discard the signs and
then use these rules to put them back".  Why those rules?  It's oblivious to
the symmetric/floored controversy.


On Tuesday, April 21, 2015 at 5:32:15 PM UTC-5, Rod Pemberton wrote:
> "Google is your friend."

Bah.

> "Signed Integer Division" (kForth)
> http://ccreweb.org/software/kforth/kforth5.html
...
> Sigh, I need to read those too ...

Thanks, this one was useful, both for its remarks and for the link.
Which is broken, but which can be found at:

http://research.microsoft.com/pubs/151917/divmodnote.pdf

It contains some C code that uses symmetric division operators to produce a
floored result.


I guess what I'll do now is: A) write some kind of division routine. B)
determine whether what I've done is symmetric or floored, then C) name it
appropriately, and write another routine that fudges the results.  It'd be nice
if I could set out with the intention of doing it one way or the other;
hopefully when I'm done I'll be able provide others with the exact answer that
I was looking for.


Cheers,
-- Julian

[toc] | [prev] | [next] | [standalone]

#38473

Here's one more implementation, for ppc, which includes signed,
symmetric division.  The commentary tries to be clear about the
algorithms -- don't know how well it succeeds.

http://www.umich.edu/~williams/archive/forth/kforth/index.html

-- David

[toc] | [prev] | [next] | [standalone]

#38474

On 4/21/15 11:05 PM, David N. Williams wrote:
> Here's one more implementation, for ppc, which includes signed,
> symmetric division.  The commentary tries to be clear about the
> algorithms -- don't know how well it succeeds.
>
> http://www.umich.edu/~williams/archive/forth/kforth/index.html

Oops, here's the actual link:

http://www.umich.edu/~williams/archive/forth/kforth/div.s

-- David

[toc] | [prev] | [next] | [standalone]

#38521

On Tuesday, April 21, 2015 at 6:28:18 PM UTC-5, Julian Fondren wrote:
...
> On Tuesday, April 21, 2015 at 5:32:15 PM UTC-5, Rod Pemberton wrote:
> > "Google is your friend."
...
> 
> > "Signed Integer Division" (kForth)
> > http://ccreweb.org/software/kforth/kforth5.html
> ...
> 
> Thanks, this one was useful, both for its remarks and for the link.
> Which is broken, but which can be found at:
> 
> http://research.microsoft.com/pubs/151917/divmodnote.pdf
> ...

Thanks. The link has been updated now.

Krishna

[toc] | [prev] | [next] | [standalone]

#38469

In article <8a492bc8-9c9e-465b-95e4-7d9b986ff583@googlegroups.com>,
Julian Fondren  <julian.fondren@gmail.com> wrote:
>Hello clf,
>
>I have about a week's worth of spare-time learning of ARM assembly under my
>belt.  You can see some of the fruits of that at
>
>http://minimaltype.com/13.txt
>http://minimaltype.com/innerloops.txt
>
>(13 preceded by 1.S, 2.S, 3.S, and so on, starting from hello world.)
>
>Once I got to the level of 13.S, I started converting AvdH's yourforth from x86
>to ARM.  For the most part, despite my knowing almost nothing at all about x86
>assembler, this has been a real pleasure.  ARM assembler is really a joy to
>work with, or at least I think so now after bashing my head against a few walls
>early on.  Especially ARM's stack words and conditional instructions are very
>clean and flexible.  The conversion to ARM assembly was also proceeding at a
>pretty quick pace... until I hit the first word requiring division.
>
>Which brings me to the subject of this post.
>
>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?  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.
>
>Can someone clearly describe, or point me to a clear description, as to how one
>*implements* floored division vs. symmetric division?  Suppose I start out by
>discarding signs and just repeatedly subtract numbers until I get a positive
>quotient and remainder.  What do i then do to satisfy callers expecting foored
>or symmetric division?  This has proven to be remarkably difficult to search
>for.  Wikipedia literally just says that things "break down" when negative
>numbers are involved.  yourforth just uses x86's idiv instruction.  An ARM
>jonesforth that I've found has a division routine, but out of excessive
>unconcern for ANS compatibility it doesn't identify what kind of a routine it
>is.

Frans van de Markt (Dutch Forth) hit the same snag with porting ciforth to
ARM. My advise was to look at examples from FIG listings and the DEC alpha
ciforth (DEC alpha has no hardware division either)
With that he solved it, but it was one of the hardest parts of the
port. (another one is the -c option, to generate executables.)
You could also get that ciforth from me, but that would take the fun out of
it.
I hope we can in the future compare things and copy each other best
tricks.

>
>I'm aware that this manner of division is going to be dreadfully slow.  For
>known divisors I'll have a way to perform the division with multipication,
>Otherwise this is fine for now.
>
>And I feel compelled to add.. I'm not writing a Forth.  I'm porting a Forth.
>Starting with yourforth as it's small and commented well enough to make up for
>my not knowing x86.  I'm using gas as there's a convenient package of gcc for
>Android, and as fasm doesn't seem to actually have arm binaries.

Nobody ever writes a Forth. The latest ciforth (soon) is in fact FIGforth
version 5.2. yourforth is the bastard child of ciforth and jonesforth.

>
>
>Thanks,
>-- Julian
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

[toc] | [prev] | [next] | [standalone]

#38495

albert@spenarnc.xs4all.nl (Albert van der Horst) writes:
>My advise was to look at examples from FIG listings and the DEC alpha
>ciforth (DEC alpha has no hardware division either)
>With that he solved it, but it was one of the hardest parts of the
>port. (another one is the -c option, to generate executables.)
>You could also get that ciforth from me, but that would take the fun out of
>it.
>I hope we can in the future compare things and copy each other best
>tricks.

Hmm, Gforth implemented sm/rem and fm/mod in terms of um/mod in 1996
<http://www.complang.tuwien.ac.at/cvsweb/cgi-bin/cvsweb/gforth/Attic/primitives?rev=1.53;content-type=text%2Fplain>.
Did you look at that and copy our tricks?

- 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/

[toc] | [prev] | [next] | [standalone]

#38499

Anton Ertl wrote:

http://www.complang.tuwien.ac.at/cvsweb/cgi-bin/cvsweb/gforth/Attic/primitives?rev=1.53;content-type=text%2Fplain

As far as double cell stack operations go:

: 2swap rot >r rot r> ;

Is probably more efficient than:

: 2swap >r -rot r> -rot ;

Since most systems define -ROT as "ROT ROT" (gforth doesn't - it's a
primitive).

Hence, 

: 2nip rot drop rot drop ;

Is probably more efficient than:

: 2nip 2swap 2drop ;

And finally, if your PICK or 2SWAP isn't too good, this /may/ be a slightly
better alternative:

: 2TUCK OVER >R ROT >R ROT OVER R> R> ROT ;

Hans Bezemer

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.lang.forth

csiph-web