日志功能的复杂性是什么? [英] What is the complexity of the log function?

问题描述

基于日志10的功能的复杂性是什么?

推荐答案

这实际上取决于您要计算其对数值的值的域.

This really depends on the domain of what values you want to compute a logarithm of.

对于IEEE倍增，许多处理器可以在单个汇编指令中采用对数；例如，x86具有FYL2X和FYL2XP1指令.尽管通常这样的指令只会采用某个固定基数的对数，但是通过使用以下事实，它们可以用于采用任意基数的对数:

For IEEE doubles, many processors can take logarithms in a single assembly instruction; x86 has the FYL2X and FYL2XP1 instructions, for example. Although typically instructions like these will only take the logarithm in some fixed base, they can be used to take logarithms in arbitrary bases by using the fact that

log _a b = log _c b/log _c a

log_a b = log_c b / log_c a

只需取两个对数并找到它们的商即可.

by simply taking two logarithms and finding their quotient.

对于一般整数(任意精度)，您可以将重复平方与二进制搜索结合使用，以仅使用O(log log n)算术运算来取对数(每次对数字进行平方运算，则使指数翻倍)，这意味着只能在超出数值对数之前对数字对数进行平方n次，并且可以执行二进制搜索).使用一些带有斐波那契数的可爱技巧，您只能在O( log n)空间.如果您要计算二进制对数，则可以使用一些可爱的技巧移位以在较短的时间内计算该值(尽管渐进复杂度相同).

For general integers (of arbitrary precision), you can use repeated squaring combined with a binary search to take logarithms using only O(log log n) arithmetic operations (each time you square a number you double the exponent, which means you can only square the number log log n times before you've exceeded its value and can do a binary search). Using some cute tricks with Fibonacci numbers, you can do this in only O(log n) space. If you're computing the binary logarithm, there are some cute tricks you can use with bit shifts to compute the value in less time (though the asymptotic complexity is the same).

对于任意实数，逻辑更难.您可以使用牛顿方法或泰勒级数来计算对数，以达到一定的精度，尽管我承认我不熟悉执行此操作的方法.但是，您实际上很少需要这样做，因为大多数实数是IEEE的两倍，并且在那种情况下有更好的算法(甚至是硬件指令).

For arbitrary real numbers the logic is harder. You can use Newton's method or the Taylor series to compute logarithms to within a certain precision, though I confess that I'm not familiar with the methods for doing this. However, you rarely actually need to do this because most real numbers are IEEE doubles and there are better algorithms (or even hardware instructions) in that case.

希望这会有所帮助！

这篇关于日志功能的复杂性是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！