Mixing
Get the floor value under modular division for very large number.
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
I have got 3 numbers a,b and m(m is prime). a is very very large(around 10^10^5). I have to calculate (floor(a/b))%m. Since a is very large, so I have stored 'a' as string then calculated value of a under mod m using code below:
long long int len = a.length();
long long int ans=0;
for(long long int i = 0; i<len;i++)
ans=(ans*10 + (a[i]-'0'))%m;
return ans;
Then I simply multiplied above value with the multiplicative mod inverse of b(I have calculated multiplicative mod inverse of b using fermat's little theorem.)
But this is not the desired answer. This will give me exact value of (a/b)%m. But I have to calculate (floor(a/b))%m.
Example: a=7, b=2 and m=5. Since a can be very very large(10^10^5), I just cant store 'a' directly. I must store it under mod m. So now a becomes 2(7%5 = 2).
Now I perform (a/b)%m=(2/2)%5 = 1.
But my actual answer should have(floor(7/2)%5)=3%5=3.
I am stuck here. Can anyone help me to get the desired answer.
number-theory modular-arithmetic
asked Jul 25 at 17:27
Devendra Verma
1064
 |Â
show 15 more comments
up vote
0
down vote
favorite
I have got 3 numbers a,b and m(m is prime). a is very very large(around 10^10^5). I have to calculate (floor(a/b))%m. Since a is very large, so I have stored 'a' as string then calculated value of a under mod m using code below:
long long int len = a.length();
long long int ans=0;
for(long long int i = 0; i<len;i++)
ans=(ans*10 + (a[i]-'0'))%m;
return ans;
Then I simply multiplied above value with the multiplicative mod inverse of b(I have calculated multiplicative mod inverse of b using fermat's little theorem.)
But this is not the desired answer. This will give me exact value of (a/b)%m. But I have to calculate (floor(a/b))%m.
Example: a=7, b=2 and m=5. Since a can be very very large(10^10^5), I just cant store 'a' directly. I must store it under mod m. So now a becomes 2(7%5 = 2).
Now I perform (a/b)%m=(2/2)%5 = 1.
But my actual answer should have(floor(7/2)%5)=3%5=3.
I am stuck here. Can anyone help me to get the desired answer.
number-theory modular-arithmetic
asked Jul 25 at 17:27
Devendra Verma
1064
Could you explain what is happening in your for-loop?
– gd1035
Jul 25 at 17:33
$b^-1(10a_1 + a_0) mod m = 10a_1b^-1 + a_1b^-1 mod m = (10a_1bmod m) + (a_1b mod m)$. So why not just multiply by the mod inverse as you go along?
– fleablood
Jul 25 at 17:35
1
How can it "give me exact value of(a/b)%m" whenbdoes not appear in the code?
– Weather Vane
Jul 25 at 17:36
I don't think the question has anything to do with the multiplicative inverse of $bpmod m$. With $m=29,b=13,a=17$, it is clear that $lfloor frac abrfloor =1$. But the multiplicative inverse of $13pmod 29$ is $9$, so you'd get $17times 9 equiv 8 pmod 29$. No connection.
– lulu
Jul 25 at 17:37
1
You get a different answer because your computation is unrelated to the given problem.
– lulu
Jul 25 at 17:45
 |Â
show 15 more comments
up vote
0
down vote
favorite
up vote
0
down vote
favorite
I have got 3 numbers a,b and m(m is prime). a is very very large(around 10^10^5). I have to calculate (floor(a/b))%m. Since a is very large, so I have stored 'a' as string then calculated value of a under mod m using code below:
long long int len = a.length();
long long int ans=0;
for(long long int i = 0; i<len;i++)
ans=(ans*10 + (a[i]-'0'))%m;
return ans;
Then I simply multiplied above value with the multiplicative mod inverse of b(I have calculated multiplicative mod inverse of b using fermat's little theorem.)
But this is not the desired answer. This will give me exact value of (a/b)%m. But I have to calculate (floor(a/b))%m.
Example: a=7, b=2 and m=5. Since a can be very very large(10^10^5), I just cant store 'a' directly. I must store it under mod m. So now a becomes 2(7%5 = 2).
Now I perform (a/b)%m=(2/2)%5 = 1.
But my actual answer should have(floor(7/2)%5)=3%5=3.
I am stuck here. Can anyone help me to get the desired answer.
number-theory modular-arithmetic
asked Jul 25 at 17:27
Devendra Verma
1064
I have got 3 numbers a,b and m(m is prime). a is very very large(around 10^10^5). I have to calculate (floor(a/b))%m. Since a is very large, so I have stored 'a' as string then calculated value of a under mod m using code below:
long long int len = a.length();
long long int ans=0;
for(long long int i = 0; i<len;i++)
ans=(ans*10 + (a[i]-'0'))%m;
return ans;
Then I simply multiplied above value with the multiplicative mod inverse of b(I have calculated multiplicative mod inverse of b using fermat's little theorem.)
But this is not the desired answer. This will give me exact value of (a/b)%m. But I have to calculate (floor(a/b))%m.
Example: a=7, b=2 and m=5. Since a can be very very large(10^10^5), I just cant store 'a' directly. I must store it under mod m. So now a becomes 2(7%5 = 2).
Now I perform (a/b)%m=(2/2)%5 = 1.
But my actual answer should have(floor(7/2)%5)=3%5=3.
I am stuck here. Can anyone help me to get the desired answer.
number-theory modular-arithmetic
asked Jul 25 at 17:27
Devendra Verma
1064
edited Jul 25 at 17:51
asked Jul 25 at 17:27
Devendra Verma
1064
asked Jul 25 at 17:27
Devendra Verma
1064
asked Jul 25 at 17:27
Devendra Verma
1064
1064
Could you explain what is happening in your for-loop?
– gd1035
Jul 25 at 17:33
$b^-1(10a_1 + a_0) mod m = 10a_1b^-1 + a_1b^-1 mod m = (10a_1bmod m) + (a_1b mod m)$. So why not just multiply by the mod inverse as you go along?
– fleablood
Jul 25 at 17:35
1
How can it "give me exact value of(a/b)%m" whenbdoes not appear in the code?
– Weather Vane
Jul 25 at 17:36
I don't think the question has anything to do with the multiplicative inverse of $bpmod m$. With $m=29,b=13,a=17$, it is clear that $lfloor frac abrfloor =1$. But the multiplicative inverse of $13pmod 29$ is $9$, so you'd get $17times 9 equiv 8 pmod 29$. No connection.
– lulu
Jul 25 at 17:37
1
You get a different answer because your computation is unrelated to the given problem.
– lulu
Jul 25 at 17:45
 |Â
show 15 more comments
Could you explain what is happening in your for-loop?
– gd1035
Jul 25 at 17:33
$b^-1(10a_1 + a_0) mod m = 10a_1b^-1 + a_1b^-1 mod m = (10a_1bmod m) + (a_1b mod m)$. So why not just multiply by the mod inverse as you go along?
– fleablood
Jul 25 at 17:35
1
How can it "give me exact value of(a/b)%m" whenbdoes not appear in the code?
– Weather Vane
Jul 25 at 17:36
I don't think the question has anything to do with the multiplicative inverse of $bpmod m$. With $m=29,b=13,a=17$, it is clear that $lfloor frac abrfloor =1$. But the multiplicative inverse of $13pmod 29$ is $9$, so you'd get $17times 9 equiv 8 pmod 29$. No connection.
– lulu
Jul 25 at 17:37
1
You get a different answer because your computation is unrelated to the given problem.
– lulu
Jul 25 at 17:45
Could you explain what is happening in your for-loop?
– gd1035
Jul 25 at 17:33
Could you explain what is happening in your for-loop?
– gd1035
Jul 25 at 17:33
$b^-1(10a_1 + a_0) mod m = 10a_1b^-1 + a_1b^-1 mod m = (10a_1bmod m) + (a_1b mod m)$. So why not just multiply by the mod inverse as you go along?
– fleablood
Jul 25 at 17:35
$b^-1(10a_1 + a_0) mod m = 10a_1b^-1 + a_1b^-1 mod m = (10a_1bmod m) + (a_1b mod m)$. So why not just multiply by the mod inverse as you go along?
– fleablood
Jul 25 at 17:35
1
1
How can it "give me exact value of
(a/b)%m" when b does not appear in the code?– Weather Vane
Jul 25 at 17:36
How can it "give me exact value of
(a/b)%m" when b does not appear in the code?– Weather Vane
Jul 25 at 17:36
I don't think the question has anything to do with the multiplicative inverse of $bpmod m$. With $m=29,b=13,a=17$, it is clear that $lfloor frac abrfloor =1$. But the multiplicative inverse of $13pmod 29$ is $9$, so you'd get $17times 9 equiv 8 pmod 29$. No connection.
– lulu
Jul 25 at 17:37
I don't think the question has anything to do with the multiplicative inverse of $bpmod m$. With $m=29,b=13,a=17$, it is clear that $lfloor frac abrfloor =1$. But the multiplicative inverse of $13pmod 29$ is $9$, so you'd get $17times 9 equiv 8 pmod 29$. No connection.
– lulu
Jul 25 at 17:37
1
1
You get a different answer because your computation is unrelated to the given problem.
– lulu
Jul 25 at 17:45
You get a different answer because your computation is unrelated to the given problem.
– lulu
Jul 25 at 17:45
 |Â
show 15 more comments
2 Answers
2
active
oldest
votes
up vote
2
down vote
I would store the numbers as arrays of $1$s and $0$s in binary. If $a$ is of order $10^10^5$ that is only about $300,000$ words of memory. You need to write a function that divides two numbers of this type. The neat thing is that if $b$ is $n$ bits long, you just need to see if $b$ is greater than or less than the first $n$ bits of $a$. If it is, write down a $1$ in the answer and subtract $b$ from $a$. If not, it will be less than the first $n+1$ bits of $a$, so write a $01$ and subtract $b$ again. Once you have subtracted $b$, write as many $0$s as needed to get back to $n$ bits of what is left of $a$. We are implementing binary long division. When $b$ is greater than the rest of $a$ quit and you have $lfloor frac ab rfloor=c$. Now you take $c$ and divide it by $m$ the same way, but you keep the remainder instead of the quotient.
Of course, you can handle much larger numbers if you store as ints instead of bits, but the programming will be harder.
answered Jul 25 at 17:54
Ross Millikan
275k21186351
Oh my goodness. Such a brilliant idea to store 'a' as binary. Salute to you. I think this might should work. I will try this and let you know if this works.
– Devendra Verma
Jul 25 at 18:01
There's no need to reinvent the wheel when it comes to bignum math. Anyways I think storing as bool instead of int is faster since I/O may be the bottleneck here (also depends on CPU arch)
– qwr
Jul 25 at 18:02
@qwr: Yes, I would just use a canned package, but I didn't think that was the spirit of the question. I have reinvented the wheel in Excel when I wanted numbers twice as long as it provides and didn't want to give up the other features it provides.
– Ross Millikan
Jul 25 at 18:07
Actually I was in programming contest and I cant use any third party libraries.
– Devendra Verma
Jul 25 at 18:09
add a comment |Â
up vote
0
down vote
There is no need to manually use binary arrays. Use GMP Bignum Library and it will handle everything for you. This comes out to roughly 300,000 bits or 41 kB which a computer can handle easily. Even Python and Mathematica can handle these quantities. Ex.
>>> 10**(10**5) // 7**12345
answered Jul 25 at 17:59
qwr
6,58532654
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
I would store the numbers as arrays of $1$s and $0$s in binary. If $a$ is of order $10^10^5$ that is only about $300,000$ words of memory. You need to write a function that divides two numbers of this type. The neat thing is that if $b$ is $n$ bits long, you just need to see if $b$ is greater than or less than the first $n$ bits of $a$. If it is, write down a $1$ in the answer and subtract $b$ from $a$. If not, it will be less than the first $n+1$ bits of $a$, so write a $01$ and subtract $b$ again. Once you have subtracted $b$, write as many $0$s as needed to get back to $n$ bits of what is left of $a$. We are implementing binary long division. When $b$ is greater than the rest of $a$ quit and you have $lfloor frac ab rfloor=c$. Now you take $c$ and divide it by $m$ the same way, but you keep the remainder instead of the quotient.
Of course, you can handle much larger numbers if you store as ints instead of bits, but the programming will be harder.
answered Jul 25 at 17:54
Ross Millikan
275k21186351
Oh my goodness. Such a brilliant idea to store 'a' as binary. Salute to you. I think this might should work. I will try this and let you know if this works.
– Devendra Verma
Jul 25 at 18:01
There's no need to reinvent the wheel when it comes to bignum math. Anyways I think storing as bool instead of int is faster since I/O may be the bottleneck here (also depends on CPU arch)
– qwr
Jul 25 at 18:02
@qwr: Yes, I would just use a canned package, but I didn't think that was the spirit of the question. I have reinvented the wheel in Excel when I wanted numbers twice as long as it provides and didn't want to give up the other features it provides.
– Ross Millikan
Jul 25 at 18:07
Actually I was in programming contest and I cant use any third party libraries.
– Devendra Verma
Jul 25 at 18:09
add a comment |Â
up vote
2
down vote
I would store the numbers as arrays of $1$s and $0$s in binary. If $a$ is of order $10^10^5$ that is only about $300,000$ words of memory. You need to write a function that divides two numbers of this type. The neat thing is that if $b$ is $n$ bits long, you just need to see if $b$ is greater than or less than the first $n$ bits of $a$. If it is, write down a $1$ in the answer and subtract $b$ from $a$. If not, it will be less than the first $n+1$ bits of $a$, so write a $01$ and subtract $b$ again. Once you have subtracted $b$, write as many $0$s as needed to get back to $n$ bits of what is left of $a$. We are implementing binary long division. When $b$ is greater than the rest of $a$ quit and you have $lfloor frac ab rfloor=c$. Now you take $c$ and divide it by $m$ the same way, but you keep the remainder instead of the quotient.
Of course, you can handle much larger numbers if you store as ints instead of bits, but the programming will be harder.
answered Jul 25 at 17:54
Ross Millikan
275k21186351
Oh my goodness. Such a brilliant idea to store 'a' as binary. Salute to you. I think this might should work. I will try this and let you know if this works.
– Devendra Verma
Jul 25 at 18:01
There's no need to reinvent the wheel when it comes to bignum math. Anyways I think storing as bool instead of int is faster since I/O may be the bottleneck here (also depends on CPU arch)
– qwr
Jul 25 at 18:02
@qwr: Yes, I would just use a canned package, but I didn't think that was the spirit of the question. I have reinvented the wheel in Excel when I wanted numbers twice as long as it provides and didn't want to give up the other features it provides.
– Ross Millikan
Jul 25 at 18:07
Actually I was in programming contest and I cant use any third party libraries.
– Devendra Verma
Jul 25 at 18:09
add a comment |Â
up vote
2
down vote
up vote
2
down vote
I would store the numbers as arrays of $1$s and $0$s in binary. If $a$ is of order $10^10^5$ that is only about $300,000$ words of memory. You need to write a function that divides two numbers of this type. The neat thing is that if $b$ is $n$ bits long, you just need to see if $b$ is greater than or less than the first $n$ bits of $a$. If it is, write down a $1$ in the answer and subtract $b$ from $a$. If not, it will be less than the first $n+1$ bits of $a$, so write a $01$ and subtract $b$ again. Once you have subtracted $b$, write as many $0$s as needed to get back to $n$ bits of what is left of $a$. We are implementing binary long division. When $b$ is greater than the rest of $a$ quit and you have $lfloor frac ab rfloor=c$. Now you take $c$ and divide it by $m$ the same way, but you keep the remainder instead of the quotient.
Of course, you can handle much larger numbers if you store as ints instead of bits, but the programming will be harder.
answered Jul 25 at 17:54
Ross Millikan
275k21186351
I would store the numbers as arrays of $1$s and $0$s in binary. If $a$ is of order $10^10^5$ that is only about $300,000$ words of memory. You need to write a function that divides two numbers of this type. The neat thing is that if $b$ is $n$ bits long, you just need to see if $b$ is greater than or less than the first $n$ bits of $a$. If it is, write down a $1$ in the answer and subtract $b$ from $a$. If not, it will be less than the first $n+1$ bits of $a$, so write a $01$ and subtract $b$ again. Once you have subtracted $b$, write as many $0$s as needed to get back to $n$ bits of what is left of $a$. We are implementing binary long division. When $b$ is greater than the rest of $a$ quit and you have $lfloor frac ab rfloor=c$. Now you take $c$ and divide it by $m$ the same way, but you keep the remainder instead of the quotient.
Of course, you can handle much larger numbers if you store as ints instead of bits, but the programming will be harder.
answered Jul 25 at 17:54
Ross Millikan
275k21186351
answered Jul 25 at 17:54
Ross Millikan
275k21186351
answered Jul 25 at 17:54
Ross Millikan
275k21186351
answered Jul 25 at 17:54
Ross Millikan
275k21186351
275k21186351
Oh my goodness. Such a brilliant idea to store 'a' as binary. Salute to you. I think this might should work. I will try this and let you know if this works.
– Devendra Verma
Jul 25 at 18:01
There's no need to reinvent the wheel when it comes to bignum math. Anyways I think storing as bool instead of int is faster since I/O may be the bottleneck here (also depends on CPU arch)
– qwr
Jul 25 at 18:02
@qwr: Yes, I would just use a canned package, but I didn't think that was the spirit of the question. I have reinvented the wheel in Excel when I wanted numbers twice as long as it provides and didn't want to give up the other features it provides.
– Ross Millikan
Jul 25 at 18:07
Actually I was in programming contest and I cant use any third party libraries.
– Devendra Verma
Jul 25 at 18:09
add a comment |Â
Oh my goodness. Such a brilliant idea to store 'a' as binary. Salute to you. I think this might should work. I will try this and let you know if this works.
– Devendra Verma
Jul 25 at 18:01
There's no need to reinvent the wheel when it comes to bignum math. Anyways I think storing as bool instead of int is faster since I/O may be the bottleneck here (also depends on CPU arch)
– qwr
Jul 25 at 18:02
@qwr: Yes, I would just use a canned package, but I didn't think that was the spirit of the question. I have reinvented the wheel in Excel when I wanted numbers twice as long as it provides and didn't want to give up the other features it provides.
– Ross Millikan
Jul 25 at 18:07
Actually I was in programming contest and I cant use any third party libraries.
– Devendra Verma
Jul 25 at 18:09
Oh my goodness. Such a brilliant idea to store 'a' as binary. Salute to you. I think this might should work. I will try this and let you know if this works.
– Devendra Verma
Jul 25 at 18:01
Oh my goodness. Such a brilliant idea to store 'a' as binary. Salute to you. I think this might should work. I will try this and let you know if this works.
– Devendra Verma
Jul 25 at 18:01
There's no need to reinvent the wheel when it comes to bignum math. Anyways I think storing as bool instead of int is faster since I/O may be the bottleneck here (also depends on CPU arch)
– qwr
Jul 25 at 18:02
There's no need to reinvent the wheel when it comes to bignum math. Anyways I think storing as bool instead of int is faster since I/O may be the bottleneck here (also depends on CPU arch)
– qwr
Jul 25 at 18:02
@qwr: Yes, I would just use a canned package, but I didn't think that was the spirit of the question. I have reinvented the wheel in Excel when I wanted numbers twice as long as it provides and didn't want to give up the other features it provides.
– Ross Millikan
Jul 25 at 18:07
@qwr: Yes, I would just use a canned package, but I didn't think that was the spirit of the question. I have reinvented the wheel in Excel when I wanted numbers twice as long as it provides and didn't want to give up the other features it provides.
– Ross Millikan
Jul 25 at 18:07
Actually I was in programming contest and I cant use any third party libraries.
– Devendra Verma
Jul 25 at 18:09
Actually I was in programming contest and I cant use any third party libraries.
– Devendra Verma
Jul 25 at 18:09
add a comment |Â
up vote
0
down vote
There is no need to manually use binary arrays. Use GMP Bignum Library and it will handle everything for you. This comes out to roughly 300,000 bits or 41 kB which a computer can handle easily. Even Python and Mathematica can handle these quantities. Ex.
>>> 10**(10**5) // 7**12345
answered Jul 25 at 17:59
qwr
6,58532654
add a comment |Â
up vote
0
down vote
There is no need to manually use binary arrays. Use GMP Bignum Library and it will handle everything for you. This comes out to roughly 300,000 bits or 41 kB which a computer can handle easily. Even Python and Mathematica can handle these quantities. Ex.
>>> 10**(10**5) // 7**12345
answered Jul 25 at 17:59
qwr
6,58532654
add a comment |Â
up vote
0
down vote
up vote
0
down vote
There is no need to manually use binary arrays. Use GMP Bignum Library and it will handle everything for you. This comes out to roughly 300,000 bits or 41 kB which a computer can handle easily. Even Python and Mathematica can handle these quantities. Ex.
>>> 10**(10**5) // 7**12345
answered Jul 25 at 17:59
qwr
6,58532654
There is no need to manually use binary arrays. Use GMP Bignum Library and it will handle everything for you. This comes out to roughly 300,000 bits or 41 kB which a computer can handle easily. Even Python and Mathematica can handle these quantities. Ex.
>>> 10**(10**5) // 7**12345
answered Jul 25 at 17:59
qwr
6,58532654
answered Jul 25 at 17:59
qwr
6,58532654
answered Jul 25 at 17:59
qwr
6,58532654
answered Jul 25 at 17:59
qwr
6,58532654
6,58532654
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2862641%2fget-the-floor-value-under-modular-division-for-very-large-number%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Could you explain what is happening in your for-loop?
– gd1035
Jul 25 at 17:33
$b^-1(10a_1 + a_0) mod m = 10a_1b^-1 + a_1b^-1 mod m = (10a_1bmod m) + (a_1b mod m)$. So why not just multiply by the mod inverse as you go along?
– fleablood
Jul 25 at 17:35
1
How can it "give me exact value of
(a/b)%m" whenbdoes not appear in the code?– Weather Vane
Jul 25 at 17:36
I don't think the question has anything to do with the multiplicative inverse of $bpmod m$. With $m=29,b=13,a=17$, it is clear that $lfloor frac abrfloor =1$. But the multiplicative inverse of $13pmod 29$ is $9$, so you'd get $17times 9 equiv 8 pmod 29$. No connection.
– lulu
Jul 25 at 17:37
1
You get a different answer because your computation is unrelated to the given problem.
– lulu
Jul 25 at 17:45