factory-0.3.0.0: 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; https://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 https://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.