(simple?) problem with multiplication

[Ttodir]

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.

 

[Ttodir]

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)

 

[Balog Pal]

no types larger than int can be used.

why?

 

[Christopher]

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.

 

[Anonymous]

Balog Pal ha scritto:

why?

because a possible extension in the future will be to declare the
variables long long instead of int

 

[Ttodir]

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

 

[Gido]

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;

 

[Anonymous]

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;
}

 

[Anonymous]

Gido ha scritto:

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

 

[Kai-Uwe Bux]

Ttodir ha scritto:

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

 

[Rune Allnor]

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

 

[Ttodir]

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.

 

[gwowen]

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.

 

[Dilip]

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.

 

[Paul]

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 << std::endl;
}

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

}

 

[Juha Nieminen]

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

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

 

[gwowen]

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

 

[gwowen]

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

 

[Paul]

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?

 

[Paul]

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?