factory-0.2.1.1: Rational arithmetic in an irrational world.

Factory.Math.DivideAndConquer

Contents

Description

`AUTHOR`
Dr. Alistair Ward
`DESCRIPTION`
• Provides a polymorphic algorithm, to unfold a list into a tree, to which an associative binary operator is then applied to re-fold the tree to a scalar.
• Implementations of this strategy have been provided for addition and multiplication, though other associative binary operators, like `gcd` or `lcm` could also be used.
• Where the contents of the list are consecutive, a more efficient implementation is available in Factory.Data.Interval.

Synopsis

# Types

## Type-synonyms

• The ratio of the original list-length at which to bisect.
• CAVEAT: the value can overflow.

type MinLength = Int Source

The list-length beneath which to terminate bisection.

# Functions

Arguments

 :: Monoid monoid => BisectionRatio The ratio of the original list-length at which to bisect. -> MinLength For efficiency, the list will not be bisected, when it's length has been reduced to this value. -> [monoid] The list on which to operate. -> monoid The resulting scalar.
• Reduces a list to a single scalar encapsulated in a `Monoid`, using a divide-and-conquer strategy, bisecting the list and recursively evaluating each part; http://en.wikipedia.org/wiki/Divide_and_conquer_algorithm.
• By choosing a `bisectionRatio` other than `(1 % 2)`, the bisection can be made asymmetrical. The specified ratio represents the length of the left-hand portion, over the original list-length; eg. `(1 % 3)` results in the first part, half the length of the second.
• This process of recursive bisection, is terminated beneath the specified minimum list-length, after which the monoid's binary operator is directly folded over the list.
• One can view this as a http://en.wikipedia.org/wiki/Hylomorphism_%28computer_science%29, in which the list is exploded into a binary tree-structure (each leaf of which contains a list of up to `minLength` integers, and each node of which contains an associative binary operator), and then collapsed to a scalar, by application of the operators.

Arguments

 :: Num n => BisectionRatio The ratio of the original list-length at which to bisect. -> MinLength For efficiency, the list will not be bisected, when it's length has been reduced to this value. -> [n] The numbers whose product is required. -> n The resulting product.
• Multiplies the specified list of numbers.
• Since the result can be large, `divideAndConquer` is used in an attempt to form operands of a similar order of magnitude, which creates scope for the use of more efficient multiplication-algorithms.

Arguments

 :: Num n => BisectionRatio The ratio of the original list-length at which to bisect. -> MinLength For efficiency, the list will not be bisected, when it's length has been reduced to this value. -> [n] The numbers whose sum is required. -> n The resulting sum.
• Sums the specified list of numbers.
• Since the result can be large, `divideAndConquer` is used in an attempt to form operands of a similar order of magnitude, which creates scope for the use of more efficient multiplication-algorithms. Multiplication is required for the addition of `Rational` numbers by cross-multiplication; this function is unlikely to be useful for other numbers.