Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #7132

Re: (simple?) problem with multiplication

From Pete Becker <pete@versatilecoding.com>
Organization Roundhouse Consulting, Ltd.
Newsgroups comp.lang.c++
Date 2011-06-24 14:14 -0400
Message-ID <2011062414142435091-pete@versatilecodingcom> (permalink)
References <589f8b74-d065-44a5-ab9e-81e6a6fcd88b@v12g2000vby.googlegroups.com> <iu2jph$1tj$1@hoshi.visyn.net>
Subject Re: (simple?) problem with multiplication

Show all headers | View raw

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)

Back to comp.lang.c++ | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

(simple?) problem with multiplication Ttodir <sanmrtn96@gmail.com> - 2011-06-21 11:04 -0700
  Re: (simple?) problem with multiplication Ttodir <sanmrtn96@gmail.com> - 2011-06-21 11:11 -0700
  Re: (simple?) problem with multiplication "Balog Pal" <pasa@lib.hu> - 2011-06-21 20:35 +0200
    Re: (simple?) problem with multiplication Anonymous <anonymous@no.net> - 2011-06-21 20:45 +0200
    Re: (simple?) problem with multiplication Pete Becker <pete@versatilecoding.com> - 2011-06-21 14:46 -0400
      Re: (simple?) problem with multiplication Ttodir <sanmrtn96@gmail.com> - 2011-06-21 12:03 -0700
        Re: (simple?) problem with multiplication Gido <gido0001@gmail.com> - 2011-06-21 14:30 -0700
          Re: (simple?) problem with multiplication Anonymous <anonymous@no.net> - 2011-06-21 23:32 +0200
          Re: (simple?) problem with multiplication Juha Nieminen <nospam@thanks.invalid> - 2011-06-23 06:33 +0000
  Re: (simple?) problem with multiplication Pete Becker <pete@versatilecoding.com> - 2011-06-21 14:40 -0400
  Re: (simple?) problem with multiplication Christopher <cpisz@austin.rr.com> - 2011-06-21 11:39 -0700
  Re: (simple?) problem with multiplication Anonymous <anonymous@no.net> - 2011-06-21 23:32 +0200
    Re: (simple?) problem with multiplication Kai-Uwe Bux <jkherciueh@gmx.net> - 2011-06-21 23:41 +0200
  Re: (simple?) problem with multiplication Rune Allnor <allnor@tele.ntnu.no> - 2011-06-21 21:33 -0700
    Re: (simple?) problem with multiplication Ttodir <sanmrtn96@gmail.com> - 2011-06-22 04:59 -0700
  Re: (simple?) problem with multiplication gwowen <gwowen@gmail.com> - 2011-06-22 06:55 -0700
    Re: (simple?) problem with multiplication Pete Becker <pete@versatilecoding.com> - 2011-06-22 10:10 -0400
      Re: (simple?) problem with multiplication Leigh Johnston <leigh@i42.co.uk> - 2011-06-22 15:19 +0100
        Re: (simple?) problem with multiplication Dilip <rdilipk@gmail.com> - 2011-06-22 07:33 -0700
          Re: (simple?) problem with multiplication Leigh Johnston <leigh@i42.co.uk> - 2011-06-22 15:39 +0100
            Re: (simple?) problem with multiplication Pete Becker <pete@versatilecoding.com> - 2011-06-22 11:02 -0400
              Re: (simple?) problem with multiplication "Paul" <pchristor@yahoo.co.uk> - 2011-06-23 23:45 +0100
          Re: (simple?) problem with multiplication gwowen <gwowen@gmail.com> - 2011-06-22 23:59 -0700
      Re: (simple?) problem with multiplication gwowen <gwowen@gmail.com> - 2011-06-22 23:50 -0700
        Re: (simple?) problem with multiplication "Paul" <pchristor@yahoo.co.uk> - 2011-06-23 09:26 +0100
  Re: (simple?) problem with multiplication "Paul" <pchristor@yahoo.co.uk> - 2011-06-22 21:24 +0100
    Re: (simple?) problem with multiplication "Paul" <pchristor@yahoo.co.uk> - 2011-06-24 00:00 +0100
  Re: (simple?) problem with multiplication gwowen <gwowen@gmail.com> - 2011-06-24 01:42 -0700
    Re: (simple?) problem with multiplication "Paul" <pchristor@yahoo.co.uk> - 2011-06-24 10:47 +0100
  Re: (simple?) problem with multiplication SG <s.gesemann@gmail.com> - 2011-06-24 10:09 -0700
    Re: (simple?) problem with multiplication Pete Becker <pete@versatilecoding.com> - 2011-06-24 13:32 -0400
      Re: (simple?) problem with multiplication Kai-Uwe Bux <jkherciueh@gmx.net> - 2011-06-24 20:07 +0200
        Re: (simple?) problem with multiplication Pete Becker <pete@versatilecoding.com> - 2011-06-24 14:14 -0400
          Re: (simple?) problem with multiplication Kai-Uwe Bux <jkherciueh@gmx.net> - 2011-06-24 20:28 +0200
            Re: (simple?) problem with multiplication Pete Becker <pete@versatilecoding.com> - 2011-06-24 16:26 -0400
              Re: (simple?) problem with multiplication "Paul" <pchristor@yahoo.co.uk> - 2011-06-25 03:01 +0100
                Re: (simple?) problem with multiplication "Paul" <pchristor@yahoo.co.uk> - 2011-06-25 18:20 +0100
            Re: (simple?) problem with multiplication "Alf P. Steinbach /Usenet" <alf.p.steinbach+usenet@gmail.com> - 2011-06-25 04:21 +0200
            Re: (simple?) problem with multiplication "Paul" <pchristor@yahoo.co.uk> - 2011-06-25 10:12 +0100
              Re: (simple?) problem with multiplication SG <s.gesemann@gmail.com> - 2011-06-25 02:51 -0700
                Re: (simple?) problem with multiplication "Paul" <pchristor@yahoo.co.uk> - 2011-06-25 11:19 +0100
                Re: (simple?) problem with multiplication "Paul" <pchristor@yahoo.co.uk> - 2011-06-25 11:19 +0100
                Re: (simple?) problem with multiplication Gareth Owen <gwowen@gmail.com> - 2011-06-26 07:59 +0100
                Re: (simple?) problem with multiplication "Paul" <pchristor@yahoo.co.uk> - 2011-06-26 12:34 +0100
          Re: (simple?) problem with multiplication SG <s.gesemann@gmail.com> - 2011-06-25 02:37 -0700
        Re: (simple?) problem with multiplication Gareth Owen <gwowen@gmail.com> - 2011-06-25 08:58 +0100
          Re: (simple?) problem with multiplication "Paul" <pchristor@yahoo.co.uk> - 2011-06-25 10:00 +0100
          Re: (simple?) problem with multiplication Kai-Uwe Bux <jkherciueh@gmx.net> - 2011-06-25 10:29 +0200

csiph-web