Using Swift to demonstrate finding powers with just adding (and some prep work).

AdjacentDifference.swift

import Foundation


/**
    A generator for the distance between two adjacent elements from another generator.
 */
public struct AdjacentDifferenceGenerator<Source: GeneratorType where Source.Element: Strideable>: GeneratorType {

    /// The last value read, needed to calculate the difference
    private var queue: (Source.Element?, Source.Element?)
    /// The generator of the values
    private var generator: Source

    /**
        - parameter generator: The source of the elements to differentiate.

        - postcondition: The first call of `self.next()` will call `self.generator.next()` twice to obtain the first difference.  Subsequent calls to `next` will call the inner-`next` just once, to compare with the formerly most recent element.
     */
    public init(generator: Source) {
        self.queue = (nil, nil)
        self.generator = generator
    }

    mutating public func next() -> Source.Element.Stride? {
        guard let newOne = self.generator.next() else {
            return nil
        }

        self.queue = (self.queue.1, newOne)
        if self.queue.0 == nil {
            if let newTwo = self.generator.next() {
                self.queue = (newOne, newTwo)
            } else {
                return nil
            }
        }
        return self.queue.0!.distanceTo(self.queue.1!)
    }

}

/**
    A generator for arrays of adjacent differences.
*/
public struct AdjacentDifferenceArrayGenerator<T: Strideable where T.Stride == T>: GeneratorType {

    /// The array to reduce each turn
    private var array: [T]

    /**
        - parameter source: The sequence where the first set of differences will be taken.

        - postcondition: The first call to `self.next()` returns that first set of differences.  Later calls return the differences among the previous set of differences.
     */
    public init<U: SequenceType where U.Generator.Element == T>(source: U) {
        self.array = source.adjacentDifference()
    }

    public mutating func next() -> [T]? {
        guard !array.isEmpty else {
            return nil
        }
        defer {
            self.array = self.array.adjacentDifference()
        }

        return self.array
    }

}

// MARK: - Extensions

public extension SequenceType where Generator.Element: Strideable {

    /**
        - returns: For the subsequence from the second element on, a corresponding distance from the target element's predecessor's value to the target element's value.  Empty and single-element sequences return an empty array.

        - todo: Handle laziness (with additional types and an extension).
    */
    public func adjacentDifference() -> [Self.Generator.Element.Stride] {
        var result: [Self.Generator.Element.Stride] = []
        var generator = AdjacentDifferenceGenerator(generator: self.generate())
        while let difference = generator.next() {
            result.append(difference)
        }
        return result
    }

}

public extension SequenceType where Generator.Element: Strideable, Generator.Element.Stride: Strideable, Generator.Element.Stride.Stride == Generator.Element.Stride {

    /// - returns: Start with the array of adjacent differences for this sequence.  Return a two-dimensional array with the first adjacent differences array then the array made from adjacent differences of the previous adjacent difference array, until an difference array of one element is made.  Empty and single sequences return an empty array.
    public func pyramidOfAdjacentDifferences() -> [[Self.Generator.Element.Stride]] {
        var result = [self.adjacentDifference()]
        if result.first!.isEmpty {
            return []
        }

        var generator = AdjacentDifferenceArrayGenerator(source: result.first!)
        while let differences = generator.next() {
            result.append(differences)
        }
        return result
    }
    
}

Factorial.swift

import Foundation


/**
    A generator for the factorials.  The first return from `next` is 0! and each increment adds one to the counter.
 */
public struct FactorialGenerator<Counter: IntegerType>: GeneratorType {

    /// The counter for the next factor to multiply
    private var counter: Counter = 0
    /// The running factorial result
    private var factorial: Counter = 1

    public init() {
    }

    mutating public func next() -> Counter? {
        defer {
            self.counter = self.counter.successor()
            self.factorial *= self.counter
        }

        return self.factorial
    }

}

/**
    A generator for a number and its factorial as a tuple (in that order).  The first return from `next` is `(0, 0!)`.
 */
public struct FactorialPairGenerator<Counter: IntegerType>: GeneratorType {

