?gcd(x c y , z)

can we find the value of gcd(x c y , z) easily and very fast using a computer.

where
1. "c" represents "combinations" used in 'permutations and combinations'.
2. x is very very large number (ex: may be of 100 or 1000 numerical digits)
3. y is also large having 2 to 5 digits less than x.
4. z is also large having the same number of digits as x.

 

Log in or Sign up to hide all adverts.

This is closely related to the roots of the wtf(x) function, and if often but erroneously related to the stfu(x) function.

 

Log in or Sign up to hide all adverts.

\(\textrm{gcd} \left( \left( { x \\ y } \right) , \, z \right)\) would seem to require on the order of \(y\) operations.

But you can prime factorize \(z = \prod p_i^{e_i}\), then for each prime in this relatively small set, compute the exponent of that prime, \(c_i\), in the prime factorization of \( \left( { x \\ y } \right) \), which can be computed in order \(\ln x\) operations. Then it is a simple matter to compute \(\textrm{gcd} \left( \left( { x \\ y } \right) , \, z \right) = \prod p_i^{\textrm{min}( e_i , c(n, k, p_i))}\).

Code:

binom_prime_exponent ( n, k, prime ) {
	if ( k == 0 || k == n ) return 0;
	if ( 2 * k > n ) {
		k = n - k;
	}

	if ( prime > n - k ) {
		return 1;
	}
	if ( prime * 2 > n ) {
		return 0;
	}
	if ( prime * prime > n ) {
		if ( n % prime < k % prime ) {
			return 1;
		} else {
			return 0;
		}
	}
	n2 = n, k2 = k, c = 0, r = 0;
	while ( n2 >= 1 ) {
		if ( n2 % prime < k2 % prime + r ) {
			r = 1;
			c ++;
		} else {
			r = 0;
		}
		n2 = floor(n2/prime);
		k2 = floor(k2/prime);
	}
	return c;
}

Pseudocode based on http://www.luschny.de/math/factorial/FastBinomialFunction.html but not double-checked.

 

Log in or Sign up to hide all adverts.

Hmm..

It appears you need to add:
if (prime > n) {
return 0;
}
That makes sense.

It would also be nice to add something to throw an exception if n <1, if k<0 or if k > n since even if you define binom(n,k) = 0 for such situations, it's stupid to count the prime factors of 0.

Even for n < 100 and prime < 100, this pseudocode (implemented in Perl) averages about 3 times faster than the naive binomial code (which fails to have enough precision when n > 62 ).