New pages

(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)

• 10:39, 15 February 2023 ‎Rosenkrantz; D. J.; Stearns; R. E.; Lewis; P. M. (Approximate TSP The Traveling-Salesman Problem) (hist | edit) ‎[449 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{2})$ == Space Complexity == $O({1})$ words (Derived: Nearest neighbor search can be done with constant auxiliary space) == Description == Nearest neighbor search == Approximate? == Approximate Approximation Factor: 1/2\log n + 1/2 == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1974 == Reference == https://link.springer.com/chapter/10.1007/978-1-4020-9688-4_3")
• 10:39, 15 February 2023 ‎Gutina; Gregory; Yeob; Anders; Zverovich; Alexey ( The Traveling-Salesman Problem) (hist | edit) ‎[394 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == - == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2002 == Reference == https://www.researchgate.net/publication/222408030_Traveling_Salesman_Should_not_be_Greedy_Domination_Analysis_of_Greedy-Type_Heuristics_for_the_TSP")
• 10:39, 15 February 2023 ‎Johnson; D. S.; McGeoch; L. A. ( The Traveling-Salesman Problem) (hist | edit) ‎[343 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^{(p(n)$}) == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 1997 == Reference == http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.92.1635&rep=rep1&type=pdf")
• 10:39, 15 February 2023 ‎Applegate et al. (Approximate TSP The Traveling-Salesman Problem) (hist | edit) ‎[296 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{2} E)$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2006 == Reference == https://www.jstor.org/stable/j.ctt7s8xg")
• 10:39, 15 February 2023 ‎Arbitrator solution (Dining Philosophers Problem Deadlock Avoidance) (hist | edit) ‎[356 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O({1})$ (adding 1 arbitrator, which is of constant size) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1965 == Reference == https://en.wikipedia.org/wiki/Dining_philosophers_problem#Arbitrator_solution")
• 10:39, 15 February 2023 ‎Resource hierarchy solution (Dining Philosophers Problem Deadlock Avoidance) (hist | edit) ‎[362 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O(n)$ (each fork has a mutex and there are O(n) forks) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1965 == Reference == https://en.wikipedia.org/wiki/Dining_philosophers_problem#Resource_hierarchy_solution")
• 10:39, 15 February 2023 ‎HJLS algorithm ( Integer Relation) (hist | edit) ‎[574 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3}(n+k)$) == Space Complexity == $O(n^{2})$ -- but requires infinite precision with large n or else it becomes unstable (Derived: Store Gram-Schmidt basis vectors b_i (n n-dimensional vectors) and Gram-Schmidt numbers \mu_{i,j} (i and j both from 1 to n), not sure how to take into account the "bit complexity" part) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == bit...")
• 10:39, 15 February 2023 ‎Ferreira, Camargo, Song (1D Maximum Subarray Maximum Subarray Problem) (hist | edit) ‎[351 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(log n)$ == Space Complexity == $O(n)$ auxiliary words (constant number of arrays as outlined in algorithm) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == EREW PRAM? == Year == 2014 == Reference == https://ieeexplore.ieee.org/document/6972008")
• 10:39, 15 February 2023 ‎Bird (1D Maximum Subarray Maximum Subarray Problem) (hist | edit) ‎[334 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary ??? (keep track of current tail sum and best sum) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == ??? == Year == 1989 == Reference == https://dl.acm.org/doi/10.1093/comjnl/32.2.122")
• 10:39, 15 February 2023 ‎Gries (1D Maximum Subarray Maximum Subarray Problem) (hist | edit) ‎[377 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary words (keep track of current tail sum and best sum) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1982 == Reference == https://www.sciencedirect.com/science/article/pii/0167642383900151?via%3Dihub")
• 10:39, 15 February 2023 ‎Fortune ( Delaunay triangulation) (hist | edit) ‎[457 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (See Fortune's Algorithm (Voronoi diagrams); Voronoi diagram gives us O(n) circumcenters which can be used to find the O(n) triangles) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1987 == Reference == http://www.wias-berlin.de/people/si/course/files/Fortune87-SweepLine-Voronoi.pdf")
• 10:39, 15 February 2023 ‎Power Iteration (Eigenpair with the Largest Eigenvalue Eigenvalues (Iterative Methods)) (hist | edit) ‎[452 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words (Derived: Stores an auxiliary vector) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1929 == Reference == https://onlinelibrary.wiley.com/doi/pdf/10.1002/zamm.19290090105?casa_token=xSwK6PkV010AAAAA:j_1-JKs0GG-KuwUUyM_dIt8kmOa5z6lvp_GABgDryAYxKdYvChyNGA9VA5CZLyAurWOVYPRn45geRTFk")
• 10:39, 15 February 2023 ‎S-buffer/Scanline Rendering ( Shown Surface Determination) (hist | edit) ‎[269 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(E+p)$? == Space Complexity == $O(p+n)$? words? ((can be easily derived?)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1980 == Reference ==")
• 10:39, 15 February 2023 ‎Z-buffering ( Shown Surface Determination) (hist | edit) ‎[529 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(np)$ == Space Complexity == $O(p+n)$ words? (https://www.geeksforgeeks.org/z-buffer-depth-buffer-method/#:~:text=Z%2Dbuffer%2C%20which%20is%20also,pixels%20times%20number%20of%20objects.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1974 == Reference == http://isgwww.cs.uni-magdeburg.de/graphics/misc/Wolfgang_Stra%C3%9Fer_Schnelle_Kurven-_un...")
• 10:39, 15 February 2023 ‎Binary space partitioning (BSP) ( Shown Surface Determination) (hist | edit) ‎[364 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2}+p)$? (previously said $O(n^{2}logn)$ == Space Complexity == $O(n^{2}+p)$? words? ((can be easily derived?)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1969 == Reference == https://apps.dtic.mil/dtic/tr/fulltext/u2/700375.pdf")
• 10:39, 15 February 2023 ‎Ray tracing ( Shown Surface Determination) (hist | edit) ‎[267 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(np)$ == Space Complexity == $O(p+n)$? words? ((can be easily derived?)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1982 == Reference ==")
• 10:39, 15 February 2023 ‎Warnock's algorithm ( Shown Surface Determination) (hist | edit) ‎[319 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(np)$ == Space Complexity == $O(p+n)$? words? ((can be easily derived?)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1969 == Reference == https://dl.acm.org/doi/book/10.5555/905316?dl=ACM")
• 10:39, 15 February 2023 ‎Painter's algorithm/Newell's algorithm ( Shown Surface Determination) (hist | edit) ‎[340 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*log(n)$+np) == Space Complexity == $O(p+n)$ words? ((can be easily derived)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1972 == Reference == https://www.cs.drexel.edu/~david/Classes/Papers/p443-newell.pdf")
• 10:39, 15 February 2023 ‎Suzuki-Kasami's algorithm ( Mutual Exclusion) (hist | edit) ‎[459 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$? (originally this had $O(logn)$) == Space Complexity == $O({1})$ per process, $O(n)$ total? communication variables? (https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.135.825&rep=rep1&type=pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1985 == Reference == https://cse.iitkgp.ac.in/~agupta/distsys/Mutex-SuzukiKasami.pdf")
• 10:39, 15 February 2023 ‎Raymond's algorithm ( Mutual Exclusion) (hist | edit) ‎[444 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(logn)$? (originally this had $O(n)$) == Space Complexity == $O({1})$ per process, $O(n)$ total? communication variables? (https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.135.825&rep=rep1&type=pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1997 == Reference ==")
• 10:39, 15 February 2023 ‎Maekawa's algorithm ( Mutual Exclusion) (hist | edit) ‎[430 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{0.5})$ == Space Complexity == $O({1})$ per process, $O(n)$ total? communication variables? (https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.135.825&rep=rep1&type=pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1985 == Reference == https://cseweb.ucsd.edu/classes/wi09/cse223a/p145-maekawa.pdf")
• 10:39, 15 February 2023 ‎Taubenfeld's black-white bakery algorithm ( Mutual Exclusion) (hist | edit) ‎[398 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ per process, $O(n)$ total? communication variables? (https://link.springer.com/content/pdf/10.1007/b101206.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2004 == Reference == https://link.springer.com/chapter/10.1007/978-3-540-30186-8_5")
• 10:39, 15 February 2023 ‎Szymanski's algorithm ( Mutual Exclusion) (hist | edit) ‎[464 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ per process, $O(n)$ total? communication variables? (http://cs.rpi.edu/~szymansk/papers/jerus.93.pdf (kinda)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1988 == Reference == https://www.researchgate.net/publication/221235887_A_simple_solution_to_Lamport's_concurrent_programming_problem_with_linear_wait")
• 10:39, 15 February 2023 ‎Lamport's bakery algorithm ( Mutual Exclusion) (hist | edit) ‎[411 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ per process, $O(n)$ total? communication variables? (https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.135.825&rep=rep1&type=pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1974 == Reference == http://lamport.azurewebsites.net/pubs/bakery.pdf")
• 10:38, 15 February 2023 ‎Covanov and Thomé ( Multiplication) (hist | edit) ‎[325 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn {2}^{O(log*n)$}) == Space Complexity == $O(n)$ auxiliary?? bits (^ same as above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 2015 == Reference == https://hal.inria.fr/hal-01108166v1/document")
• 10:38, 15 February 2023 ‎Harvey; Hoeven; Lecerf ( Multiplication) (hist | edit) ‎[325 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn {2}^{({3}log*n)$}) == Space Complexity == $O(n)$ auxiliary?? bits (^ same as above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 2015 == Reference == https://arxiv.org/abs/1407.3360")
• 10:38, 15 February 2023 ‎Harvey; Hoeven ( Multiplication) (hist | edit) ‎[482 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ auxiliary?? bits ((this one is kind of a mess to read but it seems generally the same as above - objects like polynomials/vectors and other numbers are of size O(n) and there are constantly many?)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 2019 == Reference == https://hal.archives-ouvertes.fr/hal-0207...")
• 10:38, 15 February 2023 ‎De ( Multiplication) (hist | edit) ‎[320 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn {2}^{O(log*n)$}) == Space Complexity == $O(n)$ auxiliary? bits (^ same as above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 2008 == Reference == https://arxiv.org/abs/0801.1416")
• 10:38, 15 February 2023 ‎Furer's algorithm ( Multiplication) (hist | edit) ‎[533 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn {2}^{O(log*n)$}) == Space Complexity == $O(n)$ auxiliary? bits (Depends on DFT/FFT algorithm (though original source describes its own algorithm)? but all vectors/numbers are of size O(n) and there are a constant number of such objects) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 2007 == Reference == https://web.archive.org/web/201304...")
• 10:38, 15 February 2023 ‎Schönhage–Strassen algorithm ( Multiplication) (hist | edit) ‎[439 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n logn loglogn)$ == Space Complexity == $O(n)$ auxiliary? bits (Depends on DFT/FFT algorithm? but all vectors/numbers are of size O(n) and there are a constant number of such objects) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1971 == Reference == https://link.springer.com/article/10.1007/BF02242355")
• 10:38, 15 February 2023 ‎Skala (convex and non-convex polyhedral window Line Clipping) (hist | edit) ‎[381 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(np)$? == Space Complexity == $O({1})$ auxiliary? words (Easily derived? (O(1) per segment, space can be re-used)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1996 == Reference == https://onlinelibrary.wiley.com/doi/abs/10.1111/1467-8659.1510061")
• 10:38, 15 February 2023 ‎O(lg N) algorithm (convex polygonal window Line Clipping) (hist | edit) ‎[466 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*logp)$ == Space Complexity == $O({1})$ auxiliary?? words (Easily derived? (O(1) per segment, space can be re-used)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1994 == Reference == https://www.sciencedirect.com/science/article/pii/0097849394900647/pdf?md5=06bd1f11031af17d1fd34626c4e2f49b&pid=1-s2.0-0097849394900647-main.pdf")
• 10:38, 15 February 2023 ‎FOGSAA (Edit sequence, global alignment Sequence Alignment) (hist | edit) ‎[347 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(mn)$? words (Upper bounded by runtime, though likely there's a better bound?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2013 == Reference == https://www.nature.com/articles/srep01746")
• 10:38, 15 February 2023 ‎Tuned Boyer-Moore algorithm (Single String Search String Search) (hist | edit) ‎[389 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(m + s)$ words (https://www.cs.utexas.edu/users/moore/publications/fstrpos.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1991 == Reference == http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.13.9460&rep=rep1&type=pdf")
• 10:38, 15 February 2023 ‎Fringe (Informed Search Informed Search) (hist | edit) ‎[277 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(b^d)$ == Space Complexity == $O(b^d)$ words (Stores all generated nodes in memory) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2005 == Reference ==")
• 10:38, 15 February 2023 ‎Field D* (Informed Search Informed Search) (hist | edit) ‎[365 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(b^d)$ == Space Complexity == $O(b^d)$ words (Stores all generated nodes in memory) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference == https://www.ri.cmu.edu/pub_files/pub4/ferguson_david_2006_3/ferguson_david_2006_3.pdf")
• 10:38, 15 February 2023 ‎D* (Informed Search Informed Search) (hist | edit) ‎[344 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(b^d)$ == Space Complexity == $O(b^d)$ words (Stores all generated nodes in memory) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1994 == Reference == https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.15.3683")
• 10:38, 15 February 2023 ‎Block A* (Informed Search Informed Search) (hist | edit) ‎[354 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(b^d)$ == Space Complexity == $O(b^d)$ words (Stores all generated nodes in memory) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2011 == Reference == https://webdocs.cs.ualberta.ca/~holte/Publications/aaai11PeterYapFinal.pdf")
• 10:38, 15 February 2023 ‎Incremental Heuristic Search ( Informed Search) (hist | edit) ‎[220 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(b^d)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1968 == Reference ==")
• 10:38, 15 February 2023 ‎Greedy Best-First Search (Informed Search Informed Search) (hist | edit) ‎[329 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(b^d)$ == Space Complexity == $O(b^d)$ words (https://en.wikipedia.org/wiki/Breadth-first_search: Stores all generated nodes in memory) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1959 == Reference ==")
• 10:38, 15 February 2023 ‎Press, Teukolsky, Flannery (Square Matrix LU Decomposition LU Decomposition) (hist | edit) ‎[513 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $\tilde{O}(n)$ words (Derived: The only auxiliary structure used is a list called "vv" that has one entry per row of the input matrix to store some sort of scaling metric) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2007 == Reference == https://books.google.com/books?hl=en&lr=&id=1aAOdzK3FegC&oi=fnd&pg=PA1&dq=T...")
• 10:38, 15 February 2023 ‎David ( LU Decomposition) (hist | edit) ‎[235 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference ==")
• 10:38, 15 February 2023 ‎Randomized LU Decomposition (Rectangular Matrix LU Decomposition LU Decomposition) (hist | edit) ‎[528 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $\tilde{O}(nl + ml)$ words (Derived: Two intermediate auxiliary matrices of sizes $n \times l$ and $m \times l$ for the input matrix of size $m \times n$) == Description == == Approximate? == Approximate Approximation Factor: See Theorem 4.3 in original paper for error bound == Randomized? == Yes, Monte Carlo == Model of Computation == Word RAM == Year == 2016 == Reference == https://www.sc...")
• 10:38, 15 February 2023 ‎Closed formula ( LU Decomposition) (hist | edit) ‎[235 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1975 == Reference ==")
• 10:38, 15 February 2023 ‎Shanks's square forms factorization (SQUFOF) (Second Category Integer Factoring Integer Factoring) (hist | edit) ‎[378 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^{(n/{4})$}) == Space Complexity == $O(n)$? bits (Constant number of O(n)-bit integers) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 2007 == Reference == https://www.ams.org/journals/mcom/2008-77-261/S0025-5718-07-02010-8/S0025-5718-07-02010-8.pdf")
• 10:38, 15 February 2023 ‎Rational sieve (Second Category Integer Factoring Integer Factoring) (hist | edit) ‎[424 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(e^{sqrt(({2}+o({1})$)n*logn)}) == Space Complexity == $O(n+(B/logB)$^{2})? bits (Same general approach as Dixon's algorithm) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1993 == Reference == https://www.ams.org/journals/mcom/1993-61-203/S0025-5718-1993-1182953-4/S0025-5718-1993-1182953-4.pdf")
• 10:38, 15 February 2023 ‎Quadratic sieve (Second Category Integer Factoring Integer Factoring) (hist | edit) ‎[429 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == - == Space Complexity == $O(n+(B/logB)$^{2})? bits (Same general approach as Dixon's algorithm) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1981 == Reference == https://www.semanticscholar.org/paper/Analysis-and-comparison-of-some-integer-factoring-Pomerance/134b7b065a73d4ca00bb16c7b8bebbde951b0ba0")
• 10:38, 15 February 2023 ‎Continued fraction factorization (CFRAC) (Second Category Integer Factoring Integer Factoring) (hist | edit) ‎[413 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(e^{\sqrt({2}n*logn)})$ == Space Complexity == $O(n+(B/logB)$^{2})? bits (Same as above? assuming there is a bound parameter implemented) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1931 == Reference == https://www.ams.org/journals/bull/1931-37-10/S0002-9904-1931-05271-X/home.html")
• 10:38, 15 February 2023 ‎Dixon's algorithm (Second Category Integer Factoring Integer Factoring) (hist | edit) ‎[643 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(e^{({2} \sqrt({2}) \sqrt(n*logn))}){4} == Space Complexity == $O(n+(B/logB)$^{2})? bits (There are pi(B) = O(B/log B) primes in the factor base; need pi(B)+1=O(B/log B) relations involving an integer (which doesn't need to be kept track of) and a pi(B)-bit string of exponents. Also need O(n) bits to perform other computations. Rest is irrelevant asymptotically) == Description == == Approximate? == Exact == Randomized? == No, deter...")
• 10:38, 15 February 2023 ‎Euler's factorization method (First Category Integer Factoring Integer Factoring) (hist | edit) ‎[310 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^{(n/{2})})$ == Space Complexity == $O(n)$ auxiliary bits (constant number of values which require at most O(n) bits) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1940 == Reference == -")

(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)