<html><head><meta http-equiv="Content-Type" content="text/html; charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class="">Hi Tom,<div class=""><br class=""></div><div class="">I have done a quick and dirty test using the LFSR routines from <a href="https://en.wikipedia.org/wiki/Linear-feedback_shift_register" class="">https://en.wikipedia.org/wiki/Linear-feedback_shift_register</a>. See that page for the lfsr1.. lfsr3 routines. I also added lfsr4() which is basically the lfsr1() routine with a lookup table:</div><div class=""><br class=""></div><div class=""><div class="">uint16_t bittable[256];</div><div class=""><br class=""></div></div><div class=""><div class="">void init_lfsr4(void)</div><div class="">{</div><div class=""> int i;</div><div class=""> uint16_t bit;</div><div class=""><br class=""></div><div class=""> for (i=0; i<256; i++)</div><div class=""> {</div><div class=""> /* taps: 16 14 13 11; feedback polynomial: x^16 + x^14 + x^13 + x^11 + 1 */</div><div class=""> bit = ((i >> 0) ^ (i >> 2) ^ (i >> 3) ^ (i >> 5)) /* & 1u */;</div><div class=""> bittable[i] = bit << 15;</div><div class=""> }</div><div class="">}</div><div class=""><br class=""></div><div class="">unsigned lfsr4(void)</div><div class="">{</div><div class=""> // as lfsr1, but use lookup table</div><div class=""><br class=""></div><div class=""> uint16_t start_state = 0xACE1u; /* Any nonzero start state will work. */</div><div class=""> uint16_t lfsr = start_state;</div><div class=""> uint16_t bit; /* Must be 16-bit to allow bit<<15 later in the code */</div><div class=""> unsigned period = 0;</div><div class=""><br class=""></div><div class=""> do</div><div class=""> { /* taps: 16 14 13 11; feedback polynomial: x^16 + x^14 + x^13 + x^11 + 1 */</div><div class=""> bit = bittable[lfsr & 0xff];</div><div class=""> lfsr = (lfsr >> 1) | bit;</div><div class=""> ++period;</div><div class=""><br class=""></div><div class=""> PORTB = lfsr; // make noise on beeper output PB4</div><div class=""> }</div><div class=""> while (lfsr != start_state);</div><div class=""><br class=""></div><div class=""> return period;</div><div class="">}</div><div class=""><br class=""></div></div><div class="">I compiled this for a 16 MHz Atmega128 using the CrossWorks compiler with max optimisation on and timed each routine:</div><div class=""><br class=""></div><div class=""><div class="">lfsr1 t = 1257 ms, n = 65535, bps = 52136.039062</div><div class="">lfsr2l t = 243 ms, n = 65535, bps = 269691.343750</div><div class="">lfsr2r t = 223 ms, n = 65535, bps = 293878.937500</div><div class="">lfsr3 t = 2768 ms, n = 65535, bps = 23675.939453</div><div class="">lfsr4 t = 325 ms, n = 65535, bps = 201646.156250</div></div><div class=""><br class=""></div><div class="">So lfsr4() using the lookup table gave a 4 times improvement over lfsr1(). But interestingly, the Galois LFSRs lfsr2l and lfsr2r (for left and right shifting versions) were even faster. This makes sense if you look at the source code, it is very simple.</div><div class=""><br class=""></div><div class="">This is a very simple test of course, and many optimisations can be made. Perhaps shifting per byte and not per bit. And not using C… But I just wanted to have a ballpark relative comparison.</div><div class=""><br class=""></div><div class="">Ben</div><div class=""><br class=""></div><div class=""><br class=""><div><br class=""><blockquote type="cite" class=""><div class="">On 19 Feb 2020, at 19:04, Ben Stuyts <<a href="mailto:ben@stuyts.nl" class="">ben@stuyts.nl</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><meta http-equiv="Content-Type" content="text/html; charset=utf-8" class=""><div style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class="">Hi Tom,<div class=""><br class=""></div><div class="">Your link was the first I looked up after watching that video, as your noise pic’s were the first thing that came to my mind. :-)</div><div class=""><br class=""></div><div class="">Ben</div><div class=""><br class=""><div class=""><div class=""><br class=""><blockquote type="cite" class=""><div class="">On 19 Feb 2020, at 15:17, Tom Wiltshire <<a href="mailto:tom@electricdruid.net" class="">tom@electricdruid.net</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><meta http-equiv="Content-Type" content="text/html; charset=utf-8" class=""><div style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class="">I shall be interested to hear how you get on, Ben.<div class=""><br class=""></div><div class="">I *love* a nice look-up table. My first rule is “Don’t do hard sums!”, which means “pretty much anything beyond an addition”!</div><div class=""><br class=""></div><div class=""><div class="">I suspect for the very-lower-level stuff I’ve been doing, the table overhead is worse than the alternative (doing shifts of the LFSR one byte at a time, as described here: <a href="https://electricdruid.net/practical-lfsr-random-number-generators/" class="">https://electricdruid.net/practical-lfsr-random-number-generators/</a>). But it’d great if it wasn’t!</div><div class="">
<div class=""><br class=""><blockquote type="cite" class=""><div class="">On 19 Feb 2020, at 13:43, Ben Stuyts <<a href="mailto:ben@stuyts.nl" class="">ben@stuyts.nl</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div class="">I just watched this interesting talk about using lookup tables (in hardware and software): <a href="https://www.youtube.com/watch?v=LnqqvVp_UZg" class="">https://www.youtube.com/watch?v=LnqqvVp_UZg</a><br class=""><br class="">At the very last end (around 29:11 minutes) he starts talking about LFSR's and maximising their performance using lookup tables instead of the more conventional XOR method. He has a 6 times performance increase. Very cool, I’m going to try this out soon.<br class=""><br class="">Ben<br class=""><br class=""><br class="">_______________________________________________<br class="">Synth-diy mailing list<br class=""><a href="mailto:Synth-diy@synth-diy.org" class="">Synth-diy@synth-diy.org</a><br class=""><a href="http://synth-diy.org/mailman/listinfo/synth-diy" class="">http://synth-diy.org/mailman/listinfo/synth-diy</a><br class=""></div></div></blockquote></div><br class=""></div></div></div></div></blockquote></div><br class=""></div></div></div>_______________________________________________<br class="">Synth-diy mailing list<br class=""><a href="mailto:Synth-diy@synth-diy.org" class="">Synth-diy@synth-diy.org</a><br class="">http://synth-diy.org/mailman/listinfo/synth-diy<br class=""></div></blockquote></div><br class=""></div></body></html>