When the numbers are represented as two logarithms the operation is reduced to adding two numbers again, so O(log(d) + [whatever the log/inverse log conversion cost is]).
This is pretty confused. First, if the d is the number of digits of a number, then you will need O(d) of memory to store its logarithm, otherwise you will loose a lot of precision. Thus, the addition of logarithms is still O(d), not O(log(d)).
Second, calculating log(x) and its inverse, exp(x) is much more expensive than multiplication. For example, if x is between 0 and 1, you can approximate exp(x) pretty well as 1 + x + x^2/2 + x^3/6 + x^4/24. This is 3 multiplications and 3 divisions just to convert.
> Thus, the addition of logarithms is still O(d), not O(log(d)).
Oh dear, yes that's wrong, thank you for catching that.
Still, O(d) a lot better than O(d²). And perhaps more importantly: division (which is even more painful to compute) is a simple matter of subtracting the logarithmic tranformations and then taking the exponent.
> Second, calculating log(x) and its inverse, exp(x) is much more expensive than multiplication.
You're not wrong, but you're talking about the costs of a computer doing the calculation. I was talking about a human doing calculations by hand. What I forgot to mention is that Mirifici Logarithmorum Canonis Descriptio contained 90 pages of precomputed tables. Multiplying two numbers is then a matter of two look-ups, one addition, and another look-up. For large enough numbers that's worth it (and "large enough" is reached pretty quickly in the case of calculations done by hand).
And shortly after the introduction of logarithms William Oughtred invented the slide rule, using two log scales to create an analog computer, removing the need for a table as well (depending on the precision required)
Yeah, if we are talking about humans, then this is definitely a big win: big table lookup is for a human faster than multiplication (not really true for computers), and slide rules make all the difference.
This is pretty confused. First, if the d is the number of digits of a number, then you will need O(d) of memory to store its logarithm, otherwise you will loose a lot of precision. Thus, the addition of logarithms is still O(d), not O(log(d)).
Second, calculating log(x) and its inverse, exp(x) is much more expensive than multiplication. For example, if x is between 0 and 1, you can approximate exp(x) pretty well as 1 + x + x^2/2 + x^3/6 + x^4/24. This is 3 multiplications and 3 divisions just to convert.