From: Alexei Sheplyakov <varg@theor.jinr.ru>
Date: Tue, 14 Oct 2008 06:37:42 +0000 (+0400)
Subject: mod_gcd: naive hack to chose a 'good' prime (to speed up gcd computation).
X-Git-Tag: release_1-5-0~55
X-Git-Url: https://www.ginac.de/ginac.git//ginac.git?p=ginac.git;a=commitdiff_plain;h=55fcb39a1209898ec43694f7e25ffb4572b0c4d1;hp=62923ac249c7e4f7e824bc37030ac79bab3675f3;ds=sidebyside

mod_gcd: naive hack to chose a 'good' prime (to speed up gcd computation).
---

diff --git a/ginac/polynomial/mod_gcd.cpp b/ginac/polynomial/mod_gcd.cpp
index 8aa84808..82d5f427 100644
--- a/ginac/polynomial/mod_gcd.cpp
+++ b/ginac/polynomial/mod_gcd.cpp
@@ -104,8 +104,18 @@ void mod_gcd(upoly& result, upoly A, upoly B)
 	ring_t q(0);
 	upoly H;
 
-	ring_t p(2);
+	int count = 0;
+	const ring_t p_threshold = ring_t(1) << (8*sizeof(void *));
+	ring_t p = isqrt(std::min(max_coeff(A), max_coeff(B)));
 	while (true) {
+		if (count >= 8) {
+			count = 0;
+			if (p < p_threshold)
+				p <<= 1;
+			else
+				p = p + (p >> 4);
+		} else 
+			++count;
 		find_next_prime(p, g);
 
 		// Map the polynomials onto Z/p[x]