1. Forum
  2. Usenet
  3. COMP.LANG.FORTH

  • Division by 3 without hardware divide

    From Brad Eckert@21:1/5 to All on Fri Nov 4 08:52:14 2022
    ```
    \ "3 /mod" for positive numbers without division

    : 3/ ( u -- u/3 )
    [ 0 1 3 um/mod nip 1+ ] literal um* nip
    ;

    : 3/mod ( u -- ur uq )
    dup 3/ swap ( uq u )
    over dup 2* + - swap
    ;

    : test ( lo hi -- errors )
    2>r 0 r> r> do
    i 3/mod \ actual
    i 0 3 um/mod \ expected
    d= invert - \ tally
    loop
    ;
    ```
    Not very interesting I will admit, although **test** was freakishly fast when I tried it in a host Forth. Testing all 32-bit numbers (4e9 of them) took less than a minute.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Anton Ertl@21:1/5 to Brad Eckert on Fri Nov 4 17:22:46 2022
    Brad Eckert <hwfwguy@gmail.com> writes:
    ```
    \ "3 /mod" for positive numbers without division

    : 3/ ( u -- u/3 )
    [ 0 1 3 um/mod nip 1+ ] literal um* nip
    ;

    : 3/mod ( u -- ur uq )
    dup 3/ swap ( uq u )
    over dup 2* + - swap
    ;

    : test ( lo hi -- errors )
    2>r 0 r> r> do
    i 3/mod \ actual
    i 0 3 um/mod \ expected
    d= invert - \ tally
    loop
    ;
    ```

    Gforth has had staged division and used it for division by constants
    for a few years, see <http://git.savannah.gnu.org/cgit/gforth.git/tree/stagediv.fs>

    : 3u/ 3 u/ ; ok
    : 3u/mod 3 u/mod ; ok
    see 3u/
    : 3u/ $7F8D8090E108
    u/-stage2m ; ok
    see 3u/mod
    : 3u/mod $7F8D8090E120
    u/mod-stage2m ; ok
    $7F8D8090E108 3 cells dump
    7F8D8090E108: 56 55 55 55 55 55 55 55 - 55 55 55 55 55 55 55 55 VUUUUUUUUUUUUUUU
    7F8D8090E118: 03 00 00 00 00 00 00 00 - ........

    This works for the full unsigned range, not just for positive numbers.

    Signed division is also supported:

    : 3/ 3 / ; ok
    : 3/mod 3 /mod ; ok
    see 3/
    : 3/ $7F8D8090E138
    /f-stage2m ; ok
    see 3/mod
    : 3/mod $7F8D8090E150
    /modf-stage2m ; ok
    $7F8D8090E138 3 cells dump
    7F8D8090E138: AB AA AA AA AA AA AA AA - 01 00 00 00 00 00 00 00 ................
    7F8D8090E148: 03 00 00 00 00 00 00 00 - ........

    On an Intel Skylake I saw big speedups (I don't find the results at
    the moment), on Ryzens less (they have faster division on hardware),
    on ARMs even less.

    - 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: https://forth-standard.org/
    EuroForth 2022: https://euro.theforth.net

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From minforth@arcor.de@21:1/5 to Brad Eckert on Fri Nov 4 14:20:08 2022
    Brad Eckert schrieb am Freitag, 4. November 2022 um 16:52:15 UTC+1:
    ```
    \ "3 /mod" for positive numbers without division

    : 3/ ( u -- u/3 )
    [ 0 1 3 um/mod nip 1+ ] literal um* nip
    ;

    : 3/mod ( u -- ur uq )
    dup 3/ swap ( uq u )
    over dup 2* + - swap
    ;

    : test ( lo hi -- errors )
    r 0 r> r> do
    i 3/mod \ actual
    i 0 3 um/mod \ expected
    d= invert - \ tally
    loop
    ;
    ```
    Not very interesting I will admit, although **test** was freakishly fast when I tried it in a host Forth. Testing all 32-bit numbers (4e9 of them) took less than a minute.

    Some references for division by reciprocal multiplication:

    http://homepage.cs.uiowa.edu/~jones/bcd/divide.html

    https://stackoverflow.com/questions/41183935/why-does-gcc-use-multiplication-by-a-strange-number-in-implementing-integer-divi

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)