    /// The computer that does the core work
    private var factorializer = FactorialGenerator<Counter>()
    /// The counter for the iterations
    private var counter: Counter = 0

    public init() {
    }

    mutating public func next() -> (Counter, Counter)? {
        defer {
            self.counter = self.counter.successor()
        }

        return (self.counter, self.factorializer.next()!)
    }

}

/**
    - precondition: `x >= 0`.

    - parameter x: The number to have its factorial taken.

    - returns: `x`!
 */
public func factorial<Counter: IntegerType>(x: Counter) -> Counter {
    precondition(x >= 0)

    var results: (Counter, Counter)
    var factorializer = FactorialPairGenerator<Counter>()
    repeat {
        results = factorializer.next()!
    } while results.0 < x
    return results.1
}

Pascal's Triangle.swift

import Foundation


/**
    Generates the rows of Pascal's Triangle, whose elements are the binominal coeffiecents.  (Row n, column k is CHOOSE(n, k).)
*/
public struct PascalsTriangleRowGenerator<T: IntegerType>: GeneratorType {

    /// The next row of Pascal's Triangle
    private var array: [T]

    /**
        - precondition: `row >= 0`.

        - parameter row: The row of Pascal's Triangle to generate.

        - returns: The given `row` of the triangle.  (It has `row + 1` elements.)
     */
    public static func computeRow(row: Int) -> [T] {
        precondition(row >= 0)

        var result = [T]()
        result.reserveCapacity(row + 1)
        result.append(1)
        var bottom: T = 1
        var top = bottom.advancedBy(numericCast(row - 1))
        for _ in 1.stride(through: row / 2, by: +1) {
            result.append(result.last! * top / bottom)
            bottom = bottom.successor()
            top = top.predecessor()
        }
        for i in (row / 2 + 1).stride(through: row, by: +1) {
            result.append(result[row - i])
        }
        return result
    }

    /**
        - precondition: `newRow >= 0`.

        - parameter nextRow: The index of the row returned by the first call to `self.next()`.  Defaults to zero.

        - postcondition: Each subsequent call to `self.next()` returns the following row of Pascal's Triangle.
     */
    public init(nextRow: Int = 0) {
        self.array = self.dynamicType.computeRow(nextRow)
    }

    public mutating func next() -> [T]? {
        defer {
            for i in (self.array.count - 1).stride(to: 0, by: -1) {
                self.array[i] += self.array[i - 1]
            }
            self.array.append(1)
        }

        return self.array
    }

}

/**
    Caches rows of Pascal's Triangle so they're not continuously re-evaluated.
*/
public class PascalsTriangleCache<T: IntegerType> {

    /// The rows already calculated
    private var cache: [Int: [T]] = [:]
    /// The method to get new rows
    private var generator = PascalsTriangleRowGenerator<T>()

    /// Fill the cache
    private func generateRow(row: Int) {
        guard self.cache[row] == nil else {
            return  // The node is already present
        }
        precondition(row >= 0)

        repeat {
            let newRow = self.generator.next()!
            self.cache[newRow.count - 1] = newRow
        } while self.cache[row] == nil
    }

    public init() {
    }

    /**
        - precondition: `row >= 0`

        - parameter row: The row of Pascal's Triangle to get.

        - returns: The desired row of Pascal's Triangle.

        - note: There is no setter.
     */
    public subscript(row: Int) -> [T] {
        self.generateRow(row)
        return self.cache[row]!
    }

}

Power.swift

import Foundation


/**
    Generator for exponentiation: constant base, incrementing exponent.
 */
public struct PowerThroughExponentGenerator<T: IntegerType>: GeneratorType {

    /// The base of the powering
    public let base: T
    /// The exponent of the next powering
    public private(set) var exponent: Int
    /// The last power generated
    private var power: T

