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 2 of 3 — ← Prev page 1 [2] 3  Next page →

#7062

On 2011-06-22 10:39:37 -0400, Leigh Johnston said:

> 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.
> 

That's probably true, but it's not what distributive means.

-- 
  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]

#7090

"Pete Becker" <pete@versatilecoding.com> wrote in message 
news:201106221102413141-pete@versatilecodingcom...
> On 2011-06-22 10:39:37 -0400, Leigh Johnston said:
>
>> 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.
>>
>
> That's probably true, but it's not what distributive means.
>
But does this help solve the problem?

There is still the problem of;  if the divisor is very large and the results 
of the two modulo expressions are still too large to multiply without 
overflow. The obvious solution is to factorise these results further but 
what if both results are primes?

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

#7074

On Jun 22, 3:33 pm, Dilip <rdil...@gmail.com> wrote:

> Huh? For an operation to be called distributive it has to be both left
> & right distributive.

The ambiguity is nothing to do with left & right distributive - its
about what "=" means.

I implicitly meant "equality in the Z_n cyclic-group sense", at which
point Pete's 10 != 0 becomes 10==0 (mod 10). I should've been clearer.

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

#7073

On Jun 22, 3:10 pm, Pete Becker <p...@versatilecoding.com> 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)

... it is once you define equality using equivalence classes "mod
p".
I should've said that explicitly, but I was trying to give hints
rather than the solution.

10 != 0, but (10 == 0) mod 10

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

#7075

"gwowen" <gwowen@gmail.com> wrote in message 
news:078b0d70-037f-44e7-b10f-018ffe800f86@e35g2000yqc.googlegroups.com...
On Jun 22, 3:10 pm, Pete Becker <p...@versatilecoding.com> 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)

--... it is once you define equality using equivalence classes "mod
--p".
--I should've said that explicitly, but I was trying to give hints
--rather than the solution.

What were you hinting at?
You also said:
"You know how to get the overflowing part of the sum.
You know how to get the non-overflowing part of the sum."

What are the overflow and non-overflow parts of what sum?
Are you trying to pretend there is a way to solve this using some secret 
sum?

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

#7067

"Ttodir" <sanmrtn96@gmail.com> wrote in message 
news:589f8b74-d065-44a5-ab9e-81e6a6fcd88b@v12g2000vby.googlegroups.com...
> 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.
>

If you convert the integer into an array such that 543 was {5,4,3}, or in a 
vector  you can do it.
Here is an example of how to overcome such a problem using vectors, it may 
not be perfect but it should give you the idea:
#include <iostream>
#include <vector>

typedef unsigned int uint;
typedef std::vector<uint> v_uint;

v_uint foo(v_uint v1, v_uint v2, uint N){
 uint pow = N;
 v_uint retv;
 uint carry=0;
 uint temp_prod =0;

 //v1 must contain the largest.
 for(int i=0; i<v1.size() && pow>=10; i++, pow/=10){
  for (int j=i; j>=0; j-- ){
   if(i<v2.size()){
    temp_prod += v1[i-j]* v2[j];
   }
   if( i>v2.size() ){
    if( (i-j)<v2.size() )
     temp_prod+= v1[j]* v2[i-j];
   }
  }
  temp_prod +=carry;
  retv.push_back( temp_prod%10 );
  carry = temp_prod/10;
  temp_prod=0;
 }
 return retv;
}

int main(){
 uint N = 100000;
 v_uint a(5, 3);
 v_uint b(4,5);
 v_uint v  = foo(a,b, N);

 for(int i=0; i<v.size() ; i++){
  std::cout<< v[i] << std::endl;
 }

 std::cout<< (33333*5555)%100000;

}

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

#7091

