Re: (simple?) problem with multiplication
"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.