From 8d11c6c8213f46f0fa19826917c255edd5d43cb1 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Sun, 28 Jul 2024 22:54:40 +0200 Subject: Test (#4) * update * moved content in subdir * rename file * add test setup * add test setup * add github action * automaticly test all cpp files * timeout after 10s * setulimit and dont zero memory * test build pdf * install latexmk * update * update * ngerman * fonts * removed old code * add first test * added tests * test in sorted order * more tests * simplified test * more tests * fix suffix tree * fixes and improvements * done ust lst directly * fix swap * add links to pdf * fix constants * add primorial * add comment * various improvements * more tests * added missing stuf * more tests * fix tests * more tests * more tests * more tests * fix recursion? * test trie * more tests * only use python temporarily for listings * only use python temporarily for listings * more tests * fix longestCommonSubstring * more tests * more tests * made code more similiar * fix? * more tests * more tests * more tests * add ahoCorasick test + limit 4GB stack size * more tests * fix test * add additional test * more tests * more tests * fix? * better fix * fix virtual tree * more tests * more tests * recursive closest pair * more tests * decrease limit * new tests * more tests * fix name * more tests * add test * new test * more tests * more tests * more tests * more tests * new test and content * new code * new code * larger tests * fix and test * new test * new test * update pdf * remove comments * new test * more tests * more testcases * more tests * increased limit * more tests * more tests * more tests * new tests * more tests * shortened code * new test * add basic tests for bigint * more tests * removed old files * new test * ignore some files * more auto more ccw * fix test * more tests * fix * new tests * more tests * more tests * stronger test * actually verify delaunay... * more tests * fix header * more tests * run tests parallel? * test parralel? * add --missing * separate workflows * test * is the pdf checked? * separate workflows * fix workflow * more workflows --------- Co-authored-by: Yidi --- math/squfof.cpp | 89 --------------------------------------------------------- 1 file changed, 89 deletions(-) delete mode 100644 math/squfof.cpp (limited to 'math/squfof.cpp') diff --git a/math/squfof.cpp b/math/squfof.cpp deleted file mode 100644 index 1cb97de..0000000 --- a/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& 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 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