Difference between revisions of "Power function"

Latest revision as of 21:34, 10 March 2016

Question

Why are there several notions of power in Haskell, namely (^), (^^), (**)?

-- typically for integers
(^) :: (Num a, Integral b) => a -> b -> a

-- typically for rationals
(^^) :: (Fractional a, Integral b) => a -> b -> a

-- typically for floating-point numbers
(**) :: Floating a => a -> a -> a

Answer

The reason is that there is no implementation of the power function that can cover all exotic choices for basis and exponent while being both efficient and accurate.

See this StackOverflow question for details.

Type inference reasons

In mathematical notation, the human reader is clever enough to to tell which definition of the power function is applicable in a given context. In Haskell, doing so would drastically complicate type inference. In some other languages such as C++, operator overloading is used to work around this problem, but this approach does not work for Haskell's numeric type classes.

Mathematical reasons

If we assume the most general types for both basis and exponent, namely complex numbers, the result of the power is no longer unique. In particular, all possible solutions of say 1^x, where x is irrational, is dense in the complex unit circle.

But even for real numbers there are problems: to calculate (-1)**(1/3::Double) the power implementation would have to decide whether (1/3::Double) is close enough to ⅓. If it does so it returns (-1), otherwise it fails. However, why shall 0.333333333333333 represent ⅓? It may be really meant as 333333333333333/10^15, and a real 10¹⁵th root of −1 does not exist. Fortunately, the Haskell implementation does not try to be too clever here. But it does so at another point:

Prelude> (-1)**2 :: Double
1.0
Prelude> (-1)**(2 + 1e-15 - 1e-15) :: Double
NaN

While both expressions should be evaluated to 1.0, a reliable check for integers is not possible with floating-point numbers.

Power function in Numeric Prelude

One can refine the set of power functions further as it is done in the Numeric Prelude. In this library, the more general the basis the less general the exponent and vice versa:

basis type	provides	symbol	exponent type	definition
any ring	`(*)`	`(^)`	cardinal	repeated multiplication	$a^{b}=\prod _{i=1}^{b}a$
any field	`(/)`	`(^-)`	integer	multiplication and division	$a^{b}={\begin{cases}a^{b}&b\geq 0\\{\frac {1}{a^{-b}}}&b<0\end{cases}}$
an algebraic field	`root`	`(^/)`	rational	list of polynomial zeros (length = denominator of the exponent)	$a^{\frac {p}{q}}=\{x:a^{p}=x^{q}\}$
positive real	`log`	`(^?)`	any ring of characteristic zero with inverses for integers and a notion of limit	exponential series and logarithm	$a^{b}=\exp(b\log a)=\sum _{k\geq 0}{\frac {(b\log a)^{k}}{k!}}$

examples for rings are: Polynomials, Matrices, Residue classes
examples for fields: Fractions of polynomials (rational functions), Residue classes with respect to irreducible divisors, in fact we do not need fields, we only need the division and associativity, thus invertible Matrices are fine

That is, (^-) replaces (^^), (^?) replaces (**), (^) remains and (^/) is new.

@@ Line 3: / Line 3: @@
 Why are there several notions of power in Haskell, namely <hask>(^)</hask>, <hask>(^^)</hask>, <hask>(**)</hask>?
+<haskell>
+-- typically for integers
+(^) :: (Num a, Integral b) => a -> b -> a
+-- typically for rationals
+(^^) :: (Fractional a, Integral b) => a -> b -> a
+-- typically for floating-point numbers
+(**) :: Floating a => a -> a -> a
+</haskell>
 == Answer ==
