Path: csiph.com!x330-a1.tempe.blueboxinc.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!border3.nntp.dca.giganews.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 15:26:24 -0500 From: Pete Becker Organization: Roundhouse Consulting, Ltd. Newsgroups: comp.lang.c++ Date: Fri, 24 Jun 2011 16:26:24 -0400 Message-ID: <2011062416262439377-pete@versatilecodingcom> References: <589f8b74-d065-44a5-ab9e-81e6a6fcd88b@v12g2000vby.googlegroups.com> 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: 62 X-Usenet-Provider: http://www.giganews.com X-Trace: sv3-aEzWRRiTXKnuYJfYjhymHSs34r3oVCWhwWB+FkfpCgILSILZ5DtRrq9Q+beHaKLS1kTGqn2AHmyo0Ub!Dzxqyn1mr8AtNwQTY5Q6A1BS+0r/xHRwwV/dDNtsXg97M6zQkXjTDrbAaMUTcYKDHpEOLUfa 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: 3418 Xref: x330-a1.tempe.blueboxinc.net comp.lang.c++:7137 On 2011-06-24 14:28:09 -0400, Kai-Uwe Bux said: > Pete Becker wrote: > >> 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? > > Yes. > >>> >>> (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". > > A fair interpretation has to take into account the full material of the > text. How does your interpretation deal with the "can be compute with a > modified double-and-add algorithm for multiplication" part? That part makes > it perfectly clear that SG did not intend (a%B)*(b%B) to be evaluated as a C > expression. Your interpretation (forced upon readers of your posting by > leaving out the part it ignored) makes it sound as though he did. That is > why I think your quoting was vicious: it left out a part that is crucial to > the interpretation of the part that was quoted. > Okay. The signal to bullshit ratio in this newsgroup is fast approaching zero. It's not worth the time spent reading it any more. Have a good life. -- Pete Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The Standard C++ Library Extensions: a Tutorial and Reference (www.petebecker.com/tr1book)