"Paul" <pchristor@yahoo.co.uk> wrote in message 
news:0csMp.20407$Dk2.5847@newsfe04.ams2...
>
> "Ttodir" <sanmrtn96@gmail.com> wrote in message 
> news:589f8b74-d065-44a5-ab9e-81e6a6fcd88b@v12g2000vby.googlegroups.com...
>> 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.
>>
>
> If you convert the integer into an array such that 543 was {5,4,3}, or in 
> a vector  you can do it.
> Here is an example of how to overcome such a problem using vectors, it may 
> not be perfect but it should give you the idea:
> #include <iostream>
> #include <vector>
>
> typedef unsigned int uint;
> typedef std::vector<uint> v_uint;
>
> v_uint foo(v_uint v1, v_uint v2, uint N){
> uint pow = N;
> v_uint retv;
> uint carry=0;
> uint temp_prod =0;
>
> //v1 must contain the largest.
> for(int i=0; i<v1.size() && pow>=10; i++, pow/=10){
>  for (int j=i; j>=0; j-- ){
>   if(i<v2.size()){
>    temp_prod += v1[i-j]* v2[j];
>   }
>   if( i>v2.size() ){
>    if( (i-j)<v2.size() )
>     temp_prod+= v1[j]* v2[i-j];
>   }
>  }
>  temp_prod +=carry;
>  retv.push_back( temp_prod%10 );
>  carry = temp_prod/10;
>  temp_prod=0;
> }
> return retv;
> }
>
> int main(){
> uint N = 100000;
> v_uint a(5, 3);
> v_uint b(4,5);
> v_uint v  = foo(a,b, N);
>
> for(int i=0; i<v.size() ; i++){
>  std::cout<< v[i] << std::endl;
> }
>
> std::cout<< (33333*5555)%100000;
>
> }
>
>

Previous code was a bit buggy I will include a revised version which 
includes a couple of helper functions.
Obviously there is room for improvement but it seems to work ok.

#include <iostream>
#include <vector>

typedef unsigned int uint;
typedef std::vector<uint> v_uint;

v_uint int_to_vect(uint arg, uint base){
 v_uint retv;
 while(arg){
  retv.push_back(arg%base);
  arg/=base;
 }
 return retv;
}

uint vect_to_int(v_uint v, uint B){
 uint temp=0;
 uint pow=1;

 for (int i=0; i<v.size(); i++, pow*=B){
  temp+=v[i]*pow;
 }

 return temp;
}

uint power_mag(uint B, uint pow){
 uint temp=(pow)?B:1;
 for (int i=1; i<pow; i++){
  if(temp*B>temp)
  temp*=B;
 }
 return temp;
}


uint foo(uint a, uint b, uint B, uint p){
 v_uint v1= int_to_vect((a>=b)?a:b, B);
 v_uint v2= int_to_vect((a>=b)?b:a, B);
 int v1s= v1.size();
 int v2s= v2.size();
 uint pow = power_mag(B,p);
 v_uint retv;
 uint carry=0;
 uint temp_prod =0;

 for(int i=0; i<(v1s+v2s-1) && pow>=B; i++, pow/=B){
  for (int j=i; j>=0; j-- ){
   if(i<v2s){
    temp_prod += v1[i-j]* v2[j];
   }
   if( i>=v2s && i<v1s && (i-j)<v2s ){
    temp_prod += v1[j]* v2[i-j];
   }
   if(i>=v1s && j<(v2s-1)-(i-v1s) ){
    temp_prod+= v1[v1s-1-j] * v2[j+(i-(v1s-1))];
   }
  }
  temp_prod +=carry;
  retv.push_back( temp_prod%B );
  carry = temp_prod/B;
  temp_prod=0;
 }
 while(pow>=B && carry){
  retv.push_back(carry%B);
  carry/=B;
  pow/=B;
 }
 return vect_to_int(retv,B);
}


int main(){
 uint B = 8; //Base for divisor
 uint pow = 6; //Power for divisor

 uint x  = foo(96,9677,B, pow);

 //Example (9677*96)%8^6
}



Please let me know if you find a better way of doing it, It is alot simpler 
if  B==2 but unfortunately your requirement was B==10.

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

#7099

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.

Here's a sketch solution. It's not well tested, but I think the ideas
are sound... It uses unsigneds rather than ints, and takes N as a
template parameter, both for convenience, but nothing bigger.

[implementation - modint.hpp]
#ifndef MODINT_HPP
#define MODINT_HPP

#include<climits>

template <unsigned N>
class modint
{
private:
  unsigned val_;
  static modint overflowmod_;

public:
  void operator+=(const modint& rhs) {
    unsigned increment = (rhs.val()%N);
    if(val_ > UINT_MAX - increment){ // overflow
      increment -= N-val_;           // add enough to make val_ == N
~= 0
      val_ = 0;
    }
    val_ = (val_ + increment) % N;
  }

  void rightshift() { val_ /= 2;}
  void leftshift() {
    const bool overflow = (val_ > UINT_MAX/2);
    val_ *= 2;
    val_ %= N;
    if(overflow) *this += modint(overflowmod_);
  }