    /**
        - precondition: `nextExponent >= 0`.

        - parameter base: The base of all powers given.
        - parameter nextExponent: The exponent of the power on the first return of `self.next()`.  Defaults to zero.

        - postcondition: After each call of `self.next()`, the exponent used increments by one.
    */
    public init(base: T, nextExponent: Int = 0) {
        precondition(nextExponent >= 0)

        self.base = base
        self.exponent = nextExponent
        self.power = 1

        for _ in 0..<nextExponent {
            self.power *= base
        }
    }

    mutating public func next() -> T? {
        defer {
            self.power *= self.base
            self.exponent = self.exponent.successor()
        }

        return self.power
    }

}

/**
    - precondition: `exponent >= 0`.

    - parameter base: The base of the power.
    - parameter exponent: The exponent of the power.

    - returns: `base^exponent`.
*/
public func powi<T: IntegerType>(base: T, exponent: Int) -> T {
    var computer = PowerThroughExponentGenerator<T>(base: base, nextExponent: exponent)
    return computer.next()!
}

/**
    Create a differnce array with raw multiplications for exponentiation and full subtraction rounds.

    - precondition: `exponent >= 0`.

    - parameter base: The base for the first power to be raised.
    - parameter exponent: The exponent for any power to be raised.

    - returns: An array of `exponent + 1` elements, where:
        * `Elements[0] == base^exponent`.
        * `Elements[1]`, if it exists, is the difference from `Elements[0]` to `(base + 1)^exponent`.
        * `Elements[n]` is the difference `Elements[n - 1]` needs to add to properly step its predecessor on its first turn.  (`Elements[k]` first turn to be read is on turn `k`, where `k` is 1 on the first iteration of the system.)
 */
public func generateSeedsWithBruteForce<T: IntegerType where T.Stride == T>(atBase: T, exponent: Int) -> [T] {
    var powers = [Array<T>(atBase...atBase.advancedBy(numericCast(exponent))).map { powi($0, exponent: exponent) }]
    powers.appendContentsOf(powers.first!.pyramidOfAdjacentDifferences())
    return powers.map { $0.first! }
}

/**
    Create a difference array with just the bare number of polynomials calculated.  It has the same external behavior as `generateSeedsWithBruteForce`.
 */
public func generateSeedsWithPolynomials<T: IntegerType>(atBase: T, exponent: Int) -> [T] {
    var exponentPoly = UnivariatePolynomial<T>(coefficient: 1, exponent: exponent)
    let basePoly = UnivariatePolynomial<T>(looseCoefficients: atBase)
    let unitStep = UnivariatePolynomial<T>(looseCoefficients: 1, 1)
    var differences = Array<T>()
    for _ in 0.stride(through: exponent, by: +1) {
        differences.append((exponentPoly • basePoly)[0])
        exponentPoly = (exponentPoly • unitStep) - exponentPoly
    }
    return differences
}

/**
    Generator for exponentiation: incrementing base, constant exponent.
 */
public struct PowerThroughBaseGenerator<T: IntegerType>: GeneratorType {

    /// The base of the next powering
    public private(set) var base: T
    /// The exponent of the powering
    public let exponent: Int
    /// The number of iterations
    private var startingDelta: Int
    /// The list of differences to iterate
    private var deltas: [T]

    /**
        - precondition: `exponent >= 0`.

        - parameter nextBase: The base of the power on the first return of `self.next()`.
        - parameter exponent: The exponent of all powers given.
        - parameter seedGenerator: The function that, given a base and exponent, returns and array with the raised power followed by differences needed to iterate.  (The Nth-order delta is at index N.  *N* goes from 0 to `exponent` (inclusive).)  See more details at the docs for `generateSeedsWithBruteForce`; substitute functions have to have the same signature and return semantics.

        - postcondition: After each call of `self.next()`, the base used increments by one.
     */
    public init(nextBase: T, exponent: Int, seedGenerator: (T, Int) -> [T]) {
        precondition(exponent >= 0)

        self.deltas = seedGenerator(nextBase, exponent)
        self.startingDelta = 1
        self.exponent = exponent
        self.base = nextBase
    }

