From ef95a81b809ec6fcaf53a870f7bc86bf613b42f8 Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Tue, 30 Jul 2024 15:57:54 +0200
Subject: removed old slow code

---
 content/math/math.tex   |  2 --
 content/math/squfof.cpp | 89 -------------------------------------------------
 2 files changed, 91 deletions(-)
 delete mode 100644 content/math/squfof.cpp

(limited to 'content')

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);
-}}}}
-- 
cgit v1.2.3