removed old slow code

4 files changed, 11 insertions, 94 deletions

diff --git a/content/math/math.tex b/content/math/math.tex
index f99d0d4..c15825f 100644
--- a/content/math/math.tex
+++ b/content/math/math.tex
@@ -109,8 +109,6 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 	\sourcecode{math/millerRabin.cpp}

 	\method{rho}{findet zufälligen Teiler}{\sqrt[\leftroot{3}\uproot{2}4]{n}}

 	\sourcecode{math/rho.cpp}

-	%\method{squfof}{findet zufälligen Teiler}{\sqrt[\leftroot{4}\uproot{2}4]{n}}

-	%\sourcecode{math/squfof.cpp}

 \end{algorithm}

 

 \begin{algorithm}{Teiler}

diff --git a/content/math/squfof.cpp b/content/math/squfof.cpp
deleted file mode 100644
index 1cb97de..0000000
--- a/content/math/squfof.cpp
+++ /dev/null
@@ -1,89 +0,0 @@
-using lll = __int128;

-

-constexpr lll multipliers[] = {1, 3, 5, 7,

-                               11, 3*5, 3*7, 3*11,

-                               5*7, 5*11, 7*11,

-                               3*5*7, 3*5*11, 3*7*11,

-                               5*7*11, 3*5*7*11};

-

-lll root(lll x) {

-	lll r = sqrtl(x);

-	while(r*r < x) r++;

-	while(r*r > x) r--;

-	return r;

-}

-

-lll croot(lll x) {

-	lll r = cbrtl(x);

-	while(r*r*r < x) r++;

-	while(r*r*r > x) r--;

-	return r;

-}

-

-lll squfof(lll N) {

-	lll s = croot(N);

-	if (s*s*s == N) return s;

-	s = root(N);

-	if (s*s == N) return s;

-	for (lll k : multipliers) {

-		lll D = k * N;

-		lll Po, P, Pprev, q, b, r, i;

-		Po = Pprev = P = root(D);

-		lll Qprev = 1;

-		lll Q = D - Po*Po;

-		lll L = 2 * root(2 * s);

-		lll B = 3 * L;

-		for (i = 2; i < B; i++) {

-			b = (Po + P) / Q;

-			P = b*Q - P;

-			q = Q;

-			Q = Qprev + b * (Pprev - P);

-			r = root(Q);

-			if (!(i & 1) && r*r == Q) break;

-			Qprev = q;

-			Pprev = P;

-		}

-		if (i >= B) continue;

-		b = (Po - P) / r;

-		Pprev = P = b*r + P;

-		Qprev = r;

-		Q = (D-Pprev*Pprev)/Qprev;

-		i = 0;

-		do {

-			b = (Po + P) / Q;

-			Pprev = P;

-			P = b*Q - P;

-			q = Q;

-			Q = Qprev +	b * (Pprev - P);

-			Qprev = q;

-			i++;

-		} while(P != Pprev);

-		r = gcd(N, Qprev);

-		if (r != 1 && r != N) return r;

-	}

-	exit(1);//try fallback to pollard rho

-}

-

-constexpr lll trialLim = 5'000;

-

-void factor(lll n, map<lll, int>& facts) {

-	for (lll i = 2; i * i <= n && i <= trialLim; i++) {

-		while (n % i == 0) {

-			facts[i]++;

-			n /= i;

-	}}

-	if (n > 1 && n < trialLim * trialLim) {

-		facts[n]++;

-	} else {

-		vector<lll> todo = {n};

-		while (!todo.empty()) {

-			lll c = todo.back();

-			todo.pop_back();

-			if (c == 1) continue;

-			if (isPrime(c)) {

-				facts[c]++;

-			} else {

-				lll d = squfof(c);

-				todo.push_back(d);

-				todo.push_back(c / d);

-}}}}

diff --git a/tcr.pdf b/tcr.pdf
index 6cfe7d1..608476d 100644
--- a/tcr.pdf
+++ b/tcr.pdf
diff --git a/test/math/rho.cpp b/test/math/rho.cpp
index 5e4792a..941524b 100644
--- a/test/math/rho.cpp
+++ b/test/math/rho.cpp
@@ -96,17 +96,25 @@ void stress_test() {
 	cerr << "stress tested: " << t.time << "ms" << endl;
 }
 
-constexpr int N = 2'000;
+ll randomHard(ll lim) {
+	ll root2 = sqrt(lim);
+	ll root3 = cbrt(lim);
+	ll a = Random::prime<ll>(root2 / 2 - root3, root2 / 2 + root3);
+	ll b = Random::prime<ll>(lim / a - root3, lim / a);
+	return a * b;
+}
+
+constexpr int N = 200;
 void performance_test() {
 	timer t;
 	hash_t hash = 0;
 	for (int operations = 0; operations < N; operations++) {
-		ll x = Random::integer<ll>(1e18 / 2, 1e18);
+		ll x = randomHard(1e18);
 		t.start();
 		hash += factor(x).size();
 		t.stop();
 	}
-	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	if (t.time > 750) cerr << "too slow: " << t.time << FAIL;
 	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
 }