Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!selfless.tophat.at!news.glorb.com!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: Tue, 21 Jun 2011 13:40:05 -0500
From: Pete Becker <pete@versatilecoding.com>
Organization: Roundhouse Consulting, Ltd.
Newsgroups: comp.lang.c++
Date: Tue, 21 Jun 2011 14:40:05 -0400
Message-ID: <2011062114400582456-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: 23
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-PNv6upqNTXBjJDzp3xV+N1tEgf4Xn0JUWKb+adAnLNp31rjOoXJ4TrgxCvZkJJCOq0ZUy7b4Gd8YD7z!BgqKw4zDxxIUtpPbjVGS+G9wBzrrmnF9N8ZVhah0VarPw16XVEVQVcj2Hvh+fuGZfTNiiitO
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: 1763
Xref: x330-a1.tempe.blueboxinc.net comp.lang.c++:7028

On 2011-06-21 14:04:37 -0400, Ttodir said:

> Hello,
> 
> I need a fast way to calculate (a * b) % B, with the following
> constraints:
> 
> - a, b, B are int
> - B = 10^N , N>0 arbitrary (B always fits in an int)
> - the result must be valid even if the multiplication overflows
> - portable code, no assumptions on the sizeof(int) and no types larger
> than int can be used.
> 
> Any help will be much appreciated.

Read about greatest common divisors.

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