c++ - Qt中的qFastSin原理

Question

inline qreal qFastSin(qreal x)
{
    int si = int(x * (0.5 * QT_SINE_TABLE_SIZE / M_PI)); // Would be more accurate with qRound, but slower.
    qreal d = x - si * (2.0 * M_PI / QT_SINE_TABLE_SIZE);
    int ci = si + QT_SINE_TABLE_SIZE / 4;
    si &= QT_SINE_TABLE_SIZE - 1;
    ci &= QT_SINE_TABLE_SIZE - 1;
    return qt_sine_table[si] + (qt_sine_table[ci] - 0.5 * qt_sine_table[si] * d) * d;
}

这个qt_sine_table是一张长度为QT_SINE_TABLE_SIZE(256)的实数表。

const qreal qt_sine_table[QT_SINE_TABLE_SIZE] = {
    qreal(0.0),
    qreal(0.024541228522912288),
    qreal(0.049067674327418015),
    qreal(0.073564563599667426),
    qreal(0.098017140329560604),
    qreal(0.1224106751992162),
    qreal(0.14673047445536175),
    qreal(0.17096188876030122),
    qreal(0.19509032201612825),
    qreal(0.2191012401568698),
    qreal(0.24298017990326387),
    qreal(0.26671275747489837),
    qreal(0.29028467725446233),
    qreal(0.31368174039889152),
    qreal(0.33688985339222005),
    qreal(0.35989503653498811),
    qreal(0.38268343236508978),
    qreal(0.40524131400498986),
    qreal(0.42755509343028208),
    qreal(0.44961132965460654),
    qreal(0.47139673682599764),
    qreal(0.49289819222978404),
    qreal(0.51410274419322166),
    qreal(0.53499761988709715),
    qreal(0.55557023301960218),
    qreal(0.57580819141784534),
    qreal(0.59569930449243336),
    qreal(0.61523159058062682),
    qreal(0.63439328416364549),
    qreal(0.65317284295377676),
    qreal(0.67155895484701833),
    qreal(0.68954054473706683),
    qreal(0.70710678118654746),
    qreal(0.72424708295146689),
    qreal(0.74095112535495911),
    qreal(0.75720884650648446),
    qreal(0.77301045336273699),
    qreal(0.78834642762660623),
    qreal(0.80320753148064483),
    qreal(0.81758481315158371),
    qreal(0.83146961230254524),
    qreal(0.84485356524970701),
    qreal(0.85772861000027212),
    qreal(0.87008699110871135),
    qreal(0.88192126434835494),
    qreal(0.89322430119551532),
    qreal(0.90398929312344334),
    qreal(0.91420975570353069),
    qreal(0.92387953251128674),
    qreal(0.93299279883473885),
    qreal(0.94154406518302081),
    qreal(0.94952818059303667),
    qreal(0.95694033573220894),
    qreal(0.96377606579543984),
    qreal(0.97003125319454397),
    qreal(0.97570213003852857),
    qreal(0.98078528040323043),
    qreal(0.98527764238894122),
    qreal(0.98917650996478101),
    qreal(0.99247953459870997),
    qreal(0.99518472667219682),
    qreal(0.99729045667869021),
    qreal(0.99879545620517241),
    qreal(0.99969881869620425),
    qreal(1.0),
    qreal(0.99969881869620425),
    qreal(0.99879545620517241),
    qreal(0.99729045667869021),
    qreal(0.99518472667219693),
    qreal(0.99247953459870997),
    qreal(0.98917650996478101),
    qreal(0.98527764238894122),
    qreal(0.98078528040323043),
    qreal(0.97570213003852857),
    qreal(0.97003125319454397),
    qreal(0.96377606579543984),
    qreal(0.95694033573220894),
    qreal(0.94952818059303667),
    qreal(0.94154406518302081),
    qreal(0.93299279883473885),
    qreal(0.92387953251128674),
    qreal(0.91420975570353069),
    qreal(0.90398929312344345),
    qreal(0.89322430119551521),
    qreal(0.88192126434835505),
    qreal(0.87008699110871146),
    qreal(0.85772861000027212),
    qreal(0.84485356524970723),
    qreal(0.83146961230254546),
    qreal(0.81758481315158371),
    qreal(0.80320753148064494),
    qreal(0.78834642762660634),
    qreal(0.7730104533627371),
    qreal(0.75720884650648468),
    qreal(0.74095112535495899),
    qreal(0.72424708295146689),
    qreal(0.70710678118654757),
    qreal(0.68954054473706705),
    qreal(0.67155895484701855),
    qreal(0.65317284295377664),
    qreal(0.63439328416364549),
    qreal(0.61523159058062693),
    qreal(0.59569930449243347),
    qreal(0.57580819141784545),
    qreal(0.55557023301960218),
    qreal(0.53499761988709715),
    qreal(0.51410274419322177),
    qreal(0.49289819222978415),
    qreal(0.47139673682599786),
    qreal(0.44961132965460687),
    qreal(0.42755509343028203),
    qreal(0.40524131400498992),
    qreal(0.38268343236508989),
    qreal(0.35989503653498833),
    qreal(0.33688985339222033),
    qreal(0.31368174039889141),
    qreal(0.29028467725446239),
    qreal(0.26671275747489848),
    qreal(0.24298017990326407),
    qreal(0.21910124015687005),
    qreal(0.19509032201612861),
    qreal(0.17096188876030122),
    qreal(0.1467304744553618),
    qreal(0.12241067519921635),
    qreal(0.098017140329560826),
    qreal(0.073564563599667732),
    qreal(0.049067674327417966),
    qreal(0.024541228522912326),
    qreal(0.0),
    qreal(-0.02454122852291208),
    qreal(-0.049067674327417724),
    qreal(-0.073564563599667496),
    qreal(-0.09801714032956059),
    qreal(-0.1224106751992161),
    qreal(-0.14673047445536158),
    qreal(-0.17096188876030097),
    qreal(-0.19509032201612836),
    qreal(-0.2191012401568698),
    qreal(-0.24298017990326382),
    qreal(-0.26671275747489825),
    qreal(-0.29028467725446211),
    qreal(-0.31368174039889118),
    qreal(-0.33688985339222011),
    qreal(-0.35989503653498811),
    qreal(-0.38268343236508967),
    qreal(-0.40524131400498969),
    qreal(-0.42755509343028181),
    qreal(-0.44961132965460665),
    qreal(-0.47139673682599764),
    qreal(-0.49289819222978393),
    qreal(-0.51410274419322155),
    qreal(-0.53499761988709693),
    qreal(-0.55557023301960196),
    qreal(-0.57580819141784534),
    qreal(-0.59569930449243325),
    qreal(-0.61523159058062671),
    qreal(-0.63439328416364527),
    qreal(-0.65317284295377653),
    qreal(-0.67155895484701844),
    qreal(-0.68954054473706683),
    qreal(-0.70710678118654746),
    qreal(-0.72424708295146678),
    qreal(-0.74095112535495888),
    qreal(-0.75720884650648423),
    qreal(-0.77301045336273666),
    qreal(-0.78834642762660589),
    qreal(-0.80320753148064505),
    qreal(-0.81758481315158382),
    qreal(-0.83146961230254524),
    qreal(-0.84485356524970701),
    qreal(-0.85772861000027201),
    qreal(-0.87008699110871135),
    qreal(-0.88192126434835494),
    qreal(-0.89322430119551521),
    qreal(-0.90398929312344312),
    qreal(-0.91420975570353047),
    qreal(-0.92387953251128652),
    qreal(-0.93299279883473896),
    qreal(-0.94154406518302081),
    qreal(-0.94952818059303667),
    qreal(-0.95694033573220882),
    qreal(-0.96377606579543984),
    qreal(-0.97003125319454397),
    qreal(-0.97570213003852846),
    qreal(-0.98078528040323032),
    qreal(-0.98527764238894111),
    qreal(-0.9891765099647809),
    qreal(-0.99247953459871008),
    qreal(-0.99518472667219693),
    qreal(-0.99729045667869021),
    qreal(-0.99879545620517241),
    qreal(-0.99969881869620425),
    qreal(-1.0),
    qreal(-0.99969881869620425),
    qreal(-0.99879545620517241),
    qreal(-0.99729045667869021),
    qreal(-0.99518472667219693),
    qreal(-0.99247953459871008),
    qreal(-0.9891765099647809),
    qreal(-0.98527764238894122),
    qreal(-0.98078528040323043),
    qreal(-0.97570213003852857),
    qreal(-0.97003125319454397),
    qreal(-0.96377606579543995),
    qreal(-0.95694033573220894),
    qreal(-0.94952818059303679),
    qreal(-0.94154406518302092),
    qreal(-0.93299279883473907),
    qreal(-0.92387953251128663),
    qreal(-0.91420975570353058),
    qreal(-0.90398929312344334),
    qreal(-0.89322430119551532),
    qreal(-0.88192126434835505),
    qreal(-0.87008699110871146),
    qreal(-0.85772861000027223),
    qreal(-0.84485356524970723),
    qreal(-0.83146961230254546),
    qreal(-0.81758481315158404),
    qreal(-0.80320753148064528),
    qreal(-0.78834642762660612),
    qreal(-0.77301045336273688),
    qreal(-0.75720884650648457),
    qreal(-0.74095112535495911),
    qreal(-0.724247082951467),
    qreal(-0.70710678118654768),
    qreal(-0.68954054473706716),
    qreal(-0.67155895484701866),
    qreal(-0.65317284295377709),
    qreal(-0.63439328416364593),
    qreal(-0.61523159058062737),
    qreal(-0.59569930449243325),
    qreal(-0.57580819141784523),
    qreal(-0.55557023301960218),
    qreal(-0.53499761988709726),
    qreal(-0.51410274419322188),
    qreal(-0.49289819222978426),
    qreal(-0.47139673682599792),
    qreal(-0.44961132965460698),
    qreal(-0.42755509343028253),
    qreal(-0.40524131400499042),
    qreal(-0.38268343236509039),
    qreal(-0.359895036534988),
    qreal(-0.33688985339222),
    qreal(-0.31368174039889152),
    qreal(-0.2902846772544625),
    qreal(-0.26671275747489859),
    qreal(-0.24298017990326418),
    qreal(-0.21910124015687016),
    qreal(-0.19509032201612872),
    qreal(-0.17096188876030177),
    qreal(-0.14673047445536239),
    qreal(-0.12241067519921603),
    qreal(-0.098017140329560506),
    qreal(-0.073564563599667412),
    qreal(-0.049067674327418091),
    qreal(-0.024541228522912448)
};

这段代码看意思应该是近似计算会很快，但是没看懂具体是为什么可以这么算，文档也没有关于这个函数的介绍……求指点一波……

Answer 1

这是典型的查表法.

简单说, 就是把 0 ~ 2 PI 这个连续范围简化为 256 个离散值. 我找了一张示意图(注意, 仅仅是示意):

预先将这些离散点的值算出来, 也就是你所列出表里的那些值.

---

然后, 把 x 分解成两部分, Fix 的部分(si)直接查表得到值, 另外浮点的部分, 就要麻烦点, 需要做插值计算了.

具体步骤可参考: https://en.wikipedia.org/wiki/Lookup_table#Computing_sines

ci 其实是 si + PI / 2, qt_sine_table[ci] 就是 cos(si).

si &= QT_SINE_TABLE_SIZE - 1;
ci &= QT_SINE_TABLE_SIZE - 1;

这两句主要是校正作用, 将 0 ~ 256 范围外的值转为该范围内的, 利用的是 sin 的周期性.

---

这个算法很成熟, 可以参考 SO 上的这个解释: http://stackoverflow.com/questions/3688649/create-sine-lookup-table-in-c.

更准确的方法, 我觉得应该利用泰勒级数展开的方式去求解.