    mutating public func next() -> T? {
        defer {
            for i in min(self.exponent, self.startingDelta).stride(to: 0, by: -1) {
                self.deltas[i - 1] += self.deltas[i]
            }
            self.startingDelta = self.startingDelta.successor()
            self.base = self.base.successor()
        }

        return self.deltas.first!
    }

}

Univariate Polynomial.swift

import Foundation


/**
    Models a polynomial of one variable.
*/
public struct UnivariatePolynomial<T: IntegerType>: CustomStringConvertible {

    /// The coefficients for each term; index number is the corresponding power.
    private var coefficients: [T]
    /// The name of the indeterminate.  Make sure it's a single letter.
    public var indeterminate: String = "x"

    /// The degree of the polynominal.  A zero-value polynominal has a special degree < 0.
    public var degree: Int {
        return self.coefficients.count - 1
    }
    // The polynominal as an expression, using `indeterminate` as the variable name
    public var description: String {
        switch self.coefficients.count {
        case 0:
            return T.allZeros.description
        case 1:
            return self.coefficients.first!.description
        default:
            var result = "\(self.coefficients.last!)\(self.indeterminate)^\(self.degree)"
            for i in (self.degree - 1).stride(to: 0, by: -1) {
                if self.coefficients[i] != T.allZeros {
                    result += " + \(self.coefficients[i])\(self.indeterminate)^\(i)"
                }
            }
            if self.coefficients.first! != T.allZeros {
                result += " + \(self.coefficients.first!)"
            }
            return result
        }
    }

    /// Check that there's no leading zero coefficients
    private mutating func purgeZeros() {
        while !self.coefficients.isEmpty && self.coefficients.last! == T.allZeros {
            self.coefficients.popLast()
        }
    }

    /**
        - precondition: `degree >= 0`

        - parameter degree: The power of the term to be examined.

        - returns: (For getter) The coefficient of the term to be examined.

        - postcondition: (For setter) `self[degree] == newValue`.
    */
    public subscript(degree: Int) -> T {
        get {
            guard degree >= 0 && degree < self.coefficients.count else {
                return T.allZeros
            }

            return self.coefficients[degree]
        }

        set {
            precondition(degree >= 0)

            switch degree {
            case 0..<self.coefficients.count:
                self.coefficients[degree] = newValue
            case let x where x > self.coefficients.count:
                self.coefficients.appendContentsOf(Array<T>(count: x - self.coefficients.count, repeatedValue: T.allZeros))
                fallthrough
            default:  // degree == self.coefficients.count
                self.coefficients.append(newValue)
            }
            self.purgeZeros()
        }
    }

    /**
        Initialize using an array as the source of the initial coefficients.

        - parameter coefficients: The receiver's coefficients; element at index K is for the term with power K.

        - postcondition: Let *N* be the maximum of the indices whose elements are non-zero.  Then `self.degree == N`, `self[i] == coefficients[i]` for `0 <= i <= N`, and `self[i] == 0` for other values of `i`.
     */
    public init(coefficients: [T]) {
        self.coefficients = coefficients
        self.purgeZeros()
    }

    /**
        Initialize from a list of coefficients.

        - parameter coefficients: The receiver's coefficients, highest order first.

        - postcondition: `self.degree == N`, where *N* is the number of arguments after the first nonzero one (or a negative number if no nonzero arguments existed).  For a nonnegative *N*, `self[i]` from *N* to 0 gives the trailing arguments.
    */
    public init(looseCoefficients: T...) {
        self.init(coefficients: looseCoefficients.reverse())
    }

    /**
        Initialize from a single term.

        - precondition: `exponent >= 0`.

        - parameter coefficient: The coefficient of the single term.
        - parameter exponent: The power of the single term.

        - postcondition: `self[exponent] == coefficient`.  For `N != exponent`, `self[N] == 0`.
    */
    public init(coefficient: T, exponent: Int) {
        var coefficients = Array<T>(count: exponent, repeatedValue: T.allZeros)
        coefficients.append(coefficient)
        self.init(coefficients: coefficients)
    }

}