  unsigned val() const { return val_;}
  modint(unsigned x) : val_(x % N) {}
};

template <unsigned N>
modint<N> modint<N>::overflowmod_ = (1 + (UINT_MAX % N));

// peasants arithmetic, mod N
template <unsigned N>
modint<N> operator*(modint<N> r1,modint<N> r2)
{
  modint<N> tot = 0;
  while(r2.val() != 0){
    if(r2.val() % 2 == 1) {
      tot += r1;
    }
    r2.rightshift();
    r1.leftshift();
  }
  return tot;
}
#endif

[test program]

#include <iostream>
#include "modint.hpp"

int main(void)
{
  const unsigned BIGVAL = 0xFFFFFFFF;
  modint<BIGVAL> a = BIGVAL-3, b =  BIGVAL-9;

  std::cout << a.val() << " " << b.val() << std::endl;
  std::cout << (a * b).val() << std::endl;
}

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

#7103

"gwowen" <gwowen@gmail.com> wrote in message 
news:9a27e4e2-96be-4fc5-b163-d4bd99f7ca3a@k6g2000yqc.googlegroups.com...
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.

Here's a sketch solution. It's not well tested, but I think the ideas
are sound... It uses unsigneds rather than ints, and takes N as a
template parameter, both for convenience, but nothing bigger.

[implementation - modint.hpp]
#ifndef MODINT_HPP
#define MODINT_HPP

#include<climits>

template <unsigned N>
class modint
{
private:
  unsigned val_;
  static modint overflowmod_;

public:
  void operator+=(const modint& rhs) {
    unsigned increment = (rhs.val()%N);
    if(val_ > UINT_MAX - increment){ // overflow
      increment -= N-val_;           // add enough to make val_ == N
~= 0
      val_ = 0;
    }
    val_ = (val_ + increment) % N;
  }

  void rightshift() { val_ /= 2;}
  void leftshift() {
    const bool overflow = (val_ > UINT_MAX/2);
    val_ *= 2;
    val_ %= N;
    if(overflow) *this += modint(overflowmod_);
  }

  unsigned val() const { return val_;}
  modint(unsigned x) : val_(x % N) {}
};

template <unsigned N>
modint<N> modint<N>::overflowmod_ = (1 + (UINT_MAX % N));

// peasants arithmetic, mod N
template <unsigned N>
modint<N> operator*(modint<N> r1,modint<N> r2)
{
  modint<N> tot = 0;
  while(r2.val() != 0){
    if(r2.val() % 2 == 1) {
      tot += r1;
    }
    r2.rightshift();
    r1.leftshift();
  }
  return tot;
}
#endif

[test program]

#include <iostream>
#include "modint.hpp"

int main(void)
{
  const unsigned BIGVAL = 0xFFFFFFFF;
  modint<BIGVAL> a = BIGVAL-3, b =  BIGVAL-9;

  std::cout << a.val() << " " << b.val() << std::endl;
  std::cout << (a * b).val() << std::endl;
}

-----------------------------------------------------------

How is this used?

With the expression (a*b)% B^N

Is BIGVAL N or 10^N?

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

#7124

In case this hasn't been mentioned already (I just skimmed this
thread):

  (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.

Cheers!
SG

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

#7125

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;

-- 
  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]

