{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:42:33Z","timestamp":1750308153065,"version":"3.41.0"},"reference-count":16,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2005,9,1]],"date-time":"2005-09-01T00:00:00Z","timestamp":1125532800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGSAM Bull."],"published-print":{"date-parts":[[2005,9]]},"abstract":"We consider the evaluation of the truncated hypergeometric\nseries<\/jats:p>\n [EQUATION]<\/jats:p>\n to high precision, where <i>a, b, p<\/i>, and\n<i>q<\/i> are polynomials with integer coefficients, and\n<i>a<\/i>(<i>n<\/i>),\n<i>b<\/i>(<i>n<\/i>),\n<i>p<\/i>(<i>n<\/i>),\n<i>q<\/i>(<i>n<\/i>) have bit length\n<i>O<\/i>(log <i>n<\/i>). We also assume that\nthe series is linearly convergent, so that the\n<i>n<\/i>th term of (1) is\n<i>O<\/i>(<i>c<sup>-n<\/sup><\/i>)\nwith <i>c<\/i> &gt; 1. These series are commonly\nused in the high precision evaluation of elementary functions and\nother constants, including the exponential function, logarithms,\ntrigonometric functions, and constants such as the\nAp&eacute;ry's constant &zeta;(3) [9, 10].<\/jats:p>\n \"Binary splitting\" is an approach that has been independently\ndiscovered and used by many authors in the computation of (1) [2,\n3, 4, 5, 8, 10, 12]. Binary splitting computes the numerator and\ndenominator of the rational number\n<i>S<\/i>(<i>N<\/i>). The decimal\nrepresentation of <i>S<\/i>(<i>N<\/i>) is\nthen computed by fixed-point division of the numerator by the\ndenominator. The binary splitting approach takes advantage of the\nspecial form of the series (1) to obtain a denominator that is\nrelatively small (of size <i>O<\/i>(<i>N<\/i>\nlog <i>N<\/i>)). It also takes advantage of fast integer\nmultiplication to obtain a time complexity of\n<i>O<\/i>((log\n<i>N<\/i>)<sup>2<\/sup>M(<i>N<\/i>)),\nwhere M(<i>N<\/i>) =\n<i>O<\/i>(<i>N<\/i> log <i>N<\/i>\nlog log <i>N<\/i>) is the complexity of integer\nmultiplication of two <i>N<\/i>-bit integers [16]. The\nspace complexity of the algorithm is\n<i>O<\/i>(<i>N<\/i> log\n<i>N<\/i>), the size of the computed numerator and\ndenominator.<\/jats:p>\n Typically, the numerator and denominator computed by binary\nsplitting have large common factors. For example, in the\ncomputation of 640000 digits of &zeta;(3), as much as 86% of\nthe size of the computed numerator and denominator can be\nattributed to their common factor [7]. Empirically, we have\nobserved that the size of the reduced numerator and denominator is\n<i>O<\/i>(<i>N<\/i>) instead of\n<i>O<\/i>(<i>N<\/i> log <i>N<\/i>)\nas computed by binary splitting. The additional digits computed not\nonly slow down the final division but also require more memory to\nbe used during the computation. For computing a large number of\ndecimal digits, either the computation cannot be done at all or\nsome data would have to be swapped out of memory, increasing the\ncomputation time dramatically.<\/jats:p>\n In this poster, we study the application of well-known\ntechniques in computer algebra to the evaluation of (1). If a bound\non the size of the <i>reduced<\/i> numerator and\ndenominator is known, we can compute the image of\n<i>S<\/i>(<i>N<\/i>) in (1) under an\nappropriately chosen modulus. Fast rational number reconstruction\ncan then be applied to recover the reduced numerator and\ndenominator [13, 14, 15, 17]. We show how to apply our techniques\nto the computation of &zeta;(3), including the prediction of\nthe size of the reduced numerator and denominator. In particular,\nwe obtain the desired <i>O<\/i>(<i>N<\/i>)\nbound on the size of reduced numerator and denominator, which is an\ninteresting result by itself. The techniques used in the analysis\ncan be applied to similar hypergeometric series.<\/jats:p>","DOI":"10.1145\/1113439.1113445","type":"journal-article","created":{"date-parts":[[2007,1,17]],"date-time":"2007-01-17T18:32:02Z","timestamp":1169058722000},"page":"81-83","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Space-efficient evaluation of hypergeometric series"],"prefix":"10.1145","volume":"39","author":[{"given":"Howard","family":"Cheng","sequence":"first","affiliation":[{"name":"University of Lethbridge, Lethbridge, Alberta, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Barry","family":"Gergel","sequence":"additional","affiliation":[{"name":"University of Lethbridge, Lethbridge, Alberta, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ethan","family":"Kim","sequence":"additional","affiliation":[{"name":"University of Lethbridge, Lethbridge, Alberta, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eugene","family":"Zima","sequence":"additional","affiliation":[{"name":"Wilfrid Laurier University, Waterloo, Ontario, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2005,9]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"T.\n Amdeberhan\n and \n D.\n Zeilberger\n . \n Hypergeometric series acceleration via the WZ method\n . Electronic Jl. \n of Combinatorics 4 1997\n . T. Amdeberhan and D. Zeilberger. Hypergeometric series acceleration via the WZ method. Electronic Jl. of Combinatorics 4 1997.","key":"e_1_2_1_1_1","DOI":"10.37236\/1318"},{"unstructured":"D. J. Bernstein. Fast multiplication and its applications. To appear in Buhler-Stevenhagen Algorithmic number theory book. D. J. Bernstein. Fast multiplication and its applications. To appear in Buhler-Stevenhagen Algorithmic number theory book.","key":"e_1_2_1_2_1"},{"key":"e_1_2_1_3_1","volume-title":"Pi and the AGM","author":"Borwein J.","year":"1987","unstructured":"J. Borwein and P. Borwein . Pi and the AGM . John Wiley and Sons , 1987 . J. Borwein and P. Borwein. Pi and the AGM. John Wiley and Sons, 1987."},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1016\/S0377-0427(00)00336-8"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.1145\/321941.321944"},{"key":"e_1_2_1_6_1","volume-title":"Space-efficient evaluation of hypergeometric series. To appear in Communications in Computer Algebra","author":"Cheng H.","year":"2005","unstructured":"H. Cheng , B. Gergel , E. Kim , and E. V. Zima . Space-efficient evaluation of hypergeometric series. To appear in Communications in Computer Algebra , 2005 . H. Cheng, B. Gergel, E. Kim, and E. V. Zima. Space-efficient evaluation of hypergeometric series. To appear in Communications in Computer Algebra, 2005."},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1145\/345542.345581"},{"key":"e_1_2_1_8_1","first-page":"261","volume-title":"Computers in Mathematics","author":"Gosper R. W.","year":"1990","unstructured":"R. W. Gosper . Strip mining in the abandoned orefields of nineteenth century mathematics . In Computers in Mathematics , pages 261 -- 284 . Dekker , New York , 1990 . R. W. Gosper. Strip mining in the abandoned orefields of nineteenth century mathematics. In Computers in Mathematics, pages 261--284. Dekker, New York, 1990."},{"unstructured":"X. Gourdon and P. Sebah. Numbers constants and computation. http:\/\/numbers.computation.free.fr\/Constants\/constants.html. X. Gourdon and P. Sebah. Numbers constants and computation. http:\/\/numbers.computation.free.fr\/Constants\/constants.html.","key":"e_1_2_1_9_1"},{"key":"e_1_2_1_10_1","series-title":"Lecture Notes in Computer Science","volume-title":"Algorithmic Number Theory, Third International Symposium, ANTS-III","author":"Haible B.","year":"1998","unstructured":"B. Haible and T. Papanikolaou . Fast multiprecision evaluation of series of rational numbers . In J. P. Buhler, editor, Algorithmic Number Theory, Third International Symposium, ANTS-III , volume 1423 of Lecture Notes in Computer Science . Springer , 1998 . B. Haible and T. Papanikolaou. Fast multiprecision evaluation of series of rational numbers. In J. P. Buhler, editor, Algorithmic Number Theory, Third International Symposium, ANTS-III, volume 1423 of Lecture Notes in Computer Science. Springer, 1998."},{"key":"e_1_2_1_11_1","volume-title":"Private Communication","author":"Hanrot G.","year":"2005","unstructured":"G. Hanrot , E. Thom\u00e9 , and P. Zimmermann . A new algorithm for hypergeometric constants . Private Communication , 2005 . G. Hanrot, E. Thom\u00e9, and P. Zimmermann. A new algorithm for hypergeometric constants. Private Communication, 2005."},{"key":"e_1_2_1_12_1","first-page":"68","article-title":"Fast evaluation of ζ(3)","volume":"27","author":"Karatsuba E. A.","year":"1993","unstructured":"E. A. Karatsuba . Fast evaluation of ζ(3) . Problemy Peredachi Informatsii , 27 : 68 -- 73 , 1993 . E. A. Karatsuba. Fast evaluation of ζ(3). Problemy Peredachi Informatsii, 27:68--73, 1993.","journal-title":"Problemy Peredachi Informatsii"},{"doi-asserted-by":"publisher","key":"e_1_2_1_13_1","DOI":"10.1145\/1005285.1005321"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.1007\/BF00289520"},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_1","DOI":"10.1007\/BF02242355"},{"doi-asserted-by":"publisher","key":"e_1_2_1_17_1","DOI":"10.1137\/S0097539702408636"}],"container-title":["ACM SIGSAM Bulletin"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1113439.1113445","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1113439.1113445","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:18:47Z","timestamp":1750263527000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1113439.1113445"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,9]]},"references-count":16,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2005,9]]}},"alternative-id":["10.1145\/1113439.1113445"],"URL":"https:\/\/doi.org\/10.1145\/1113439.1113445","relation":{},"ISSN":["0163-5824"],"issn-type":[{"type":"print","value":"0163-5824"}],"subject":[],"published":{"date-parts":[[2005,9]]},"assertion":[{"value":"2005-09-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}