LeafLabs Garden » Topic: Fixed Point Math library
http://forums.leaflabs.com/topic.php?id=266
A place to share, learn, and grow...en-USFri, 22 Jan 2016 00:07:47 +0000http://bbpress.org/?v=1.0.2<![CDATA[Search]]>q
http://forums.leaflabs.com/search.php
iainism on "Fixed Point Math library"
http://forums.leaflabs.com/topic.php?id=266&page=4#post-12168
Fri, 03 Aug 2012 03:11:55 +0000iainism12168@http://forums.leaflabs.com/<p>Hi both - I'm glad this is proving useful to someone.</p>
<p>I will return to the library later this year, but at the moment working on the project for my MSc is swallowing somewhere between most and all of my time when I'm not sleeping!
</p>gbulmer on "Fixed Point Math library"
http://forums.leaflabs.com/topic.php?id=266&page=4#post-11974
Tue, 24 Jul 2012 17:42:11 +0000gbulmer11974@http://forums.leaflabs.com/<p>dapoup - This has been used to discuss the fixed point.<br />
Some folks are trying a newer (than LeafLabs) gcc from <a href="https://launchpad.net/gcc-arm-embedded" rel="nofollow">https://launchpad.net/gcc-arm-embedded</a> which has fixed point support built in.
</p>dapoup on "Fixed Point Math library"
http://forums.leaflabs.com/topic.php?id=266&page=4#post-11967
Tue, 24 Jul 2012 08:32:46 +0000dapoup11967@http://forums.leaflabs.com/<p>Indeed, as a Maple newcomer and audio enthusiast, I'm extremely interested in the outcome of this work. Is this the topic covering technical points about the "fixed point library" that is announced on the documentation of the Maple?
</p>gbulmer on "Fixed Point Math library"
http://forums.leaflabs.com/topic.php?id=266&page=4#post-10441
Mon, 30 Apr 2012 19:39:33 +0000gbulmer10441@http://forums.leaflabs.com/<p>iainism - while this isn't very helpful to you, but following you through this fixed point stuff is very interesting to me. I suspect several people are (or will be) getting some benefit from following along with you. So thanks for all you effort.
</p>iainism on "Fixed Point Math library"
http://forums.leaflabs.com/topic.php?id=266&page=4#post-10438
Mon, 30 Apr 2012 17:45:43 +0000iainism10438@http://forums.leaflabs.com/<p>Hi gbulmer - thanks for catching that - you're absolutely right (again) about the sign bit. I really need to brush up on my bitwise operations!
</p>gbulmer on "Fixed Point Math library"
http://forums.leaflabs.com/topic.php?id=266&page=4#post-10436
Mon, 30 Apr 2012 16:11:48 +0000gbulmer10436@http://forums.leaflabs.com/<p>ianism</p>
<blockquote><p>I've corresponded with Trenki, who has pointed out that the sign conversion in my code above isn't necessary, as the sign bit is preserved by the bitwise shifts</p>
</blockquote>
<p>That is not completely accurate.</p>
<p>The sign <strong>is</strong> preserved for signed integers by <code>>>=</code>. </p>
<p>As I mentioned in my earlier post, sign is <strong>not</strong> preserved for <code><<=</code>.<br />
This shift could move a '1' into the most-significant-bit (msb), which is always an error because that bit represented part of the value, and not the sign of the value. The rewritten code still has the same error. The error won't happen on every value, only the values where a '1' is shifted into the msb.</p>
<p>The fact that division is faster is pretty interesting.
</p>iainism on "Fixed Point Math library"
http://forums.leaflabs.com/topic.php?id=266&page=4#post-10435
Mon, 30 Apr 2012 14:07:06 +0000iainism10435@http://forums.leaflabs.com/<p>Hi gbulmer.</p>
<p>[The last paragraph of this post may be more significant then the remainder]</p>
<p>"It appears to be template <int q> inline fixed_point<q> f_inv(fixed_point<q> a)<br />
but it actually adjust the number so that the return value is a fixed_point<32-q>, and not a fixed_point<q>."</p>
<p>Yes, it is slightly confusing, but this is due to the nature of Trenki's library function:<br />
<code>template <int q> inline fixed_point<q> fixinv(fixed_point<q> a)</code></p>
<p>Which sits behind <code>inv<p></code> (for p=) and takes a <code>fixed_point<q></code> but returns a <code>fixed_point<32-q></code>, which is fine for inv<16>. The purpose of my code is to convert the returned value back to <code>fixed_point<q></code> when q isn't 16.</p>
<p>I've corresponded with Trenki, who has pointed out that the sign conversion in my code above isn't necessary, as the sign bit is preserved by the bitwise shifts (something I'd forgotten in the 10 years or so since I last did bitwise operations!). His suggestion is:</p>
<pre><code>// q is the precision of the input
// output also has precision of q
template<int q>
inline fixed_point<q> f_inv(fixed_point<q> a)
{
const int p = 32 - q;
fixed_point<q> retVal;
retVal.intValue = fixinv<q>(a.intValue);
if (q < p)
retVal.intValue >>= (p - q);
else
retVal.intValue <<= (q - p);
return retVal;
}</code></pre>
<p>I suppose a logical step could be to create a <code>.longValue</code> (similar to <code>.intValue</code>) to allow overflow checking but I'm not sure how much use this would be, since this would still leave an opening for underflow when using a low number of fractional bits and inverting large numbers...</p>
<p>In any case this could all be moot, since in my (very brief) tests, it seems (that for p != 16) the division operator outperforms taking the product of a <code>fixed_point<p></code> and a <code>f_inv<p>(fixed_point<p>)</code>. Which is a trifle vexing!
</p>gbulmer on "Fixed Point Math library"
http://forums.leaflabs.com/topic.php?id=266&page=4#post-10424
Mon, 30 Apr 2012 06:29:52 +0000gbulmer10424@http://forums.leaflabs.com/<p>iainism - IMHO this is confusing, and not explicit.</p>
<p>It appears to be<br />
<code>template <int q> inline fixed_point<q> f_inv(fixed_point<q> a)</code><br />
but it actually adjust the number so that the return value is a <code>fixed_point<32-q></code>, and <strong>not</strong> a <code>fixed_point<q></code>.</p>
<p>IMHO it would be clearer if it were:<br />
<code>template <int p> inline fixed_point<p> f_inv(fixed_point<p> a)</code><br />
and it kept all of the details of how it achieves that internal, and actually return a <code>fixed_point<p></code>.<br />
Or it were<br />
<code>template <int p, int q> inline fixed_point<q> f_inv(fixed_point<p> a)</code></p>
<p>NB: it can silently overflow, and lose the most significant bits.<br />
If it does <code>helper <<= (q-p);</code> the upper bits are discarded which could have the effect of drastically changing the value.</p>
<p>Edit: NB 2: the sign might be incorrect, but this is related to the overflow due to <code>helper <<= (q-p);</code> which could shift a '1' into the top, sign, bit, and change the sign of the value.
</p>iainism on "Fixed Point Math library"
http://forums.leaflabs.com/topic.php?id=266&page=4#post-10410
Sat, 28 Apr 2012 12:32:57 +0000iainism10410@http://forums.leaflabs.com/<p>OK, adding this to fixed_class.h seems to work (all the time now!), and provides the template function <code>f_inv</code> to handle non-16-bit precision cases:</p>
<pre><code>// q is the precision of the input
// output also has precision of q
template <int q>
inline fixed_point<q> f_inv(fixed_point<q> a)
{
int p=32-q;
int helper;
bool sign = false;
fixed_point<32-q> x;
fixed_point<q> retVal;
x.intValue = fixinv<q>(a.intValue);
helper=x.intValue;
if (a < 0) {
sign = true;
a = -a;
}
if (p==q) {
// Do nothing!
} else {
if (q<p) { // Need to right-shift
helper >>= (p-q);
} else { // Need to left-shift
helper <<= (q-p);
}
}
retVal.intValue = helper;
if (sign) {
return -retVal;
} else {
return retVal;
}
}</code></pre>
<p>One can then do a*f_inv<P>(b)
</p>iainism on "Fixed Point Math library"
http://forums.leaflabs.com/topic.php?id=266&page=4#post-10409
Sat, 28 Apr 2012 10:25:49 +0000iainism10409@http://forums.leaflabs.com/<p>[I realise the <code>if</code> I've added could be optimised a little to use a negative shift operation, but I prefer explicit code and I never try to out-optimise my compiler ;-)]
</p>iainism on "Fixed Point Math library"
http://forums.leaflabs.com/topic.php?id=266&page=4#post-10408
Sat, 28 Apr 2012 10:18:04 +0000iainism10408@http://forums.leaflabs.com/<p>Edit: Removed faulty code... Will be back later with some that works, I hope!
</p>iainism on "Fixed Point Math library"
http://forums.leaflabs.com/topic.php?id=266&page=4#post-10406
Sat, 28 Apr 2012 06:00:12 +0000iainism10406@http://forums.leaflabs.com/<p>Argh. On my phone and didn't quite cover the last question!</p>
<p>Using 32-p for q works fine, but this requires some shifting around if one is feeding in the result of a previous <p> operation, as per my final thought above.</p>
<p>Iain
</p>iainism on "Fixed Point Math library"
http://forums.leaflabs.com/topic.php?id=266&page=3#post-10405
Sat, 28 Apr 2012 05:54:11 +0000iainism10405@http://forums.leaflabs.com/<p>Hi gbulmer, yes inv<16> works fine, (there's actually a function written for p=16 as a special case, but any other p fails at compile time, with a 'no match' error).</p>
<p>I can use the division operator to get where I need to be. I was just mindful of the discussion of the additional time taken for division, as discussed above, and so curious if anyone had found a way to use fixinv for p!=16, without using the two conversions, which add a floating point operation each.</p>
<p>I think that one could do a bitwise shift one way or the other on the result of fixinv based off a comparison of p and 32-p by 32-2p bits. I'll test this once I'm back at my machine and feed back.
</p>gbulmer on "Fixed Point Math library"
http://forums.leaflabs.com/topic.php?id=266&page=3#post-10390
Fri, 27 Apr 2012 13:40:12 +0000gbulmer10390@http://forums.leaflabs.com/<p>iainism - have you tried using p=16, and <code>fixed_point<16> inv(..)</code> as an experiment?</p>
<p>The comment in fixed_func.h says:<br />
<pre><code>// q is the precision of the input
// output has 32-q bits of fraction
template <int q>
inline int fixinv(int32_t a) ...</code></pre>
<p>Which seems to agree with what you wrote. </p>
<p>So have you tried instantiating<code>template <int q> inline int fixinv(int32_t a)</code> with <code><32-p></code>?
</p>iainism on "Fixed Point Math library"
http://forums.leaflabs.com/topic.php?id=266&page=3#post-10372
Thu, 26 Apr 2012 16:33:33 +0000iainism10372@http://forums.leaflabs.com/<p>"Use the 'inv' function in Trenki's library to implement division a/b as a*inv(b)"</p>
<p>Has anyone got this to work with anything except P=16? The fixed_class.h file says:</p>
<pre><code>// math functions
// no default implementation
template <int p>
inline fixed_point<p> sin(fixed_point<p> a);
template <int p>
inline fixed_point<p> cos(fixed_point<p> a);
template <int p>
inline fixed_point<p> sqrt(fixed_point<p> a);
template <int p>
inline fixed_point<p> rsqrt(fixed_point<p> a);
template <int p>
inline fixed_point<p> inv(fixed_point<p> a);</code></pre>
<p>I've looked at using</p>
<p><code>fixinv<P>(c)</code></p>
<p>But this returns a result with 32-P fractional bits, and the only way I've found to convert this back to P fractional bits is to do a fix2float<32-P> and then a float2fix<P> which seems quite wasteful (and brings in floating point operations)!
</p>