diff options
| author | mzuenni <mzuenni@users.noreply.github.com> | 2024-07-28 22:54:40 +0200 |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2024-07-28 22:54:40 +0200 |
| commit | 8d11c6c8213f46f0fa19826917c255edd5d43cb1 (patch) | |
| tree | 96d75baff33d5a04b5a60f1a41f514a26c716874 /math/squfof.cpp | |
| parent | 8c33b4e0d3030cfed17fc64b4fe41133339f6d87 (diff) | |
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 <noob999noob999@gmail.com>
Diffstat (limited to 'math/squfof.cpp')
| -rw-r--r-- | math/squfof.cpp | 89 |
1 files changed, 0 insertions, 89 deletions
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<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);
-}}}}
|