c算法 - 问题

Question

我应该使用什么样的算法来计算2 ^ n..其中n总是大于100..使用c :)建议一个好的算法

Answer 1

要使用log(n)复杂度计算2 ^ n,您可以执行以下操作(假设类型可以存储我们得到的结果):

type result = 1;
type temp = 2;

while (n){
   if (n%2)
     result *= temp;
   temp *= temp;
   n/=2;
}

Answer 2

可能你应该搜索bigint格式从二进制转换为十进制的算法.请注意,您在二进制系统中的数字将表示为

100...00 // n - 1 zeros 

在二进制到十进制之间进行一次转换将比执行log(n)乘法运算快得多bigint.

如果你真的想要使用很多乘法,请阅读Karatsuba乘法

编辑:这篇博文提出了一种使用一个双精度浮点变量计算2 ^ 1023的方法