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

Groups > comp.lang.forth > #46610

Re: division performance (was: The problem with implementation defined ...)

From anton@mips.complang.tuwien.ac.at (Anton Ertl)
Newsgroups comp.lang.forth
Subject Re: division performance (was: The problem with implementation defined ...)
Date 2016-04-09 13:43 +0000
Organization Institut fuer Computersprachen, Technische Universitaet Wien
Message-ID <2016Apr9.154319@mips.complang.tuwien.ac.at> (permalink)
References (7 earlier) <2016Apr5.131223@mips.complang.tuwien.ac.at> <ne1864$c9u$1@dont-email.me> <2016Apr6.120304@mips.complang.tuwien.ac.at> <ne9cp7$2gt$2@dont-email.me> <2016Apr9.121431@mips.complang.tuwien.ac.at>

Show all headers | View raw

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>>Yes, the main problem is the division by 1 and -1.  If you exclude that, 
>>it's just one cell, e.g. try this:
>>
>>: prepare/ ( n1 -- n2 )  0 1 rot fm/mod nip ;
>>: uprepare ( u1 -- u2 )  0 1 rot um/mod nip ;
>>: p/ ( n1 something -- n2 )  m* nip ;
>>: up/ ( u1 something -- u2 ) um* nip ;
>
>6 3 prepare/ p/ . \ outputs 1
>
>It's not that simple:-).

Unfortunately, it's quite a bit more complicated, as discussed by
several sources.

Let's consider the unsigned case and only divisor 3.  Your PREPARE/
gives $5555555555555555 as reciprocal.  As we can see, this is too
small, so let's try $5555555555555556 instead:

6 $5555555555555556 up/ . \ outputs 2

So that's ok in this case.  Let's see if it's always right.  The error
will be largest with the largest dividend that gives a rest of 2 (or
generally, divisor-1).  For the divisor 3 and 64 bits, that number
happens to be $fffffffffffffffe.

$fffffffffffffffe $5555555555555556 up/ hex. \ gives $5555555555555555
\ let's check the result:
$5555555555555555 3 * hex. \ gives $FFFFFFFFFFFFFFFF

So this simple UP/ is not good enough in general.  The two approaches
for fixing it are to use extra precision (a longer reciprocal, and
more right-shifting), or computing the remainder of the approximate
quotient, and correcting the error based on that.

Alverson's extra-precision way is to have a w+1-bit (w is the cell
width) reciprocal (representable in w bits, because the first bit is
always 1), with the shift being w+(number of bits in the divisor).
Instead, we could also use a 2w-bit reciprocal and a w*2w->3w
multiplication (of which we use the top word).  The latter seems
simpler to implement in software (and not slower on a machine with a
pipelined w*w->2w multiplier).

Terje Mathisen devised an algorithm (presented by Agner Fog), that
works with just a w-bit reciprocal, but requires different UP/ actions
for different divisors.  We could represent "something" as cell-wide
reciprocal, plus shift amount, plus the xt of the required action, and
UP/ would then just be EXECUTE.  This can also be made to work with
divisor 1.

I have also seen a reference to Hacker's Delight, and an addendum
<http://www.hackersdelight.org/divcMore.pdf> covers the case when the
high word of multiplication is not available, but the original part
apparently is only in the book, so I'll look at it on Monday, if I
remember to do so.

Sources: 

<http://homepage.cs.uiowa.edu/~jones/bcd/divide.html>
Fog: <http://www.agner.org/optimize/optimizing_assembly.pdf> (page 143 ff.)
Alverson: <http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.33.1710>

- 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 2015: http://www.rigwit.co.uk/EuroForth2015/

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

Thread

