# Difference between revisions of "Applications and libraries/Mathematics"

(moved implementations from Exact real arithmetic) |
(categorise libraries for computable reals) |
||

Line 27: | Line 27: | ||

:An implementation of real decimal arithmetic, for cases where the binary floating point is not acceptable (for example, money). |
:An implementation of real decimal arithmetic, for cases where the binary floating point is not acceptable (for example, money). |
||

− | ;[[Exact real arithmetic]] |
||

− | :is an interesting area: it is a deep connection between numeric methods and deep theoretic fondations of algorithms (and mathematics). Its topic: ''computable real number''s raise a lot of interesting questions rooted in mathematical analysis, arithmetic, but also [http://en.wikipedia.org/wiki/Computability_theory computability theory] (see numbers-as-programs approaches). Computable reals can be achieved by many approaches -- it is not one single theory. |
||

− | Exact real arithmetic refers to an implementation of the computable real numbers. |
||

+ | There are several levels of [[Exact real arithmetic|handling real numbers]] and according libraries. |
||

− | There are several implementations of exact real arithmetic in Haskell. |
||

− | === |
+ | ==== Arbitrary precision ==== |

− | [http://medialab.freaknet.org/bignum/ BigFloat] is an implementation by Martin Guy. |
||

+ | All numbers have fixed precision, rounding errors accumulate. |
||

− | It works with streams of decimal digits (strictly in the range from 0 to 9) and a separate sign. |
||

− | The produced digits are always correct. |
||

− | Output is postponed until the code is certain what the next digit is. |
||

− | This sometimes means that [http://medialab.freaknet.org/bignum/dudeney.html no more data is output]. |
||

− | === COMP === |
||

+ | ;[http://cvs.haskell.org/darcs/numeric-quest/Fraction.hs Fractions.hs] |
||

+ | :algorithms by Jan Skibinski, see below |
||

− | COMP is an implementation by Yann Kieffer. The work is in beta, and the library isn't available yet. |
||

+ | ;[http://cvs.haskell.org/darcs/numericprelude/src/Number/FixedPoint.hs FixedPoint.hs] |
||

+ | :part of NumericPrelude project |
||

− | === |
+ | ==== Dynamic precision ==== |

− | [http://www.cs.man.ac.uk/arch/dlester/exact.html Era] is an implementation (in Haskell 1.2) by David Lester. It is quite fast, possibly the fastest Haskell implementation. At 220 lines it is also the shortest. Probably the shortest implementation of exact real arithmetic in any language. |
||

+ | You tell the precision, an expression shall be computed to |
||

+ | and the computer finds out, how precise to compute the input values. |
||

− | Here is a mirror: http://darcs.augustsson.net/Darcs/CReal/ |
||

+ | ;[http://www.cs.man.ac.uk/arch/dlester/exact.html ERA] is an implementation (in Haskell 1.2) by David Lester. |
||

+ | :It is quite fast, possibly the fastest Haskell implementation. At 220 lines it is also the shortest. Probably the shortest implementation of exact real arithmetic in any language. |
||

+ | :Here is a mirror: http://darcs.augustsson.net/Darcs/CReal/ |
||

+ | ;[http://www.doc.ic.ac.uk/~ae/exact-computation/#bm:implementations IC-Reals] is an implementation by Abbas Edalat, Marko Krznarć and Peter J. Potts. |
||

+ | :This implementation uses linear fractional transformations. |
||

− | === |
+ | ==== Lazily evaluated ==== |

− | [http://r6.ca/ Few Digits] is an implementation by Russell O'Connor. This is a prototype of the implementation he intendeds to write in [http://coq.inria.fr/ Coq]. Once the Coq implementation is complete, the Haskell code could be extracted producing an implementation that would be proved correct. |
||

+ | The real numbers are represented by an infinite datastructure, which allows you to increase precision successively by evaluating the data structure successively. All of the implementations below use some kind of digit stream as number representation. |
||

− | === IC-Reals === |
||

+ | ;[http://medialab.freaknet.org/bignum/ BigFloat] is an implementation by Martin Guy. |
||

+ | :It works with streams of decimal digits (strictly in the range from 0 to 9) and a separate sign. The produced digits are always correct. Output is postponed until the code is certain what the next digit is. This sometimes means that [http://medialab.freaknet.org/bignum/dudeney.html no more data is output]. |
||

− | [http://www.doc.ic.ac.uk/~ae/exact-computation/#bm:implementations IC-Reals] is an implementation by Abbas Edalat, Marko Krznarć and Peter J. Potts. This implementation uses linear fractional transformations. |
||

+ | ;In [http://users.info.unicaen.fr/~karczma/arpap/lazypi.ps.gz "The Most Unreliable Technique in the World to compute pi"] Jerzy Karczmarczuk develops some functions for computing pi lazily. |
||

− | === NumericPrelude/Positional === |
||

+ | ;[http://darcs.haskell.org/numericprelude/src/Number/Positional.hs NumericPrelude: positional numbers] |
||

+ | :Represents a real number as pair <hask>(exponent,[digit])</hask>, |
||

+ | :where the digits are <hask>Int</hask>s in the open range <hask>(-basis,basis)</hask>. |
||

+ | :There is no need for an extra sign item in the number data structure. |
||

+ | :The <hask>basis</hask> can range from <hask>10</hask> to <hask>1000</hask>. |
||

+ | :(Binary representations can be derived from the hexadecimal representation.) |
||

+ | :Showing the numbers in traditional format (non-negative digits) |
||

+ | :fails for fractions ending with a run of zeros. |
||

+ | :However the internal representation with negative digits can always be shown |
||

+ | :and is probably more useful for further processing. |
||

+ | :An interface for the numeric type hierarchy of the NumericPrelude project is provided. |
||

− | Represents a real number as pair <hask>(exponent,[digit])</hask>, where the digits are <hask>Int</hask>s in the open range <hask>(-basis,basis)</hask>. |
||

+ | :It features |
||

− | There is no need for an extra sign item in the number data structure. |
||

+ | :* basis conversion |
||

− | The <hask>basis</hask> can range from <hask>10</hask> to <hask>1000</hask>. |
||

+ | :* basic arithmetic: addition, subtraction, multiplication, division |
||

− | (Binary representations can be derived from the hexadecimal representation.) |
||

+ | :* algebraic arithmetic: square root, other roots (no general polynomial roots) |
||

− | Showing the numbers in traditional format (non-negative digits) |
||

+ | :* transcendental arithmetic: pi, exponential, logarithm, trigonometric and inverse trigonometric functions |
||

− | fails for fractions ending with a run of zeros. |
||

− | However the internal representation with negative digits can always be shown |
||

− | and is probably more useful for further processing. |
||

− | An interface for the numeric type hierarchy of the NumericPrelude project is provided. |
||

− | It features |
||

+ | ==== uncategorised ==== |
||

− | * basis conversion |
||

− | * basic arithmetic: addition, subtraction, multiplication, division |
||

− | * algebraic arithmetic: square root, other roots (no general polynomial roots) |
||

− | * transcendental arithmetic: pi, exponential, logarithm, trigonometric and inverse trigonometric functions |
||

− | [http://darcs.haskell.org/numericprelude/src/Number/Positional.hs NumericPrelude: positional numbers] |
||

+ | ;COMP is an implementation by Yann Kieffer. |
||

+ | :The work is in beta, and the library isn't available yet. |
||

+ | |||

+ | ;[http://r6.ca/ Few Digits] by Russell O'Connor. |
||

+ | :This is a prototype of the implementation he intendeds to write in [http://coq.inria.fr/ Coq]. Once the Coq implementation is complete, the Haskell code could be extracted producing an implementation that would be proved correct. |
||

## Revision as of 09:01, 23 October 2006

*The copyright status of this work is not known. Please help resolve this on the talk page.*

*This page contains a list of libraries and tools in a certain category. For a comprehensive list of such pages, see Applications and libraries.*

## Contents

## Libraries for numerical algorithms and mathematics

### Linear algebra

- GSLHaskell
- High level functional interface to standard linear algebra computations and other numerical algorithms based on the GNU Scientific Library. Alternative download site.

- Digital Signal Processing
- Modules for matrix manipulation, digital signal processing, spectral estimation, and frequency estimation.

- Index-aware linear algebra
- Frederik Eaton's library for statically checked matrix manipulation in Haskell

- Indexless linear algebra
- algorithms by Jan Skibinski, see below

See also: Design discussions

### Number representations

- Decimal arithmetic library
- An implementation of real decimal arithmetic, for cases where the binary floating point is not acceptable (for example, money).

There are several levels of handling real numbers and according libraries.

#### Arbitrary precision

All numbers have fixed precision, rounding errors accumulate.

- Fractions.hs
- algorithms by Jan Skibinski, see below

- FixedPoint.hs
- part of NumericPrelude project

#### Dynamic precision

You tell the precision, an expression shall be computed to and the computer finds out, how precise to compute the input values.

- ERA is an implementation (in Haskell 1.2) by David Lester.
- It is quite fast, possibly the fastest Haskell implementation. At 220 lines it is also the shortest. Probably the shortest implementation of exact real arithmetic in any language.
- Here is a mirror: http://darcs.augustsson.net/Darcs/CReal/

- IC-Reals is an implementation by Abbas Edalat, Marko Krznarć and Peter J. Potts.
- This implementation uses linear fractional transformations.

#### Lazily evaluated

The real numbers are represented by an infinite datastructure, which allows you to increase precision successively by evaluating the data structure successively. All of the implementations below use some kind of digit stream as number representation.

- BigFloat is an implementation by Martin Guy.
- It works with streams of decimal digits (strictly in the range from 0 to 9) and a separate sign. The produced digits are always correct. Output is postponed until the code is certain what the next digit is. This sometimes means that no more data is output.

- In "The Most Unreliable Technique in the World to compute pi" Jerzy Karczmarczuk develops some functions for computing pi lazily.

- NumericPrelude: positional numbers
- Represents a real number as pair
`(exponent,[digit])`

, - where the digits are
`Int`

s in the open range`(-basis,basis)`

. - There is no need for an extra sign item in the number data structure.
- The
`basis`

can range from`10`

to`1000`

. - (Binary representations can be derived from the hexadecimal representation.)
- Showing the numbers in traditional format (non-negative digits)
- fails for fractions ending with a run of zeros.
- However the internal representation with negative digits can always be shown
- and is probably more useful for further processing.
- An interface for the numeric type hierarchy of the NumericPrelude project is provided.

- It features
- basis conversion
- basic arithmetic: addition, subtraction, multiplication, division
- algebraic arithmetic: square root, other roots (no general polynomial roots)
- transcendental arithmetic: pi, exponential, logarithm, trigonometric and inverse trigonometric functions

#### uncategorised

- COMP is an implementation by Yann Kieffer.
- The work is in beta, and the library isn't available yet.

- Few Digits by Russell O'Connor.
- This is a prototype of the implementation he intendeds to write in Coq. Once the Coq implementation is complete, the Haskell code could be extracted producing an implementation that would be proved correct.

### Type class hierarchies

There are several approaches to improve the numeric type class hierarchy.

- Dylan Thurston and Henning Thielemann's Numeric Prelude
- Experimental revised framework for numeric type classes. Needs hiding of Prelude, overriding hidden functions like fromInteger and multi-parameter type classes. Probably restricted to GHC.

- Jerzy Karczmarczuk's approach

- Serge D. Mechveliani's Basic Algebra proposal

- Andrew Frank's approach
- The proposal: ftp://ftp.geoinfo.tuwien.ac.at/frank/numbersPrelude_v1.pdf

- Haskell Prime
- Ongoing efforts for the language revision

### other

- Geometric Algorithms
- A small Haskell library, containing algorithms for two-dimensional convex hulls, triangulations of polygons, Voronoi-diagrams and Delaunay-triangulations, the QEDS data structure, kd-trees and range-trees.

- Papers by Jerzy Karczmarczuk
- Some interesting uses of Haskell in mathematics, including functional differentiation, power series, continued fractions.

- DoCon - Algebraic Domain Constructor
- A Computer Algebra System

- HaskellMath
- The HaskellMath library is a sandbox for experimenting with mathematics algorithms. So far I've implemented a few quantitative finance models (Black Scholes, Binomial Trees, etc) and basic linear algebra functions. Next I might work on either computer algebra or linear programming. All comments welcome!

- Haskell for Maths
- David Amos' collection of math libraries in Haskell - including number theory, commutative algebra, combinatorics, permutation groups and more.

- Various math stuff by Henning Thielemann
- This is some unsorted mathematical stuff including: GNUPlot wrapper, portable grey map (PGM) image reader and writer, simplest numerical integration, differentiation, zero finding, interpolation, solution of differential equations, combinatorics, some solutions of math riddles, computation of fractal dimensions of iterated function systems (IFS)

- Adaptive Simulated Annealing
- A Haskell interface to Lester Ingber's adaptive simulating annealing code.

- Number Theory Library
- Andrew Bromage's Haskell number theory library, providing operations on primes, fibonacci sequences and combinatorics.

- Hmm: Haskell Metamath
- Hmm is a small Haskell library to parse and verify Metamath databases.

- Probabilistic Functional Programming
- The PFP library is a collection of modules for Haskell that facilitates probabilistic functional programming, that is, programming with stochastic values. The probabilistic functional programming approach is based on a data type for representing distributions. A distribution represent the outcome of a probabilistic event as a collection of all possible values, tagged with their likelihood. A nice aspect of this system is that simulations can be specified independently from their method of execution. That is, we can either fully simulate or randomize any simulation without altering the code which defines it.

- Boolean
- A general boolean algebra class and some instances for Haskell.

- HODE
- HODE is a binding to the Open Dynamics Engine. ODE is an open source, high performance library for simulating rigid body dynamics.

- HGAL
- An haskell implementation of Brendan McKay's algorithm for graph canonic labeling and automorphism group. (aka Nauty)

- Numerics with fractions
*(via Internet Archive since 10/06/2003).* - Roots of polynomials
*(via Internet Archive since 10/06/2003).*It implements the well known Laguerre's method for finding complex roots of polynomials. - Indexless linear algebra algorithms
*(via Internet Archive since 10/06/2003).*Orthogonalization, solution of linear equations, eigenvalues and eigenvectors. - State vector evolution
*(via Internet Archive since 10/06/2003)* - Short study of fuzzy oscillator
*(via Internet Archive since 10/06/2003)* - N-dimensional tensors
*(via Internet Archive since 10/06/2003)*