NonRecursiveBinaryDecomp.py

def getMatrix(matrix, turns):
    """
    returns a matrix represents the number of unique paths starting in one position and ending in another in N turns
    """

    # get an array of the binary powers we need to calculate
    baseTwoArray = getArrayOfPowersOfTwos(turns)

    # start with an identity matrix
    resultMatrix = np.identity(matrix.shape[0], dtype=object)

    # we need to remember the last power used so we can calculate how many times we need to
    # square the current matrix based on the last call.
    lastPower = 0

    for nextPower in baseTwoArray:

        # calculates how many times to square the matrix
        timesToSquare = nextPower - lastPower

        # calculate the next matrix power
        matrix = getBaseTwoTurnsMatrix(matrix, timesToSquare)
        
        # store the cumulative Matrix
        resultMatrix = resultMatrix*matrix
        
        lastPower = nextPower

    return resultMatrix