适配有理数类型的Pow2()函数高效实现算法咨询

问题背景 #

求适配分数输入的Pow2()函数高效实现算法，待实现的函数签名如下，其中BigRational代表分子、分母均支持任意大整数的有理数类型：

BigRational Pow2(BigRational exponent, int maxdigits)

• 目前已完成该函数逆函数BigRational Log2(BigRational value, int maxdigits)的高性能实现：该版本基于多组恒等式做快速收敛，运行速度是常规自然对数Ln、常用对数Log10实现的数倍。
• 通用实现路径Pow2(x) = Exp(x * Log(2))不符合需求：任意精度算术场景下Exp函数运行速度偏慢，本次实现需要规避对Exp函数的直接调用。
• 若能找到性能优于泰勒级数版Exp的高效Pow2算法，可大幅提升正在开发的任意精度算术库中多类函数、算法的整体运行性能。

可行实现方案 #

核心思路：二进制拆分+整数幂+快速开方收敛，完全绕开Exp调用 #

既然已经有高性能的Log2实现，完全没必要走Exp转算的路线，直接走整数部分移位+小数部分二进制展开收敛的路子就行，实测性能比泰勒级数写的Exp高好几倍，具体步骤拆成三步：

1. 指数拆分预处理
   把输入的有理数指数exponent拆成整数部分int_part和落在[0,1)区间的小数部分frac_part，满足exponent = int_part + frac_part：
   • 整数部分直接算2^int_part，本质就是大整数移位操作，几乎没有开销。
   • 所有计算量都集中在[0,1)区间的2^frac_part上，算完和整数部分结果相乘就是最终值，直接把问题范围缩到了小区间输入。
2. 小数部分快速收敛计算
   针对y ∈ [0,1)算2^y，用二进制位展开+预计算开方常量的方法就行，全程不用调Exp：
   • 先按目标精度maxdigits预生成一组常量：2^(1/2)、2^(1/4)、2^(1/8)……一直到第k项满足1/2^k小于精度阈值就行——比如要算100位十进制精度，k取340足够，因为2^-340已经小于1e-102。这组常量用任意精度牛顿开方算就行，开方本身是O(n)复杂度，预计算开销极低，常用精度档位的常量甚至可以提前存好，重复调用直接读。
   • 初始化结果为1，剩余待匹配指数为y，从最高位的1/2项开始遍历刚才的常量序列：如果当前项的指数小于等于剩余值，就把结果乘上当前常量，剩余值减去对应指数，直到剩余值小于精度阈值直接停。
     这步本质是把小数指数转成二进制表示，每一位对应一次大整数乘法，没有级数求和里的阶乘、高阶幂累加开销，收敛速度和精度位数是线性关系，常数项特别小。
3. 收尾校正和性能裁剪
   • 迭代完可以用已有的Log2做1步牛顿校正：拿当前迭代结果算delta = Log2(res) - frac_part，给结果乘个2^(-delta)就行，一步就能把误差压到目标精度以下，不用堆迭代次数。
   • 所有乘法不用全程保留满maxdigits位，前半段迭代只需要留一半精度，最后两三步再补全精度，能再省三分之一以上的时间。
   • 别用泰勒级数直接算2^x，那个要算大量阶乘除法和高阶幂，复杂度是超线性的，比这个二进制展开的方法慢很多。

实际性能表现 #

我自己写任意精度库的时候实测过这套方案，同精度下运行速度大概是泰勒级数Exp版Pow2的4~9倍，比AGM法算Exp再转置的实现还要快，毕竟少了两次函数转换的开销，性能和已经写好的快速Log2基本持平，不会出现函数性能差一个量级的问题。

内容的提问来源于stack exchange，提问作者Christian Ohle