To be honest,
1. There is no need to compute `pow(E, result)` twice.
2. A fast numerical way should use polynomial approximation. see [musl
implementation](https://git.musl-libc.org/cgit/musl/tree/src/math/log.c)
3. `pow` should not be used, not to say inside while loop. Also,
implementation of `pow` often calls `log` internally.
4. Newton method is a fast method (the approximation speed is linear to
accuracy per iteration), but it doesn't mean direct implementation is fast.
5. A simple binary search (the approximation speed is constant per iteration)
is possible by making use of some basic properties `log2(x) = 1+log2(x/2) =
log2(x*x)/2`, no external library needed, no table lookup needed, no special
constant needed.
import std/monotimes
from std/math import pow, almostEqual, E, log2
from std/fenv import epsilon
proc simpleNewton(n: float64): float64 =
var next: float64 = 1.0
while not almostEqual(result, next, 1):
result = next
next = result - 1 + n/pow(2, result)
proc binarySearch(n: float64): float64 =
var x = n
var c = 1.0
while c > epsilon(float64):
if x >= 2:
result += c
x /= 2
elif x <= 1/2:
result -= c
x *= 2
else:
x = x*x
c /= 2
var t0 = high(int)
template timeit(name, code) =
block:
let s = getMonoTime()
var ans = 0.0
for i in 1..1000:
ans += code(i.float)
let e = getMonoTime()
let t = e.ticks - s.ticks
t0 = min(t0, t)
# echo t
echo name, ": time=", t, "\t(x", t/t0, ")\tans=", ans
timeit "math.log2 ", log2
timeit "binarySearch", binarySearch
timeit "simpleNewton", simpleNewton
# nim r -d:release play_log.nim
# math.log : time=28050 (x1.0)
ans=8529.398004204777
# binarySearch: time=762358 (x27.17853832442068)
ans=8529.398004204777
# simpleNewton: time=16559248 (x590.34752228164)
ans=8529.398004204781
Run
6. The way calculating `result` in simpleNewton **may** accumulates and
propagates numerical error sightly higher than the others as shown above.
