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