{ "info": { "author": "Nico Schl\u00f6mer", "author_email": "nico.schloemer@gmail.com", "bugtrack_url": null, "classifiers": [ "Development Status :: 4 - Beta", "License :: OSI Approved :: MIT License", "Operating System :: OS Independent", "Programming Language :: Python", "Programming Language :: Python :: 3", "Topic :: Scientific/Engineering", "Topic :: Scientific/Engineering :: Mathematics" ], "description": "

\n \"accupy\"\n

Accurate sums and (dot) products for Python.

\n

\n\n[![CircleCI](https://img.shields.io/circleci/project/github/nschloe/accupy/master.svg?style=flat-square)](https://circleci.com/gh/nschloe/accupy/tree/master)\n[![codecov](https://img.shields.io/codecov/c/github/nschloe/accupy.svg?style=flat-square)](https://codecov.io/gh/nschloe/accupy)\n[![Code style: black](https://img.shields.io/badge/code%20style-black-000000.svg?style=flat-square)](https://github.com/psf/black)\n[![accurate](https://img.shields.io/badge/accurate-very-brightgreen.svg?style=flat-square)](https://github.com/nschloe/accupy)\n[![PyPi Version](https://img.shields.io/pypi/v/accupy.svg?style=flat-square)](https://pypi.org/project/accupy)\n[![DOI](https://zenodo.org/badge/DOI/10.5281/zenodo.1185173.svg?style=flat-square)](https://doi.org/10.5281/zenodo.1185173)\n[![GitHub stars](https://img.shields.io/github/stars/nschloe/accupy.svg?style=flat-square&logo=github&label=Stars&logoColor=white)](https://github.com/nschloe/accupy)\n[![PyPi downloads](https://img.shields.io/pypi/dd/accupy.svg?style=flat-square)](https://pypistats.org/packages/accupy)\n\n### Sums\n\nSumming up values in a list can get tricky if the values are floating point\nnumbers; digit cancellation can occur and the result may come out wrong. A\nclassical example is the sum\n```\n1.0e16 + 1.0 - 1.0e16\n```\nThe actual result is `1.0`, but in double precision, this will result in `0.0`.\nWhile in this example the failure is quite obvious, it can get a lot more\ntricky than that. accupy provides\n```python\np, exact, cond = accupy.generate_ill_conditioned_sum(100, 1.0e20)\n```\nwhich, given a length and a target condition number, will produce an array of\nfloating point numbers that is hard to sum up.\n\naccupy has the following methods for summation:\n\n * `accupy.kahan_sum(p)`: [Kahan\n summation](https://en.wikipedia.org/wiki/Kahan_summation_algorithm)\n\n * `accupy.fsum(p)`: A vectorization wrapper around\n [math.fsum](https://docs.python.org/3/library/math.html#math.fsum) (which\n uses Shewchuck's algorithm [[1]](#references) (see also\n [here](https://code.activestate.com/recipes/393090/))).\n\n * `accupy.ksum(p, K=2)`: Summation in K-fold precision (from [[2]](#references))\n\nAll summation methods sum the first dimension of a multidimensional NumPy array.\n\nLet's compare them.\n\n#### Accuracy comparison (sum)\n\n![](https://nschloe.github.io/accupy/accuracy-sums.png)\n\nAs expected, the naive\n[sum](https://docs.python.org/3/library/functions.html#sum) performs very badly\nwith ill-conditioned sums; likewise for\n[`numpy.sum`](https://docs.scipy.org/doc/numpy/reference/generated/numpy.sum.html)\nwhich uses pairwise summation. Kahan summation not significantly better; [this,\ntoo, is\nexpected](https://en.wikipedia.org/wiki/Kahan_summation_algorithm#Accuracy).\n\nComputing the sum with 2-fold accuracy in `accupy.ksum` gives the correct\nresult if the condition is at most in the range of machine precision; further\nincreasing `K` helps with worse conditions.\n\nShewchuck's algorithm in `math.fsum` always gives the correct result to full\nfloating point precision.\n\n\n#### Runtime comparison (sum)\n\n![](https://nschloe.github.io/accupy/speed-comparison1.png)\n\n![](https://nschloe.github.io/accupy/speed-comparison2.png)\n\nWe compare more and more sums of fixed size (above) and larger and larger sums,\nbut a fixed number of them (below). In both cases, the least accurate method is\nthe fastest (`numpy.sum`), and the most accurate the slowest (`accupy.fsum`).\n\n### Dot products\n\naccupy has the following methods for dot products:\n\n * `accupy.fdot(p)`: A transformation of the dot product of length _n_ into a\n sum of length _2n_, computed with\n [math.fsum](https://docs.python.org/3/library/math.html#math.fsum)\n\n * `accupy.kdot(p, K=2)`: Dot product in K-fold precision (from\n [[2]](#references))\n\nLet's compare them.\n\n#### Accuracy comparison (dot)\n\naccupy can construct ill-conditioned dot products with\n```python\nx, y, exact, cond = accupy.generate_ill_conditioned_dot_product(100, 1.0e20)\n```\nWith this, the accuracy of the different methods is compared.\n\n![](https://nschloe.github.io/accupy/accuracy-dot.png)\n\nAs for sums, `numpy.dot` is the least accurate, followed by instanced of `kdot`.\n`fdot` is provably accurate up into the last digit\n\n#### Runtime comparison (dot)\n\n![](https://nschloe.github.io/accupy/speed-comparison-dot1.png)\n![](https://nschloe.github.io/accupy/speed-comparison-dot2.png)\n\nNumPy's `numpy.dot` is _much_ faster than all alternatives provided by accupy.\nThis is because the bookkeeping of truncation errors takes more steps, but\nmostly because of NumPy's highly optimized dot implementation.\n\n\n### References\n\n1. [Richard Shewchuk, _Adaptive Precision Floating-Point Arithmetic and Fast\n Robust Geometric Predicates_, J. Discrete Comput. Geom. (1997), 18(305),\n 305\u2013363](https://doi.org/10.1007/PL00009321)\n\n2. [Takeshi Ogita, Siegfried M. Rump, and Shin'ichi Oishi, _Accurate Sum and Dot\n Product_, SIAM J. Sci. Comput. (2006), 26(6), 1955\u20131988 (34\n pages)](https://doi.org/10.1137/030601818)\n\n### Dependencies\n\naccupy needs the C++ [Eigen\nlibrary](http://eigen.tuxfamily.org/index.php?title=Main_Page), provided in\nDebian/Ubuntu by\n[`libeigen3-dev`](https://packages.ubuntu.com/search?keywords=libeigen3-dev).\n\n### Installation\n\naccupy is [available from the Python Package Index](https://pypi.org/project/accupy/), so with\n```\npip install -U accupy\n```\nyou can install/upgrade.\n\n### Testing\n\nTo run the tests, just check out this repository and type\n```\nMPLBACKEND=Agg pytest\n```\n\n### License\naccupy is published under the [MIT license](https://en.wikipedia.org/wiki/MIT_License).", "description_content_type": "text/markdown", "docs_url": null, "download_url": "", "downloads": { "last_day": -1, "last_month": -1, "last_week": -1 }, "home_page": "https://github.com/nschloe/accupy", "keywords": "", "license": "License :: OSI Approved :: MIT License", "maintainer": "", "maintainer_email": "", "name": "accupy", "package_url": "https://pypi.org/project/accupy/", "platform": "", "project_url": "https://pypi.org/project/accupy/", "project_urls": { "Homepage": "https://github.com/nschloe/accupy" }, "release_url": "https://pypi.org/project/accupy/0.2.0/", "requires_dist": null, "requires_python": ">=3", "summary": "Accurate sums and dot products for Python", "version": "0.2.0" }, "last_serial": 5655435, "releases": { "0.1.0": [ { "comment_text": "", "digests": { "md5": "c30f237683b95b584152595d1f0502c7", "sha256": "27c4d951114e037ad1c1e95b061219eced5af8f39063f5cbe8e2356ae63a4721" }, "downloads": -1, "filename": "accupy-0.1.0.tar.gz", "has_sig": true, "md5_digest": "c30f237683b95b584152595d1f0502c7", "packagetype": "sdist", "python_version": "source", "requires_python": null, "size": 8870, "upload_time": "2018-02-27T14:35:08", "url": "https://files.pythonhosted.org/packages/13/71/80186eba7cb1dee4e0bcb4b72cbeb17c6f07edcd64112d69bec363e07ae6/accupy-0.1.0.tar.gz" } ], "0.1.1": [ { "comment_text": "", "digests": { "md5": "b8353521f1f41cecda40b4846c49a8d0", "sha256": "164d04eef68b7d1f2d099204dbbb467bd08c90eda3dd9dccdd4cd604fe6a8b77" }, "downloads": -1, "filename": "accupy-0.1.1.tar.gz", "has_sig": true, "md5_digest": "b8353521f1f41cecda40b4846c49a8d0", "packagetype": "sdist", "python_version": "source", "requires_python": null, "size": 10314, "upload_time": "2018-03-02T12:13:25", "url": "https://files.pythonhosted.org/packages/da/62/d3893dbacfe506c05a73917700ccdf224370543b4ec019cd8b870073277e/accupy-0.1.1.tar.gz" } ], "0.1.2": [ { "comment_text": "", "digests": { "md5": "ab286df3f029d2660d578c9eb3c6f430", "sha256": "a7cc42d5cb28398cb5fd0318411248fdde286859e69ed9a1850e945598c4b36a" }, "downloads": -1, "filename": "accupy-0.1.2.tar.gz", "has_sig": true, "md5_digest": "ab286df3f029d2660d578c9eb3c6f430", "packagetype": "sdist", "python_version": "source", "requires_python": null, "size": 9973, "upload_time": "2018-06-01T11:41:28", "url": "https://files.pythonhosted.org/packages/99/92/f6b346408b765cc0a235dc93e602d7824429dcc10c83ec525d9861ca8de0/accupy-0.1.2.tar.gz" } ], "0.1.3": [ { "comment_text": "", "digests": { "md5": "b0bec849cfca84b2847a28ecc424580c", "sha256": "629b5bc953f4d09f2c13174682486666ec6e4468bcd742d703bb4f6757ad97a5" }, "downloads": -1, "filename": "accupy-0.1.3.tar.gz", "has_sig": false, "md5_digest": "b0bec849cfca84b2847a28ecc424580c", "packagetype": "sdist", "python_version": "source", "requires_python": null, "size": 10155, "upload_time": "2018-06-06T15:39:19", "url": "https://files.pythonhosted.org/packages/4b/99/8e4c2c605fbcb18eac8945f97c433d841d53213b5e4235e7b2c65648d5e3/accupy-0.1.3.tar.gz" } ], "0.1.4": [ { "comment_text": "", "digests": { "md5": "5ef2dc2f46169dead7734f11d5817f46", "sha256": "2a67f2a778b824fb24eb338fed8e0b61c1af93369d57ff8132f5d602d60f0543" }, "downloads": -1, "filename": "accupy-0.1.4.tar.gz", "has_sig": false, "md5_digest": "5ef2dc2f46169dead7734f11d5817f46", "packagetype": "sdist", "python_version": "source", "requires_python": null, "size": 10791, "upload_time": "2019-02-28T14:47:00", "url": "https://files.pythonhosted.org/packages/d8/41/eb14105efa47a6709fac7bd67520547cb783c536cd1e445c9d23991c5513/accupy-0.1.4.tar.gz" } ], "0.2.0": [ { "comment_text": "", "digests": { "md5": "9750f2d27aa288bc1595baa4e58caf9a", "sha256": "e27ca7eed8a1bde2e6e040f8f3ee94a5d7522f42c4360756c9ec8931cf13ca98" }, "downloads": -1, "filename": "accupy-0.2.0.tar.gz", "has_sig": false, "md5_digest": "9750f2d27aa288bc1595baa4e58caf9a", "packagetype": "sdist", "python_version": "source", "requires_python": ">=3", "size": 10605, "upload_time": "2019-08-09T12:40:45", "url": "https://files.pythonhosted.org/packages/45/ae/280e7c042076f14edaeeceb06d0efae4fbe924509ed0b1346ff374753a15/accupy-0.2.0.tar.gz" } ] }, "urls": [ { "comment_text": "", "digests": { "md5": "9750f2d27aa288bc1595baa4e58caf9a", "sha256": "e27ca7eed8a1bde2e6e040f8f3ee94a5d7522f42c4360756c9ec8931cf13ca98" }, "downloads": -1, "filename": "accupy-0.2.0.tar.gz", "has_sig": false, "md5_digest": "9750f2d27aa288bc1595baa4e58caf9a", "packagetype": "sdist", "python_version": "source", "requires_python": ">=3", "size": 10605, "upload_time": "2019-08-09T12:40:45", "url": "https://files.pythonhosted.org/packages/45/ae/280e7c042076f14edaeeceb06d0efae4fbe924509ed0b1346ff374753a15/accupy-0.2.0.tar.gz" } ] }