Path: csiph.com!x330-a1.tempe.blueboxinc.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!news.glorb.com!postnews.google.com!news1.google.com!Xl.tags.giganews.com!border1.nntp.dca.giganews.com!nntp.giganews.com!local2.nntp.dca.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Fri, 24 Jun 2011 13:14:24 -0500
From: Pete Becker <pete@versatilecoding.com>
Organization: Roundhouse Consulting, Ltd.
Newsgroups: comp.lang.c++
Date: Fri, 24 Jun 2011 14:14:24 -0400
Message-ID: <2011062414142435091-pete@versatilecodingcom>
References: <589f8b74-d065-44a5-ab9e-81e6a6fcd88b@v12g2000vby.googlegroups.com> <iu2jph$1tj$1@hoshi.visyn.net>
MIME-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1; format=flowed
Content-Transfer-Encoding: 8bit
Subject: Re: (simple?) problem with multiplication
User-Agent: Unison/2.1.4
Lines: 42
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-u4sAtPaUQlazYYSWpIH07JKMps/WyStzoyxabjGCeFJ1xPKGGHzapfZkltj6EM9HVxxUPTmlKcmOyMd!aZ5m4CPlNFyPrIOCJNiKexsM468safR6jbu4tWsaP+kDqKfK8e3/bquiMqAr315+EBW1QwgD
X-Complaints-To: abuse@giganews.com
X-DMCA-Notifications: http://www.giganews.com/info/dmca.html
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 2507
Xref: x330-a1.tempe.blueboxinc.net comp.lang.c++:7132

On 2011-06-24 14:07:45 -0400, Kai-Uwe Bux said:

> Pete Becker wrote:
> 
>> On 2011-06-24 13:09:56 -0400, SG said:
>> 
>>> In case this hasn't been mentioned already (I just skimmed this
>>> thread):
>>> 
>>> (a*b)%B = ((a%B)*(b%B))%B
>>> 
>> 
>> Yes, but it doesn't solve the problem. :-( Suppose a*b overflows and
>> that B is greater than both a and b. Then a%B is a, and b%B is b; then
>> (a%B)*(b%B) is a*b, and it overflows.
>> 
>> Another approach is brute force: write double-precision multiplication
>> and division routines; not too hard, but involves tedious details;
> 
> That seems to be vicious snipping on your part. SG said:

"Vicious"? Really?

> 
>     (a*b)%B = ((a%B)*(b%B))%B
> 
>   The last expression can be computed with a modified double-and-add
>   algorithm for multiplication that includes the modulo reduction.
> 
> So, he did not rely on (a%B)*(b%B) not overflowing.

Um, if the expression ((a%B)*(b%B)) overflows the behavior is 
undefined. "The last expression" is that result %B. If that's not your 
interpretation, please allow for the possibility that others may have 
read it differently without being "vicious".

-- 
  Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The 
Standard C++ Library Extensions: a Tutorial and Reference 
(www.petebecker.com/tr1book)