*/MOD 
Author Message
 */MOD

Hello,

What's the story behind */MOD ?  Is there some particularly
efficient way of computing it (perhaps only applicable to some
microcontrollers) or is it implemented basically as a
multiplication followed by division?  I'm thinking mostly of
systems that don't support double by single division in hardware.

Regards,

Joonas Pihlaja



Wed, 17 Mar 2004 04:57:33 GMT  
 */MOD

Quote:

> Hello,

> What's the story behind */MOD ?  Is there some particularly
> efficient way of computing it (perhaps only applicable to some
> microcontrollers) or is it implemented basically as a
> multiplication followed by division?  I'm thinking mostly of
> systems that don't support double by single division in hardware.

The charm of this operator, as well as */ and /MOD, is that
virtually all CPUs _do_ naturally produce a double product from
multiplication and divide a double by single giving both quotient
and product.  AFAIK Forth is the only high-level language
to take advantage of this feature.  Of course, to get the advantage
you have to code these operators in assembler.

Cheers,
Elizabeth

--
================================================
Elizabeth D. Rather   (US & Canada)       800-55-FORTH
FORTH Inc.                                      +1 310-491-3356
5155 W. Rosecrans Ave. #1018  Fax: +1 310-978-9454
Hawthorne, CA 90250
http://www.forth.com

"Forth-based products and Services for real-time
applications since 1973."
================================================



Wed, 17 Mar 2004 05:36:42 GMT  
 */MOD

Quote:

>What's the story behind */MOD ?  Is there some particularly
>efficient way of computing it (perhaps only applicable to some
>microcontrollers) or is it implemented basically as a
>multiplication followed by division?  I'm thinking mostly of
>systems that don't support double by single division in hardware.

They don't?

Multiplying 16 by 16 bits and getting a 32 bit outcome, or doing a 32 by
16 bit division resulting in a 16 bit quotient and remainder, that's all
pretty natural for the implementation.You have to fill in the upper
half, or discard it from the outcome, in order for it to be otherwise.

--
        Bart.



Wed, 17 Mar 2004 07:41:54 GMT  
 */MOD

Quote:


> >What's the story behind */MOD ?  Is there some particularly
> >efficient way of computing it (perhaps only applicable to some
> >microcontrollers) or is it implemented basically as a
> >multiplication followed by division?  I'm thinking mostly of
> >systems that don't support double by single division in hardware.

> They don't?

i8051:
  DIV AB
divides the unsigned 8-bit value in A by the unsigned 8-bit value in B.
Quote:
> Multiplying 16 by 16 bits and getting a 32 bit outcome, or doing a 32 by
> 16 bit division resulting in a 16 bit quotient and remainder, that's all
> pretty natural for the implementation.You have to fill in the upper
> half, or discard it from the outcome, in order for it to be otherwise.

> --
>         Bart.



Wed, 17 Mar 2004 15:21:29 GMT  
 */MOD

Quote:



>> >What's the story behind */MOD ?  Is there some particularly
>> >efficient way of computing it (perhaps only applicable to some
>> >microcontrollers) or is it implemented basically as a
>> >multiplication followed by division?  I'm thinking mostly of
>> >systems that don't support double by single division in hardware.

>> They don't?

> i8051:
>   DIV AB
> divides the unsigned 8-bit value in A by the unsigned 8-bit value in B.

I never understood why they did that.  The divide algorithm they use
probably shifts the dividend over the divisor, and that dividend must
be 16 bits wide, at least temporarily.  The 16/8 division would be a
much more useful component.  Perhaps it's just that the 8/8 division
was easier to lay out.

Andrew.



Wed, 17 Mar 2004 18:13:43 GMT  
 */MOD

Quote:

> The charm of this operator, as well as */ and /MOD, is that
> virtually all CPUs _do_ naturally produce a double product
> from multiplication and divide a double by single giving both
> quotient and product.

OK.  I was hoping that there was some nifty */MOD specific
implementation trick for CPUs that didn't do that naturally.

The reason I asked is that the Forth implementations that I've
looked at for doubly or division challenged systems all first
implement UM/MOD with a horrendously slow bit shifting algorithm,
and then use it to implement other division-like operations.

Quote:
> AFAIK Forth is the only high-level language to take advantage
> of this feature.  Of course, to get the advantage you have to
> code these operators in assembler.

The more I think about this the cooler it is.  It's a shame
conventional languages throw away the hard work of the processor
in discarding remainders and high bits of multiplications.  It's
probably the single result per operation reason that's keeping
them back. :)

Regards,

Joonas



Sun, 21 Mar 2004 14:31:26 GMT  
 */MOD
At Wed, 3 Oct 2001 09:31:26 +0300,

Quote:

>> The charm of this operator, as well as */ and /MOD, is that
>> virtually all CPUs _do_ naturally produce a double product
>> from multiplication and divide a double by single giving both
>> quotient and product.

>OK.  I was hoping that there was some nifty */MOD specific
>implementation trick for CPUs that didn't do that naturally.

>The reason I asked is that the Forth implementations that I've
>looked at for doubly or division challenged systems all first
>implement UM/MOD with a horrendously slow bit shifting algorithm,
>and then use it to implement other division-like operations.

>> AFAIK Forth is the only high-level language to take advantage
>> of this feature.  Of course, to get the advantage you have to
>> code these operators in assembler.

