Fri, 13 May 1994 14:08:11 GMT

Related articles |
---|

ANSI portable overflow detection davids@ICSI.Berkeley.EDU (1994-05-12) |

Re: ANSI portable overflow detection upton@quip.eecs.umich.edu (1994-05-13) |

Re: ANSI portable overflow detection hbaker@netcom.com (1994-05-13) |

Re: ANSI portable overflow detection Roger@natron.demon.co.uk (1994-05-18) |

Newsgroups: | comp.compilers |

From: | upton@quip.eecs.umich.edu (Michael Upton) |

Keywords: | arithmetic |

Organization: | University of Michigan EECS Dept. |

References: | 94-05-039 |

Date: | Fri, 13 May 1994 14:08:11 GMT |

David Petrie Stoutamire <davids@ICSI.Berkeley.EDU> wrote:

*>[for a compiler that translates into C, is there a reasonably efficient*

*>and portable way to check for overflow on an integer multiply?]*

An N bit multiply can be performed using 4 N/2 bit multiplies.

A * B = ??

A

*B

-----------------

YZ

for 2's comp arithmetic you want Y to be all 0s or all 1's.

A and B can be represented by 2 N/2 bit halfs:

A= jk

B= lm

A * B =

jk*lm =

jk

*lm

---------------

km

jm0

kl0

+jl00

----------------

pqrs

Z = rs

Y=pq

C= carry out of Z into Y

Z = k*m + (((j*m)+(k*l))<< N/2)

Y = (l*j) + (((j*m)+(k*l))>> N/2) + C

C = ((((k*m) >> N/2) + (j*m) + (k*l)) >> N/2) - (Z>>N/2)

Y should be all 1's or all 0's

You will probably want to convert A and B to positive before

creating jk and lm. If you do this then the msb of l and j will be 0,

and thus the msb of (j*m) and the msb of (k*l) will be 0.

I think the C term is correct, but you would want to derive this

over yourself.

mike

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.