/**
    Subtract two polynomials.

    - parameter minuend: The minuend
    - parameter subtrahend: The subtrahend

    - returns: The difference
*/
public func -<T>(minuend: UnivariatePolynomial<T>, subtrahend: UnivariatePolynomial<T>) -> UnivariatePolynomial<T> {
    var result = Array<T>(count: max(minuend.degree, subtrahend.degree) + 1, repeatedValue: T.allZeros)
    for i in 0.stride(through: minuend.degree, by: +1) {
        result[i] = minuend[i]
    }
    for j in 0.stride(through: subtrahend.degree, by: +1) {
        result[j] -= subtrahend[j]
    }
    return UnivariatePolynomial(coefficients: result)
}

/**
    Scalar/Polynomial Multiplication, scalar first

    - parameter multiplier: The scalar first factor
    - parameter multiplicand: The polynomial second factor

    - returns: The product
 */
public func *<T>(multiplier: T, multiplicand: UnivariatePolynomial<T>) -> UnivariatePolynomial<T> {
    var result = Array<T>()
    result.reserveCapacity(multiplicand.degree + 1)
    for i in 0.stride(through: multiplicand.degree, by: +1) {
        result.append(multiplier * multiplicand[i])
    }
    return UnivariatePolynomial(coefficients: result)
}

/**
    Scalar/Polynomial Multiplication, scalar second

    - parameter multiplier: The polynomial first factor
    - parameter multiplicand: The scalar second factor

    - returns: The product
 */
public func *<T>(multiplier: UnivariatePolynomial<T>, multiplicand: T) -> UnivariatePolynomial<T> {
    var result = Array<T>()
    result.reserveCapacity(multiplier.degree + 1)
    for i in 0.stride(through: multiplier.degree, by: +1) {
        result.append(multiplier[i] * multiplicand)
    }
    return UnivariatePolynomial(coefficients: result)
}

/**
    Fused multiply-add

    - parameter augendMultiplier: The first factor for the product that makes up the augend
    - parameter augendMultiplicand: The second factor for the product that makes up the augend
    - parameter addend: The (second) addend

    - returns: The sum (of the product and addend)
 */
public func fma<T>(augendMultiplier augendMultiplier: UnivariatePolynomial<T>, augendMultiplicand: UnivariatePolynomial<T>, addend: UnivariatePolynomial<T>) -> UnivariatePolynomial<T> {
    guard augendMultiplier.degree >= 0 && augendMultiplicand.degree >= 0 else {
        return addend
    }

    var result = Array<T>(count: max(augendMultiplier.degree + augendMultiplicand.degree, addend.degree) + 1, repeatedValue: T.allZeros)
    for i in 0.stride(through: addend.degree, by: +1) {
        result[i] = addend[i]
    }
    for j in 0.stride(through: augendMultiplier.degree, by: +1) {
        for k in 0.stride(through: augendMultiplicand.degree, by: +1) {
            result[j + k] = augendMultiplier[j] * augendMultiplicand[k] + result[j + k]
        }
    }
    return UnivariatePolynomial(coefficients: result)
}

// Introduce the composition operator.
infix operator • {
    precedence 139
    associativity right
}

/**
    Compostition

    - parameter outer: The second polynomial function to be applied
    - parameter inner: The first polynomial function to be applied

    - returns: The outer polynomial with its indeterminate replaced by the inner polynomial, so re-expressing the outer polynomial in terms of the inner polynomial's indeterminate.

    - notes: Using a constant for `inner` evaluates the outer polynomial for that constant value.
 */
public func •<T>(outer: UnivariatePolynomial<T>, inner: UnivariatePolynomial<T>) -> UnivariatePolynomial<T> {
    guard outer.degree > 0 else {
        return outer  // A constant (including zero) polynomial doesn't change since it has no indeterminate to be substituted.
    }

    var result = UnivariatePolynomial(looseCoefficients: outer[outer.degree])
    for i in (outer.degree - 1).stride(through: 0, by: -1) {
        result = fma(augendMultiplier: result, augendMultiplicand: inner, addend: UnivariatePolynomial(looseCoefficients: outer[i]))
    }
    return result
}