函数组合的分而治之
Divide and conquer for function compositions
我正在搜索用于在 O(log n) 时间内找到 2 个线性函数的组合的算法 n 次（其中 n 可以大到 10^18）。我刚得到一个 pdf，其中包含使用分而治之算法的 2 个大度数函数的多项式组合。
我想知道我的n次线性函数组合问题是否也可以使用O(log n)复杂度的分而治之算法来解决？
如果是，请说明算法。
提前致谢。
编辑 1: 函数 f(x) n 次的组合是 fofof...n 次。这里的函数要自己组合 n 次。没有2个函数。
您可以将线性函数 f(x) = ax + b 的应用表示为 2×2 矩阵乘以向量 (x, 1)。
(f(x)) = ( a b ) (x)
( 1 ) ( 0 1 ) (1)
将 f n 次应用于 x 是将矩阵 n 次乘以 (x, 1)，或者等价地，将矩阵的 n 次方乘以 (x, 1)。
(f^n(x)) = ( a b )^n (x)
( 1 ) ( 0 1 ) (1)
您可以通过平方求幂来计算矩阵幂。
无论您是处理实数、整数还是对某个数 M 取模的整数，这都适用。
我正在搜索用于在 O(log n) 时间内找到 2 个线性函数的组合的算法 n 次（其中 n 可以大到 10^18）。我刚得到一个 pdf，其中包含使用分而治之算法的 2 个大度数函数的多项式组合。
我想知道我的n次线性函数组合问题是否也可以使用O(log n)复杂度的分而治之算法来解决？
如果是，请说明算法。
提前致谢。
编辑 1: 函数 f(x) n 次的组合是 fofof...n 次。这里的函数要自己组合 n 次。没有2个函数。
您可以将线性函数 f(x) = ax + b 的应用表示为 2×2 矩阵乘以向量 (x, 1)。
(f(x)) = ( a b ) (x)
( 1 ) ( 0 1 ) (1)
将 f n 次应用于 x 是将矩阵 n 次乘以 (x, 1)，或者等价地，将矩阵的 n 次方乘以 (x, 1)。
(f^n(x)) = ( a b )^n (x)
( 1 ) ( 0 1 ) (1)
您可以通过平方求幂来计算矩阵幂。
无论您是处理实数、整数还是对某个数 M 取模的整数，这都适用。