openMSX
utils
fast_log2.hh
Go to the documentation of this file.
1
#ifndef FAST_LOG2_HH
2
#define FAST_LOG2_HH
3
4
// Based on:
5
// fast_log
6
// https://github.com/nadavrot/fast_log/tree/main
7
// MIT License
8
// Copyright (c) 2022 Nadav Rotem
9
//
10
// This version is modified/simplified to better suite openMSX:
11
// * double -> float
12
// * simplified fast_frexpf() (no longer works for negative or zero values)
13
// * calculate log base-2 instead of natural-log.
14
15
// Main advantage over std::log() or std::log2():
16
// * A lot faster, and can be (auto-)vectorized (verified gcc-11 and above)
17
// Main disadvantage:
18
// * Not as accurate, max error: ~0.25%. std::log() is accurate to 1 ULP.
19
20
#include <bit>
21
#include <cstdint>
22
#include <utility>
23
24
// Similar to std::frexp():
25
// decompose 'x' into 'm' and 'e' so that
26
// x == m * pow(2, e)
27
// with: 0.5 <= m < 1.0
28
// This function has some limitations
29
// * It doesn't work at all for negative values.
30
// * It gives an inaccurate result for x=0 (it returns m=0.5, e=-126, that's
31
// very close but not exact).
32
// These limitations allow this version to be much faster: it can easily be
33
// inlined and it's suitable for (auto-)vectorization.
34
inline
std::pair<float, int>
fast_frexpf
(
float
x)
35
{
36
// See: https://en.wikipedia.org/wiki/IEEE_754#Basic_and_interchange_formats
37
auto
bits = std::bit_cast<uint32_t>(x);
38
//if (bits == 0) return {0.0f, 0};
39
auto
mantissa = bits & 0x007fffff;
40
auto
exponent = bits >> 23;
// note: wrong if x < 0
41
auto
frac = std::bit_cast<float>(mantissa | 0x3f000000);
42
return
{frac, exponent - 126};
43
}
44
45
// Compute a fast _approximation_ for the base-2 logarithm of 'x'.
46
inline
float
fast_log2
(
float
x)
47
{
48
auto
[m, exp] =
fast_frexpf
(x);
// split x into: x == pow(2, exp) * m
49
50
// Use a degree-3 polynomial to approximate log2(m) over the interval [0.5, 1)
51
// val = a*pow(m,3) + b*pow(m,2) + c*m + d
52
static
constexpr
float
a = 1.33755322f;
53
static
constexpr
float
b = -4.42852392f;
54
static
constexpr
float
c = 6.30371424f;
55
static
constexpr
float
d = -3.21430967f;
56
float
val = d + m * (c + m * (b + m * a));
57
58
return
float(exp) + val;
59
}
60
61
#endif
fast_log2
float fast_log2(float x)
Definition
fast_log2.hh:46
fast_frexpf
std::pair< float, int > fast_frexpf(float x)
Definition
fast_log2.hh:34
Generated on Sun Sep 8 2024 00:13:40 for openMSX by
1.9.8