-The reason is that there is no definition for the power function which covers all exotic choices for bases and exponent.
+The reason is that there is no implementation of the power function that can cover all exotic choices for basis and exponent while being both efficient and accurate.
-It is even sensible to refine the set of power functions as it is done in the [http://darcs.haskell.org/numericprelude/ NumericPrelude] project.
+See this [https://stackoverflow.com/q/6400568 StackOverflow question] for details.
-In mathematical notation we don't respect types and we do not distinguish between powers of different types.
-However if we assume the most general types for both basis and exponent, the result of the power is no longer unique.
+=== Type inference reasons ===
-Actually all possible solutions of say <math>1^x</math>,
-where <math>x</math> is irrational is dense in the complex unit circle.
+In mathematical notation, the human reader is clever enough to to tell which definition of the power function is applicable in a given context.  In Haskell, doing so would drastically complicate type inference.  In some other languages such as C++, operator overloading is used to work around this problem, but [https://stackoverflow.com/a/6402880 this approach does not work for Haskell's numeric type classes].
-In the past I needed the power of two complex numbers only once, namely for the [http://www.math.uni-bremen.de/~thielema/Research/cwt.pdf Cauchy wavelet] (see also: [http://ieeexplore.ieee.org/iel5/78/18506/00852022.pdf?arnumber=852022]):
-: <math> f(t) = (1- i\cdot k\cdot t) ^ {-\frac{1}{2} + \frac{\mu_2}{k} + i\cdot \mu_1 } </math>
+=== Mathematical reasons ===
-However, I could not use the built-in complex power function
-because the resulting function became discontinuous.
+If we assume the most general types for both basis and exponent, namely complex numbers, the result of the power is no longer unique.  In particular, all possible solutions of say 1<sup>''x''</sup>, where ''x'' is irrational, is dense in the complex unit circle.
-Of course, powers of complex numbers have the problem of branch cuts and
-the choice of the branch built into the implementation of the complex power is quite arbitrary and
+But even for real numbers there are problems: to calculate <hask>(-1)**(1/3::Double)</hask> the power implementation would have to decide whether
-might be inappropriate.
+<hask>(1/3::Double)</hask> is close enough to ⅓.
+If it does so it returns <hask>(-1)</hask>, otherwise it fails.  However, why shall <hask>0.333333333333333</hask> represent ⅓?  It may be really meant as <hask>333333333333333/10^15</hask>, and a real 10<sup>15</sup>th root of −1 does not exist.  Fortunately, the Haskell implementation does not try to be too clever here.  But it does so at another point:
+<haskell>
+Prelude> (-1)**2 :: Double
+.0
+Prelude> (-1)**(2 + 1e-15 - 1e-15) :: Double
+NaN
+</haskell>
+While both expressions should be evaluated to <hask>1.0</hask>, a reliable check for integers is not possible with floating-point numbers.
+==Power function in Numeric Prelude==
-But also for real numbers there are problems:
-For computing <hask>(-1)**(1/3::Double)</hask> the power implementation has to decide whether
-<hask>(1/3::Double)</hask> is close enough to <math>\frac{1}{3}</math>.
-If it does so it returns <hask>(-1)</hask>, otherwise it fails.
-However, why shall <hask>0.333333333333333</hask> represent <math>\frac{1}{3}</math>?
-It may be really meant as <hask>333333333333333/10^15</hask>,
-and a real <math>10^{15}</math>th root of <math>-1</math> does not exist.
-So I propose some balancing: The more general the basis the less general the exponent and vice versa.
+One can refine the set of power functions further as it is done in the [[Numeric Prelude]].  In this library, the more general the basis the less general the exponent and vice versa:
-I also think the following symbols are more systematic and intuitive.
-They are used in NumericPrelude.
 {|
 |   basis type || provides || symbol || exponent type || definition ||
 |-
-|   any ring || <hask> * </hask>  ||   <hask> ^ </hask> || cardinal || repeated multiplication || <math>a^b = \prod_{i=1}^b a </math>
+|   any ring || <hask>(*)</hask>  ||   <hask>(^)</hask> || cardinal || repeated multiplication || <math>a^b = \prod_{i=1}^b a </math>
 |-
-|   any field || <hask> / </hask> ||  <hask> ^- </hask> || integer || multiplication and division || <math>a^b = \begin{cases} a^b & b\ge 0 \\ \frac{1}{a^{-b}} & b<0 \end{cases} </math>
+|   any field || <hask>(/)</hask> ||  <hask>(^-)</hask> || integer || multiplication and division || <math>a^b = \begin{cases} a^b & b\ge 0 \\ \frac{1}{a^{-b}} & b<0 \end{cases} </math>
 |-
-|   an algebraic field || <hask>root</hask> || <hask> ^/ </hask> ||  rational  || list of polynomial zeros (length = denominator of the exponent) || <math> a^{\frac{p}{q}} = \{ x : a^p = x^q \} </math>
+|   an algebraic field || <hask>root</hask> || <hask>(^/)</hask> ||  rational  || list of polynomial zeros (length = denominator of the exponent) || <math> a^{\frac{p}{q}} = \{ x : a^p = x^q \} </math>
 |-
-|   positive real  || <hask> log </hask> || ^? || any ring with a notion of limit || exponential series || <math>a^b = \sum_{i=0}^{\infty} \frac{(b\cdot\ln a)^i}{i!} </math>
+|   positive real  || <hask>log</hask> || <hask>(^?)</hask> || any ring of characteristic zero with inverses for integers and a notion of limit || exponential series and logarithm || <math>a^b = \exp(b \log a) = \sum_{k \geq 0} \frac{(b \log a)^k}{k!}</math>
 |}
@@ Line 47: / Line 58: @@
-That is <hask>(^-)</hask> replaces <hask>(^^)</hask>,
+That is, <hask>(^-)</hask> replaces <hask>(^^)</hask>,
 <hask>(^?)</hask> replaces <hask>(**)</hask>,
 <hask>(^)</hask> remains and <hask>(^/)</hask> is new.

Difference between revisions of "Power function"

Latest revision as of 21:34, 10 March 2016

Contents

Question

Answer

Type inference reasons

Mathematical reasons

Power function in Numeric Prelude

See also

Navigation menu

Search