#7129

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:

    (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.

That said, a version of double-and-add for modulo arithmetic has been 
proposed elsethread; and that version at least did assume that 2*(a%B) does 
not overflow.


Best,

Kai-Uwe Bux

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

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

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

#7134

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.


Best,

Kai-Uwe Bux

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

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

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

#7141

"Pete Becker" <pete@versatilecoding.com> wrote in message 
news:2011062416262439377-pete@versatilecodingcom...
> 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.
>
>

Firstly I'm sorry to see that Pete has spat the dummy out.

Secondly I have found another solution to the given problem, for unsigned 
integers only.
Multiplication of two matrices where:
m1 == size of smallest int (number of decimal digits).
m2 == size of largest int + (size of smallest int -1) x size of smallest 
int.

For example with 43296x21 we would multiply:
6 0
9 6
2 9   [6x2 array.]
3 2
4 3
0 4
multiplied by....
1
2  [2x1 array]

The resulting array would be a 6x1 array containing:
[6 21 20 7 10 8]

Which we would then simply loop through taking modulo and carrying result.
I don't feel too well tonight so early to bed for me, I may do an algorithm 
for this tomorrow if I feel better.

Note: m1*m2 != m2*m1.
HTH.

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

#7158

"Paul" <pchristor@yahoo.co.uk> wrote in message 
news:wkbNp.27837$nY6.17449@newsfe23.ams2...
>
> "Pete Becker" <pete@versatilecoding.com> wrote in message 
> news:2011062416262439377-pete@versatilecodingcom...
>> 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.
>>
>>
>
> Firstly I'm sorry to see that Pete has spat the dummy out.
>
> Secondly I have found another solution to the given problem, for unsigned 
> integers only.
> Multiplication of two matrices where:
> m1 == size of smallest int (number of decimal digits).
> m2 == size of largest int + (size of smallest int -1) x size of smallest 
> int.
>
> For example with 43296x21 we would multiply:
> 6 0
> 9 6
> 2 9   [6x2 array.]
> 3 2
> 4 3
> 0 4
> multiplied by....
> 1
> 2  [2x1 array]
>
> The resulting array would be a 6x1 array containing:
> [6 21 20 7 10 8]
>
> Which we would then simply loop through taking modulo and carrying result.
> I don't feel too well tonight so early to bed for me, I may do an 
> algorithm for this tomorrow if I feel better.
>
> Note: m1*m2 != m2*m1.
> HTH.
>
>
Ok this seems to do the trick:

#include <iostream>
#include <vector>

typedef unsigned int uint;
typedef std::vector<uint> v_uint;

v_uint int_to_vect(uint arg, uint B=10){
 v_uint retv;
 while(arg){
  retv.push_back(arg%B);
  arg/=B;
 }
 return retv;
}


uint mod_ab(uint a, uint b, uint exp=1, uint B=10){
 v_uint v1= int_to_vect((a>=b)?a:b, B);
 v_uint v2= int_to_vect((a>=b)?b:a, B);
 int v1s= v1.size();
 int v2s= (v2.size())-1;
 uint retv=0;
 uint mult=1;/*Annoying variable*/

 for(int i=v2s; i>0; --i){
  v1.push_back(0);
  v1.insert(v1.begin(), 0);
 }
 v_uint vresult;
 uint temp=0;
 for(int i=0; i<(v1s+v2s) && i<exp; ++i, mult*=B){
  for(int j=v2s; j>=0; --j){
   temp+=v1[i+v2s-j]*v2[j];
  }
  retv += (temp%B)*mult;
  temp = temp/B;
 }
 return retv;
}

int main(){
 uint a=-1, b=-1;
 std::cout<< mod_ab(a,b,3);
}

I haven't fully checked it as I just did it.

One thing that was annoying me was the need for the varaible mult.
All I need it for is to calculate B^i, which I was having problems 
simplifying when i is zero.

I think it works for all bases up to max_value of uint but haven't checked 
all that , it would probably be a good idea to make B unsigned and limit 
that to max_base 255. 

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

#7142

* Kai-Uwe Bux, on 24.06.2011 20:28 -> Pete Becker:
> ... I think your quoting was vicious: it left out a part that is crucial to
> the interpretation of the part that was quoted.

I think the word you're looking may be "inadvertently", not "vicious".


Cheers & hth.,

- Alf

-- 
blog at <url: http://alfps.wordpress.com>

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

#7148

"Kai-Uwe Bux" <jkherciueh@gmx.net> wrote in message 
news:iu2kvq$27a$1@hoshi.visyn.net...
> 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?

My interpretation of that is that it's unproven bullshit.

Lets see this magical "modified double and add algorithm" that, for you, 
solves the problem 

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

#7150

On 25 Jun., 11:12, Paul wrote:
> [...]
> My interpretation of that is that it's unproven bullshit.
>
> Lets see this magical "modified double and add algorithm" that, for you,
> solves the problem

Hmmm. It seems like I expected too much from you guys in terms of
reading comprehension, google skills, and education.

"double and add" for multiplication is the little brother of
"square and multiply" for computing powers.

Here it is:
http://en.wikipedia.org/wiki/Multiplication_algorithm#Shift_and_add

Also, I explained "modified" with a "that includes the mod-reduction"
in my initial post. In case you have no idea what the purpose of this
modification is: It's to avoid _overflows_.

*sigh*

Cheers!
SG

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

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

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

csiph-web