The problem with implementation defined behaviour. Albert van der Horst <albert@spenarnc.xs4all.nl> - 2016-03-29 14:39 +0000
  Re: The problem with implementation defined behaviour. anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-03-29 16:20 +0000
    Re: The problem with implementation defined behaviour. "Elizabeth D. Rather" <erather@forth.com> - 2016-03-29 09:16 -1000
      Re: The problem with implementation defined behaviour. Bernd Paysan <bernd.paysan@gmx.de> - 2016-03-30 00:06 +0000
        Re: The problem with implementation defined behaviour. mhx@iae.nl - 2016-03-29 22:09 -0700
          Re: The problem with implementation defined behaviour. "Elizabeth D. Rather" <erather@forth.com> - 2016-03-29 21:37 -1000
          Re: The problem with implementation defined behaviour. Paul Rubin <no.email@nospam.invalid> - 2016-03-30 00:48 -0700
            Re: The problem with implementation defined behaviour. Paul Rubin <no.email@nospam.invalid> - 2016-03-30 00:48 -0700
          Re: The problem with implementation defined behaviour. anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-03-30 07:59 +0000
            Re: The problem with implementation defined behaviour. mhx@iae.nl - 2016-03-30 10:16 -0700
              Re: The problem with implementation defined behaviour. Bernd Paysan <bernd.paysan@gmx.de> - 2016-03-30 23:43 +0000
                Re: The problem with implementation defined behaviour. mhx@iae.nl - 2016-03-31 06:01 -0700
                Re: The problem with implementation defined behaviour. Bernd Paysan <bernd.paysan@gmx.de> - 2016-04-01 21:36 +0000
                Re: The problem with implementation defined behaviour. mhx@iae.nl - 2016-04-01 14:57 -0700
                Re: The problem with implementation defined behaviour. Bernd Paysan <bernd.paysan@gmx.de> - 2016-04-01 21:59 +0000
                Re: The problem with implementation defined behaviour. mhx@iae.nl - 2016-04-02 00:51 -0700
                Re: The problem with implementation defined behaviour. anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-04-01 08:25 +0000
                Re: The problem with implementation defined behaviour. Bernd Paysan <bernd.paysan@gmx.de> - 2016-04-01 21:32 +0000
                division performance (was: The problem with implementation defined ...) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-04-05 11:12 +0000
                Re: division performance (was: The problem with implementation defined ...) Bernd Paysan <bernd.paysan@gmx.de> - 2016-04-05 20:45 +0000
                Re: division performance (was: The problem with implementation defined ...) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-04-06 10:03 +0000
                Re: division performance (was: The problem with implementation defined ...) Bernd Paysan <bernd.paysan@gmx.de> - 2016-04-08 22:53 +0000
                Re: division performance (was: The problem with implementation defined ...) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-04-09 10:14 +0000
                Re: division performance (was: The problem with implementation defined ...) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-04-09 13:43 +0000
              Re: The problem with implementation defined behaviour. anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-03-31 10:55 +0000
                Re: The problem with implementation defined behaviour. mhx@iae.nl - 2016-03-31 06:38 -0700
                Re: The problem with implementation defined behaviour. anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-03-31 16:21 +0000
                Re: The problem with implementation defined behaviour. Paul Rubin <no.email@nospam.invalid> - 2016-03-31 11:49 -0700
                Re: The problem with implementation defined behaviour. "Elizabeth D. Rather" <erather@forth.com> - 2016-03-31 10:11 -1000
                Re: The problem with implementation defined behaviour. mhx@iae.nl - 2016-04-01 03:53 -0700
                Re: The problem with implementation defined behaviour. anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-04-01 11:44 +0000
                Re: The problem with implementation defined behaviour. Bernd Paysan <bernd.paysan@gmx.de> - 2016-04-01 21:53 +0000
                Re: The problem with implementation defined behaviour. Andrew Haley <andrew29@littlepinkcloud.invalid> - 2016-04-02 11:46 -0500
                Re: The problem with implementation defined behaviour. Bernd Paysan <bernd.paysan@gmx.de> - 2016-04-02 21:43 +0000
                Re: The problem with implementation defined behaviour. Andrew Haley <andrew29@littlepinkcloud.invalid> - 2016-04-03 03:17 -0500
                Re: The problem with implementation defined behaviour. hughaguilar96@gmail.com - 2016-04-01 23:54 -0700
          Re: The problem with implementation defined behaviour. Albert van der Horst <albert@spenarnc.xs4all.nl> - 2016-03-30 12:58 +0000
          Re: The problem with implementation defined behaviour. Bernd Paysan <bernd.paysan@gmx.de> - 2016-03-30 22:22 +0000
        Re: The problem with implementation defined behaviour. Albert van der Horst <albert@spenarnc.xs4all.nl> - 2016-03-30 12:55 +0000
      Re: The problem with implementation defined behaviour. anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-03-30 07:44 +0000
        Re: The problem with implementation defined behaviour. Albert van der Horst <albert@spenarnc.xs4all.nl> - 2016-03-30 13:08 +0000
          Re: The problem with implementation defined behaviour. anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-03-30 13:43 +0000
        Re: The problem with implementation defined behaviour. Bernd Paysan <bernd.paysan@gmx.de> - 2016-03-30 22:06 +0000
      Re: The problem with implementation defined behaviour. trevor <tgritchie@blueyonder.co.uk> - 2016-03-30 13:13 +0100
        Re: The problem with implementation defined behaviour. Albert van der Horst <albert@spenarnc.xs4all.nl> - 2016-03-30 13:56 +0000
      Re: The problem with implementation defined behaviour. Albert van der Horst <albert@spenarnc.xs4all.nl> - 2016-03-30 12:49 +0000

csiph-web