factory-0.0.0.2: 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.Bounds.

Synopsis

Types

Type-synonyms

type BisectionRatio = Ratio IntSource

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

type MinLength = IntSource

The list-length beneath which to terminate bisection.

Functions

divideAndConquerSource

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.

product'Source

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.

sum'Source

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.