Divide and conquer for function compositions

Question

I was searching the algorithm for finding the composition of 2 linear functions n times (where n can be as large as 10^18) in O(log n) time. I just got a pdf containing polynomial composition of 2 functions with large degrees using divide and conquer algorithm.

I was wondering whether my problem for composition of linear function n times can also be solved using divide and conquer algorithm in O(log n) complexity?

If yes, please explain the algorithm.

Thanks, in advance.

EDIT 1: The composition of function f(x) n times is fofof...n-times. Here the function is to be composed to itself n times. There are no 2 functions.

Hint: you're looking for a variation of the square-and-multiply algorithm. — John Dvorak
This question will probably get more attention on math.stackexchange. — Aseem Baranwal
The question is too unclear...what are your functions? What do you expect when you say composition n times? If n=2, does it mean fog or fogofog or fogog, etc. — vish4071
The composition of two linear functions is a linear function, no matter the field. Have fun. — John Dvorak

Paul Hankin Paul Hankin · Accepted Answer · 2015-12-30T08:31:20

You can represent the application of a linear function f(x) = ax + b as a 2-by-2 matrix multiplied by the vector (x, 1).

(f(x)) = ( a b ) (x)
( 1  )   ( 0 1 ) (1)

Applying f n times to x is multiplying the matrix n times to (x, 1), or equivalently, multiplying the matrix raised to the power of n to (x, 1).

(f^n(x)) = ( a b )^n (x)
(  1   )   ( 0 1 )   (1)

You can compute the matrix power using exponentiation by squaring.

This works whether you're working over the real numbers, the integers, or the integers modulo some number M.

Divide and conquer for function compositions

1 Answers