Logarithm calculations
Problem Description
Logarithms were quickly adopted by scientists because of various useful properties that simplified long, tedious calculations. In particular, scientists could find the product of two numbers m and n by looking up each number’s logarithm in a special table, adding the logarithms together, and then consulting the table again to find the number with that calculated logarithm (known as its antilogarithm). Expressed in terms of common logarithms, this relationship is given by log mn = log m + log n. For example, 100 × 1,000 can be calculated by looking up the logarithms of 100 (2) and 1,000 (3), adding the logarithms together (5), and then finding its antilogarithm (100,000) in the table. Similarly, division problems are converted into subtraction problems with logarithms: log m/n = log m − log n.
Bounds Chart
Step Chart
Improvement Table
| Complexity Classes | Algorithm Paper Links | Lower Bounds Paper Links |
|---|---|---|
| Exp/Factorial | [NA Trial Multiplication (1940)]
[NA Index calculus algorithm (1922)] [NA Number field sieve (1990)] |
|
| Polynomial > 3 | ||
| Cubic | ||
| Quadratic | ||
| nlogn | ||
| Linear | ||
| logn |