3^100的位数判断

3^100的位数判断

问题来源

字节面试，面试官提问：口算估计3^100的位数，或是给出位数估计范围。

解决方案

方法一：

该方法纯口算，可得一个较为准确的一个范围
$2^{100}<3^{100}<4^{100}$
$2^{100}$位数判断
$2^{100}=(2^{10}{)}^{10}=1024^{10}\approx 1000^{10}=10^{30}$ 是31位数字
$4^{100}$位数判断
由于$4^{100}=(2^{100}{)}^2$
故$4^{100}=10^{60}$是62位数字
故位数介于31与62之间
又$x^{100}$函数的二阶导数>0
故$x^{100}$为凹函数，故位数介于46与62之间
又$3^{100}=9^{50}<10^{50}$ 故小于是51位数字
综上：位数介于46与51之间

方法二：

$3^4=81=80\ast (\frac{81}{80})$
$3^{100}=80^{25}\ast (\frac{81}{80}{)}^{25}$
$=2^{75}\ast 10^{25}\ast (\frac{81}{80}{)}^{25}$
$=32\ast 1024^7\ast 10^{25}\ast (\frac{81}{80}{)}^{25}$
$=3.2\ast (1.024{)}^7\ast 10^{47}\ast (\frac{81}{80}{)}^{25}$
现在我们估计 $(\frac{81}{80}{)}^{25}$：它小于 $(81/80)\ast (80/79)\ast ...\ast (57/56)=81/56<1.5$
类似的方法显示 $1.024^7<1.03^7<(103/100)\ast (100/97)\ast ...\ast (85/82)=103/82<104/80=1.3$
$3.2\ast 10^{47}<3^{100}<3.2\ast 1.5\ast 1.3\ast 10^{47}<10^{48}$
所以48位数字。

方法三：

该方法的关键是计算${\log }_{10}3$
${\log }_{10}3=\ln 3/\ln 10$
又

对于$ln3$
$x=3，y=1/2$
二阶展开结果为$1\ast (1+1/12)=1.1$
对于$ln10$
$x=10，y=9/11$
二阶展开结果为$18/11\ast (1+81/363)$ = 2
计算的$100\ast (1.1/2)+1=56$
对于$ln3$
$x=3，y=1/2$
对于$ln10$
三阶展开结果为$1\ast (1+1/12+1/80)=1.1$
$x=10，y=9/11$
三阶展开结果为2.3
计算的100*1.1/2.3+1 = 49

总结

由于是计算机相关面试，很容易联想到使用$2^{100}$与$4^{100}=(2^2{)}^{100}=(2^{100}{)}^2$尝试确定范围，结合$x^{100}$函数性态确定为46-62位数，实际上，笔者面试时就是思考到这一步，没有想到与$3^{100}=9^{50}$进一步确定范围。
方法二先将$3^{100}$转为$3.2\ast (1.024{)}^7\ast 10^{47}\ast (\frac{81}{80}{)}^{25}$ 再进行适当缩放判断$(\frac{81}{80}{)}^{25}$与$1.024^7$，该方法关键在于底数与对数的转换以及分数的裂项相消。
方法三是判断位数的常规方法，该方法关键在于对数${\log }_{10}3$的估算。

参考文献

方法二参考 3的100次方是多少位数？评论区方法
方法三部分参考ChatGPT

原创不易
转载请标明出处
如果对你有所帮助 别忘啦点赞支持哈