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 --- content/math/squfof.cpp | 89 +++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 89 insertions(+) create mode 100644 content/math/squfof.cpp (limited to 'content/math/squfof.cpp') diff --git a/content/math/squfof.cpp b/content/math/squfof.cpp new file mode 100644 index 0000000..1cb97de --- /dev/null +++ b/content/math/squfof.cpp @@ -0,0 +1,89 @@ +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