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

Groups > comp.lang.c++ > #7024 > unrolled thread

(simple?) problem with multiplication

Back to article view | Back to comp.lang.c++

Contents

  (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

Page 1 of 3  [1] 2 3  Next page →

#7024 — (simple?) problem with multiplication

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.

[toc] | [next] | [standalone]

#7025

On Jun 21, 8:04 pm, Ttodir <sanmrt...@gmail.com> wrote:
> 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.

Sorry, just one more note: consider a >=0 and b >=0 (but int)

[toc] | [prev] | [next] | [standalone]

#7026

"Ttodir" <sanmrtn96@gmail.com>
>  no types larger than int can be used.

why?

[toc] | [prev] | [next] | [standalone]

#7030

Balog Pal ha scritto:
> "Ttodir" <sanmrtn96@gmail.com>
>>  no types larger than int can be used.
> 
> why?
> 
because a possible extension in the future will be to declare the 
variables long long instead of int

[toc] | [prev] | [next] | [standalone]

#7031

On 2011-06-21 14:35:43 -0400, Balog Pal said:

> "Ttodir" <sanmrtn96@gmail.com>
>> no types larger than int can be used.
> 
> why?

Because it's a homework problem, with artificial constraints to force 
students to think.

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

[toc] | [prev] | [next] | [standalone]

#7033

On Jun 21, 8:46 pm, Pete Becker <p...@versatilecoding.com> wrote:
> On 2011-06-21 14:35:43 -0400, Balog Pal said:
>
> > "Ttodir" <sanmrt...@gmail.com>
> >> no types larger than int can be used.
>
> > why?
>
> Because it's a homework problem, with artificial constraints to force
> students to think.
>
> --
>   Pete
> Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
> Standard C++ Library Extensions: a Tutorial and Reference
> (www.petebecker.com/tr1book)

No, it's a problem coming from a real necessity. I made it simple. For
now I have found an algorithm, but is slow, which consists in
splitting a and b in smaller componenents, then calculating the higher
bits of the multiplication with simple math and the lower bits with an
grade-school multiplication algorithm

[toc] | [prev] | [next] | [standalone]

#7035

> No, it's a problem coming from a real necessity. I made it simple. For
> now I have found an algorithm, but is slow, which consists in
> splitting a and b in smaller componenents, then calculating the higher
> bits of the multiplication with simple math and the lower bits with an
> grade-school multiplication algorithm

Well, if it's not homework... Wouldn't the following do the trick?

int res = (a % B) * (b % B);
while (res >= B)
    res -= B;

[toc] | [prev] | [next] | [standalone]

#7037

Gido ha scritto:
>> No, it's a problem coming from a real necessity. I made it simple. For
>> now I have found an algorithm, but is slow, which consists in
>> splitting a and b in smaller componenents, then calculating the higher
>> bits of the multiplication with simple math and the lower bits with an
>> grade-school multiplication algorithm
> 
> Well, if it's not homework... Wouldn't the following do the trick?
> 
> int res = (a % B) * (b % B);

i think res might overflow there

> while (res >= B)
>     res -= B;

[toc] | [prev] | [next] | [standalone]

#7072

Gido <gido0001@gmail.com> wrote:
> while (res >= B)
>    res -= B;

  Isn't that the exact same thing as "res %= B;" (but less efficient)?
What's the point?

[toc] | [prev] | [next] | [standalone]

#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)

[toc] | [prev] | [next] | [standalone]

#7032

On Jun 21, 1:04 pm, Ttodir <sanmrt...@gmail.com> wrote:
> 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.

Smells like homework to me.

[toc] | [prev] | [next] | [standalone]

#7036

Ttodir ha scritto:
> 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.

replace c with B in the below code, and long long with int, then test it

/* this function calculates (a*b)%c taking into account that a*b might 
overflow */
long long mulmod(long long a,long long b,long long c){
     long long x = 0,y=a%c;
     while(b > 0){
         if(b%2 == 1){
             x = (x+y)%c;
         }
         y = (y*2)%c;
         b /= 2;
     }
     return x%c;
}

[toc] | [prev] | [next] | [standalone]

#7038

Anonymous wrote:

> Ttodir ha scritto:
>> 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.
> 
> replace c with B in the below code, and long long with int, then test it
> 
> /* this function calculates (a*b)%c taking into account that a*b might
> overflow */
> long long mulmod(long long a,long long b,long long c){
>      long long x = 0,y=a%c;
>      while(b > 0){
>          if(b%2 == 1){
>              x = (x+y)%c;
>          }
>          y = (y*2)%c;
>          b /= 2;
>      }
>      return x%c;
> }

I think, the proposed code could still overflow when c is, say, one short of 
the maximum possible value for long long: the code assumes that neither x+y 
nor 2*y overflow.


Best,

Kai-Uwe Bux

[toc] | [prev] | [next] | [standalone]

#7047

On Jun 21, 8:04 pm, Ttodir <sanmrt...@gmail.com> wrote:
> 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.

Fixed-point arithmetics with overflow issues is common
in embedded devices. You might want to ask parts this
question in comp.dsp.

Having said that - your other constraints seem contradictory:
Arbitrary N but no assumptions about the size of int?
Portable code but no types 'larger than int' to be used?

Either this is homework in disguise or you will have to
relax on some of these constraints. Or get a slow solution.

Rune

[toc] | [prev] | [next] | [standalone]

#7055

On 22 Giu, 06:33, Rune Allnor <all...@tele.ntnu.no> wrote:
> On Jun 21, 8:04 pm, Ttodir <sanmrt...@gmail.com> wrote:
>
> > 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.
>
> Fixed-point arithmetics with overflow issues is common
> in embedded devices. You might want to ask parts this
> question in comp.dsp.
>
> Having said that - your other constraints seem contradictory:
> Arbitrary N but no assumptions about the size of int?
> Portable code but no types 'larger than int' to be used?

I did say B will always be contained in an int, so N is arbitray but
limited.
long long is not standard , and long might have the same size as int.

> Rune

[toc] | [prev] | [next] | [standalone]

#7057

On Jun 21, 7:04 pm, Ttodir <sanmrt...@gmail.com> wrote:
> 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.


You know how to get the overflowing part of the sum.
You know how to get the non-overflowing part of the sum.
You know that modulo is distributive over multiplication ...

Just beware that calculations involving the overflow part may
themselves overflow ... but not forever.

[toc] | [prev] | [next] | [standalone]

#7058

On 2011-06-22 09:55:49 -0400, gwowen said:

> You know that modulo is distributive over multiplication ...

But it's not. :-(

(5 * 2) % 10 != (5%10) * (2%10)

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

[toc] | [prev] | [next] | [standalone]

#7059

On 22/06/2011 15:10, Pete Becker wrote:
> On 2011-06-22 09:55:49 -0400, gwowen said:
>
>> You know that modulo is distributive over multiplication ...
>
> But it's not. :-(
>
> (5 * 2) % 10 != (5%10) * (2%10)

Yes it is:

(5 * 2) % 10 == ( (5 % 10) * (2 % 10) ) % 10

/Leigh

[toc] | [prev] | [next] | [standalone]

#7060

On Jun 22, 10:19 am, Leigh Johnston <le...@i42.co.uk> wrote:
> On 22/06/2011 15:10, Pete Becker wrote:
>
> > On 2011-06-22 09:55:49 -0400, gwowen said:
>
> >> You know that modulo is distributive over multiplication ...
>
> > But it's not. :-(
>
> > (5 * 2) % 10 != (5%10) * (2%10)
>
> Yes it is:
>
> (5 * 2) % 10 == ( (5 % 10) * (2 % 10) ) % 10
>
> /Leigh

Huh? For an operation to be called distributive it has to be both left
& right distributive. Obviously modulo over multiplication is not
right distributive as Pete Showed.

[toc] | [prev] | [next] | [standalone]

#7061

On 22/06/2011 15:33, Dilip wrote:
> On Jun 22, 10:19 am, Leigh Johnston<le...@i42.co.uk>  wrote:
>> On 22/06/2011 15:10, Pete Becker wrote:
>>
>>> On 2011-06-22 09:55:49 -0400, gwowen said:
>>
>>>> You know that modulo is distributive over multiplication ...
>>
>>> But it's not. :-(
>>
>>> (5 * 2) % 10 != (5%10) * (2%10)
>>
>> Yes it is:
>>
>> (5 * 2) % 10 == ( (5 % 10) * (2 % 10) ) % 10
>>
>> /Leigh
>
> Huh? For an operation to be called distributive it has to be both left
> &  right distributive. Obviously modulo over multiplication is not
> right distributive as Pete Showed.

I guess, however what I showed is probably what gwowen actually meant.

/Leigh

[toc] | [prev] | [next] | [standalone]

Page 1 of 3  [1] 2 3  Next page →

Back to top | Article view | comp.lang.c++

csiph-web