>The more I think about this the cooler it is.  It's a shame
>conventional languages throw away the hard work of the processor
>in discarding remainders and high bits of multiplications.  It's
>probably the single result per operation reason that's keeping
>them back. :)

The problem is with processors which have no 32-bit and 32-bit to
64-bit multiplication instructions (such as ARM).  I'm now trying to
implement all the arithmetic and logical words, and I've run into the
problem that such multiplication will have to be implemented in
software (division is also bad, because there is no division
instructions whatsoever on ARM).  Does anyone know of 32-bit and
32-bit to 64-bit multiplication algorithms and 64-bit and 32-bit to
32-bit and 32-bit integer division/modulus assembly code for ARM?

--
Yes, I know my enemies.
They're the teachers who tell me to fight me.
Compromise, conformity, assimilation, submission, ignorance,
hypocrisy, brutality, the elite.
All of which are American dreams.

              - Rage Against The Machine



Mon, 22 Mar 2004 06:28:14 GMT  
 */MOD


Quote:
> The problem is with processors which have no 32-bit and 32-bit to
> 64-bit multiplication instructions (such as ARM).  I'm now trying to
> implement all the arithmetic and logical words, and I've run into the
> problem that such multiplication will have to be implemented in
> software (division is also bad, because there is no division
> instructions whatsoever on ARM).  Does anyone know of 32-bit and
> 32-bit to 64-bit multiplication algorithms and 64-bit and 32-bit to
> 32-bit and 32-bit integer division/modulus assembly code for ARM?

 You'll probably get such questions quickly answered
 in the newsgroup comp.sys.arm.  There was a short
 thread about 32/26bit division just a few months ago.

--
Tony Williams.



Mon, 22 Mar 2004 06:58:53 GMT  
 */MOD

Quote:

> The problem is with processors which have no 32-bit and 32-bit to
> 64-bit multiplication instructions (such as ARM).

It depends which ARM.  Some have a fast multiply instruction that does
the Right Thing.  This mixed precision multiply is pretty much
essential for rapid execution of public-key cryptographic primitives,
which is perhaps one reason for its oincludion in the ISA.

Quote:
> I'm now trying to implement all the arithmetic and logical words,
> and I've run into the problem that such multiplication will have to
> be implemented in software (division is also bad, because there is
> no division instructions whatsoever on ARM).  Does anyone know of
> 32-bit and 32-bit to 64-bit multiplication algorithms

Multiple-precision arithmetic is in Knuth.  There's a new edition out. [*]

For division, you can use classical binary long division.  There's a
nice explanation in
www.ece.uvic.ca/~wlittle/ceng440/440classnotes2001.pdf.

Andrew.

[*] The Art of Computer Programming : Seminumerical Algorithms (Vol 2,
3rd Ed) by Donald Ervin Knuth 3rd edition Vol 2 (November 1997)
Addison-Wesley Pub Co; ISBN: 0201896842



Mon, 22 Mar 2004 15:43:05 GMT  
 */MOD

...
Quote:
> The charm of [ */MOD ] as well as */ and /MOD, is that
> virtually all CPUs _do_ naturally produce a double product from
> multiplication and divide a double by single giving both quotient
> and product.  AFAIK Forth is the only high-level language
> to take advantage of this feature.  Of course, to get the advantage
> you have to code these operators in assembler.

If you're willing to get pretty obscure --
Tandem (now Compaq, soon apparently HP) originally
designed their own ISA/CPUs, which were inspired by
the HP3000 and largely but not entirely register-stack
oriented, and their own SIL/2.5GL "T/TAL" (Tandem
Transaction Application Language) later shortened to TAL
in the BCPL, C, BLISS group which closely reflects the ISA.

In particular the TNS signed multiply and divide are
strictly 16-bit, but _unsigned_ multiply is 16x16->32
and unsigned divide is 32/16->16quo+16rem.  In TAL
* invokes signed multiply with a 16bit result and '*'
invokes unsigned multiply with a 32bit result (which
you convert back to 16bits explicitly if desired);
similarly / takes two 16bit operands while '/' takes
32bit and 16bit but keeps only the 16bit quotient,
while '\' keeps only the 16bit remainder -- to get both
from one operation you must use (inline) assembler.

In the last few years Tanpaq replaced their own CPUs
with commercial RISC chips (while keeping their
system architecture, and OS, which are the more
important parts of their system, largely unchanged)
and while TAL is still supported (with CPU features
emulated where necessary) they are mostly pushing
C in this area.

--
- David.Thompson 1 now at worldnet.att.net



Sat, 03 Apr 2004 12:53:49 GMT  
 
 [ 10 post ] 

 Relevant Pages 

1. MOD and /MOD with Pygmy Forth

2. SM/REM FM/MOD and UM/MOD on a 32bit cell ix86 Forth

3. Utils.Mod, ET.Mod

4. Mod-2 or Mod-3 for Mac

5. Mod-2 and Mod-3 compiler

6. Mod-2 and Mod-3 compiler for the IBM PC and compatibles

7. search algorithm for a math mod function (5 mod[2]=1)

8. awk's mod operator % question (application: log base2 non-integer result)

9. MOD Library ?

10. Something Better then MOD?

11. How to play Mod with RB?

12. xml.smalltalk.org, mod.smalltalk.org and camp.smalltalk.org DNS problems resolved

 

 
Powered by phpBB® Forum Software