{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T21:11:43Z","timestamp":1743109903827,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":33,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540851936"},{"type":"electronic","value":"9783540851943"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-85194-3_11","type":"book-chapter","created":{"date-parts":[[2008,8,19]],"date-time":"2008-08-19T06:21:05Z","timestamp":1219126865000},"page":"111-128","source":"Crossref","is-referenced-by-count":0,"title":["On Faster Integer Calculations Using Non-arithmetic Primitives"],"prefix":"10.1007","author":[{"given":"Katharina","family":"L\u00fcrwer-Br\u00fcggemeier","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Ziegler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"11_CR1","doi-asserted-by":"crossref","unstructured":"Allender, E., B\u00fcrgisser, P., Kjeldgaard-Pedersen, J., Miltersen, P.B.: On the Complexity of Numerical Analysis. In: Proc. 21st Annual IEEE Conference on Computational Complexity (CCC 2006), pp. 331\u2013339 (2006)","DOI":"10.1109\/CCC.2006.30"},{"key":"11_CR2","unstructured":"AMD64 Architecture Programmer\u2019s Manual. vol. 1: Application Programming, Publication #24592 (Revision 3.13, July 2007)"},{"key":"11_CR3","series-title":"Efficient Algorithms","volume-title":"Algorithmic Number Theory","author":"E. Bach","year":"1996","unstructured":"Bach, E., Shallit, J.: Algorithmic Number Theory. Efficient Algorithms, vol.\u00a01. MIT Press, Cambridge (1996)"},{"key":"11_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1007\/11534273_36","volume-title":"Algorithms and Data Structures","author":"I. Baran","year":"2005","unstructured":"Baran, I., Demaine, E.D., P\u01cetra\u015fcu, M.: Subquadratic Algorithms for 3SUM. In: Dehne, F., L\u00f3pez-Ortiz, A., Sack, J.-R. (eds.) WADS 2005. LNCS, vol.\u00a03608, pp. 409\u2013421. Springer, Heidelberg (2005)"},{"key":"11_CR5","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03338-8","volume-title":"Algebraic Complexity Theory","author":"P. B\u00fcrgisser","year":"1997","unstructured":"B\u00fcrgisser, P., Clausen, M., Shokrollahi, M.A.: Algebraic Complexity Theory. Springer, Heidelberg (1997)"},{"key":"11_CR6","first-page":"65","volume":"25","author":"A. Bertoni","year":"1985","unstructured":"Bertoni, A., Mauri, G., Sabadini, N.: Simulations Among Classes of Random Access Machines and Equivalence Among Numbers Succinctly Represented. Ann. Discrete Math.\u00a025, 65\u201390 (1985)","journal-title":"Ann. Discrete Math."},{"key":"11_CR7","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1007\/BF01272076","volume":"2","author":"N.H. Bshouty","year":"1992","unstructured":"Bshouty, N.H., Mansour, Y., Schieber, B., Tiwari, P.: Fast Exponentiation using the Truncation Operation. Computational Complexity\u00a02, 244\u2013255 (1992)","journal-title":"Computational Complexity"},{"key":"11_CR8","volume-title":"PI and the AGM","author":"J. Borwein","year":"1987","unstructured":"Borwein, J., Borwein, P.: PI and the AGM. Wiley, Chichester (1987)"},{"key":"11_CR9","unstructured":"Bshouty, N.: Euclidean GCD algorithm is not optimal (preprint, 1989)"},{"key":"11_CR10","unstructured":"Bshouty, N.: Private communication (1992)"},{"key":"11_CR11","unstructured":"Caldwell, C.K., Cheng, Y.: Determining Mill\u2019s Constant and a Note on Honaker\u2019s Problem. Journal of Integer Sequences, article 05.4.1\u00a08 (2005)"},{"key":"11_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/3-540-36494-3_15","volume-title":"STACS 2003","author":"Q. Cheng","year":"2003","unstructured":"Cheng, Q.: On the Ultimate Complexity of Factorials. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol.\u00a02607, pp. 157\u2013166. Springer, Heidelberg (2003)"},{"key":"11_CR13","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0747-7171(08)80013-2","volume":"9","author":"D. Coppersmith","year":"1990","unstructured":"Coppersmith, D., Winograd, S.: Matrix Multiplication via Arithmetic Progressions. Journal of Symbolic Computation\u00a09, 251\u2013280 (1990)","journal-title":"Journal of Symbolic Computation"},{"issue":"1","key":"11_CR14","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1137\/0214007","volume":"14","author":"C.M. Fiduccia","year":"1985","unstructured":"Fiduccia, C.M.: An Efficient Formula for Linear Recurrences. SIAM J. Comput.\u00a014(1), 106\u2013112 (1985)","journal-title":"SIAM J. Comput."},{"key":"11_CR15","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/0925-7721(95)00022-2","volume":"5","author":"A. Gajentaan","year":"1995","unstructured":"Gajentaan, A., Overmars, M.H.: On a Class of $\\mathcal O(n^2)$ Problems in Computational Geometry. Computational Geometry: Theory and Applications\u00a05, 165\u2013185 (1995)","journal-title":"Computational Geometry: Theory and Applications"},{"key":"11_CR16","doi-asserted-by":"crossref","unstructured":"Granlund, T., Montgomery, P.L.: Division by Invariant Integers using Multiplication. In: ACM SIGPLAN Notices, pp. 61\u201372 (June 1994)","DOI":"10.1145\/773473.178249"},{"key":"11_CR17","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/j.jalgor.2003.09.001","volume":"50","author":"Y. Han","year":"2004","unstructured":"Han, Y.: Deterministic Sorting in $\\mathcal O$(n \u00b7 loglog n) time and linear space. Journal of Algorithms\u00a050, 96\u2013105 (2004)","journal-title":"Journal of Algorithms"},{"key":"11_CR18","unstructured":"Intel\u00ae64 and IA-32 Architectures Software Developer\u2019s Manual, vol. 2A. Instruction Set Reference, A-M (order no.253666, May 2007)"},{"key":"11_CR19","unstructured":"Jacobson, N.: Structure of Rings. American Mathematical Society Colloquium Publications\u00a037 (1964)"},{"issue":"1","key":"11_CR20","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1051\/ita\/1989230101011","volume":"23","author":"B. Just","year":"1989","unstructured":"Just, B., auf der Heide, F.M., Wigderson, A.: On computations with integer division. RAIRO Informatique Theoretique\u00a023(1), 101\u2013111 (1989)","journal-title":"RAIRO Informatique Theoretique"},{"issue":"3","key":"11_CR21","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1016\/0304-3975(83)90023-3","volume":"28","author":"D. Kirkpatrick","year":"1983","unstructured":"Kirkpatrick, D., Reisch, S.: Upper bounds for sorting integers on random access machines. Theoretical Computer Science\u00a028(3), 263\u2013276 (1983)","journal-title":"Theoretical Computer Science"},{"key":"11_CR22","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/s00037-004-0186-2","volume":"13","author":"P. Koiran","year":"2004","unstructured":"Koiran, P.: Valiant\u2019s Model and the Cost of Computing Integers. Computational Complexity\u00a013, 131\u2013146 (2004)","journal-title":"Computational Complexity"},{"key":"11_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1007\/3-540-56503-5_46","volume-title":"STACS 93","author":"K. L\u00fcrwer-Br\u00fcggemeier","year":"1993","unstructured":"L\u00fcrwer-Br\u00fcggemeier, K., auf der Heide, F.M.: Capabilities and Complexity of Computations with Integer Division. In: Enjalbert, P., Wagner, K.W., Finkel, A. (eds.) STACS 1993. LNCS, vol.\u00a0665, pp. 463\u2013472. Springer, Heidelberg (1993)"},{"key":"11_CR24","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1112\/S0025579300004708","volume":"20","author":"H.L. Montgomery","year":"1973","unstructured":"Montgomery, H.L., Vaughan, R.C.: The large sieve. Mathematika\u00a020, 119\u2013134 (1973)","journal-title":"Mathematika"},{"key":"11_CR25","doi-asserted-by":"crossref","unstructured":"Mansour, Y., Schieber, B., Tiwari, P.: The Complexity of Approximating the Square Root. In: Proc. 30th IEEE Symposium on Foundations of Computer Science (FOCS 1989), pp. 325\u2013330 (1989)","DOI":"10.1109\/SFCS.1989.63498"},{"key":"11_CR26","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1145\/358527.358540","volume":"24","author":"P. Pritchard","year":"1981","unstructured":"Pritchard, P.: A sublinear additive sieve for finding prime numbers. Communications of the ACM\u00a024, 18\u201323 (1981)","journal-title":"Communications of the ACM"},{"key":"11_CR27","doi-asserted-by":"crossref","unstructured":"Pratt, V.R., Rabin, M.O., Stockmeyer, L.J.: A Characterization of the Power of Vector Machines. In: Proc. 6th Annual ACM Symposium on Theory of Computing (STOC 1974), pp. 122\u2013134 (1974)","DOI":"10.1145\/800119.803892"},{"key":"11_CR28","volume-title":"Basic Real and Abstract Analysis","author":"J.F. Randolph","year":"1968","unstructured":"Randolph, J.F.: Basic Real and Abstract Analysis. Academic Press, London (1968)"},{"key":"11_CR29","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0759-7","volume-title":"The New Book of Prime Number Records","author":"P. Ribenboim","year":"1996","unstructured":"Ribenboim, P.: The New Book of Prime Number Records, 3rd edn. Springer, Heidelberg (1996)","edition":"3"},{"key":"11_CR30","doi-asserted-by":"crossref","DOI":"10.1007\/b98892","volume-title":"My Numbers, My Friends","author":"P. Ribenboim","year":"2000","unstructured":"Ribenboim, P.: My Numbers, My Friends. Springer, Heidelberg (2000)"},{"key":"11_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"520","DOI":"10.1007\/3-540-09510-1_42","volume-title":"Automata, Languages, and Programming","author":"A. Sch\u00f6nhage","year":"1979","unstructured":"Sch\u00f6nhage, A.: On the Power of Random Access Machines. In: Maurer, H.A. (ed.) ICALP 1979. LNCS, vol.\u00a071, pp. 520\u2013529. Springer, Heidelberg (1979)"},{"issue":"1","key":"11_CR32","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1016\/0020-0190(79)90087-5","volume":"8","author":"A. Shamir","year":"1979","unstructured":"Shamir, A.: Factoring Numbers in $\\mathcal O$(log n) Arithmetic Steps. Information Processing Letters\u00a08(1), 28\u201331 (1979)","journal-title":"Information Processing Letters"},{"key":"11_CR33","doi-asserted-by":"crossref","unstructured":"Simon, J.: Division is Good. In: Proc. 20th Annual Symposium on Foundations of Computer Science (IEEE FoCS 1979), pp. 411\u2013420 (1979)","DOI":"10.1109\/SFCS.1979.13"}],"container-title":["Lecture Notes in Computer Science","Unconventional Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-85194-3_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,31]],"date-time":"2025-01-31T15:26:57Z","timestamp":1738337217000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-540-85194-3_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540851936","9783540851943"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-85194-3_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2008]]}}}