Finding a billion factorials in 60 ms with SIMD
codeforces.com
Finding a billion factorials in 60 ms with SIMD
1–10 of 17 posts
Re: Finding a billion factorials in 60 ms with SIMD
#2It's interesting to see which codeforces blog posts get traction on HN.
For context, in competitive programming a lot of combinatorial problems (find some formula to count something) require you to output the answer modulo some prime. This is because otherwise the answer would overflow an int and make the problem too tedious to be fun and too hard for problem setters to write good problems or checkers for.
So to prove that you still know how to count the thing, you can do it a finite field. If you use integers mod prime, you still have all the usual arithmetic operations like addition subtraction multiplication. And even division is still easy since you can calculate multiplicative inverse with Fermat's Little Theorem (a^(p-2) = a^(-1) mod p). The final answer you output is not the real thing you're counting, but just evidence that you had the right formula and did all the right operations.
Anyway, just wanted to give context for why competitive programmers care about factorial mod a prime (usually as part of a binomial or multinomial expression). And I'm kind of surprised anyone outside of competitive programming cares about it.
See also:
Re: Finding a billion factorials in 60 ms with SIMD
#3Since we are talking factorials, i wanted to ask. What is the largest factorial that the biggest supercomputer known to man has computed? how long did it take
Re: Finding a billion factorials in 60 ms with SIMD
#4Since we are talking factorials, i wanted to ask. What is the largest factorial that the biggest supercomputer known to man has computed? how long did it take
probably not very big. factorials are pretty boring in the sense that it's relatively trivial to compute a factorial almost as big as your hard drive. 99% of the time will happen in a single multiply
Re: Finding a billion factorials in 60 ms with SIMD
#5It's interesting to see which codeforces blog posts get traction on HN. For context, in competitive programming a lot of combinatorial problems (find some formula to count something) require you to output the answer modulo some prime. This is because otherwise the answer would overflow an int and make the problem too tedious to be fun and too hard for problem setters to write good problems or checkers for. So to prov…
> a^(p-2) = a^(-1) mod p
Tangent, but curious: what made you write it like this? I've only ever seen it written as
a^(p-1) = 1 mod p
a^p = a mod p
Re: Finding a billion factorials in 60 ms with SIMD
#6It's interesting to see which codeforces blog posts get traction on HN. For context, in competitive programming a lot of combinatorial problems (find some formula to count something) require you to output the answer modulo some prime. This is because otherwise the answer would overflow an int and make the problem too tedious to be fun and too hard for problem setters to write good problems or checkers for. So to prov…
> a^(p-2) = a^(-1) mod p Tangent, but curious: what made you write it like this? I've only ever seen it written as a^(p-1) = 1 mod p or a^p = a mod p Is that form somehow more useful in some cases?
a^(-1) mod p is the multiplicative inverse in a finite field. The point of the original comment was to show how to transform the multiplicative inverse into an easier problem.
Re: Finding a billion factorials in 60 ms with SIMD
#7Since we are talking factorials, i wanted to ask. What is the largest factorial that the biggest supercomputer known to man has computed? how long did it take
probably not very big. factorials are pretty boring in the sense that it's relatively trivial to compute a factorial almost as big as your hard drive. 99% of the time will happen in a single multiply
99% of the time will happen in a single multiply
Far from it. Asymptotically it's a proportion 2/log(N) of the compute cost.
Re: Finding a billion factorials in 60 ms with SIMD
#8Earlier quoted context omitted.
> a^(p-2) = a^(-1) mod p Tangent, but curious: what made you write it like this? I've only ever seen it written as a^(p-1) = 1 mod p or a^p = a mod p Is that form somehow more useful in some cases?
a^(-1) mod p is the multiplicative inverse in a finite field. The point of the original comment was to show how to transform the multiplicative inverse into an easier problem.
Just what do you think the running time of modular inverse is?
Re: Finding a billion factorials in 60 ms with SIMD
#9Re: Finding a billion factorials in 60 ms with SIMD
#10It's interesting to see which codeforces blog posts get traction on HN. For context, in competitive programming a lot of combinatorial problems (find some formula to count something) require you to output the answer modulo some prime. This is because otherwise the answer would overflow an int and make the problem too tedious to be fun and too hard for problem setters to write good problems or checkers for. So to prov…
> a^(p-2) = a^(-1) mod p Tangent, but curious: what made you write it like this? I've only ever seen it written as a^(p-1) = 1 mod p or a^p = a mod p Is that form somehow more useful in some cases?
It's easier to write code for efficiently computing the inverse in that form, roughly:
int FastExp(int a, int e, int p)
{
if (e == 0) return 1;
if (e == 1) return a;
if (e % 2 == 0) return FastExp((a*a)%p, e/2, p);
else return a * FastExp((a*a)%p, e/2, p);
}