Databases
StackOverflow2013
Postsdbo
POFibonacci LFSRs calculation optimisation
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POFibonacci LFSRs calculation optimisation
    text
    copied!<p><a href="http://en.wikipedia.org/wiki/Linear_feedback_shift_register" rel="nofollow">Fibonacci LFSR</a> is described on wiki, it's pretty simple. <br />I'd like to calucate the period of some Fibonacci's LFSR and use generated sequence for ciphering later. <br /> Let's take and example from wiki:</p> <blockquote> <p>x<sup>16</sup> + x<sup>14</sup> + x<sup>13</sup> + x<sup>11</sup> + 1;</p> </blockquote> <pre><code>//code from wiki: include &lt;stdint.h&gt; uint16_t lfsr = 0xACE1u; unsigned bit; unsigned period = 0; do { /* taps: 16 14 13 11; characteristic polynomial: x^16 + x^14 + x^13 + x^11 + 1 */ bit = ((lfsr &gt;&gt; 0) ^ (lfsr &gt;&gt; 2) ^ (lfsr &gt;&gt; 3) ^ (lfsr &gt;&gt; 5) ) &amp; 1; lfsr = (lfsr &gt;&gt; 1) | (bit &lt;&lt; 15); ++period; } while(lfsr != 0xACE1u); </code></pre> <p>My weakly try so far in php:</p> <pre><code>function getPeriod(){ $polynoms = array(16, 14, 13, 11); $input = $polynoms[0] - 1; $n = sizeof($polynoms); for ($i = 1; $i &lt; $n; $i++) $polynoms[$i] = $polynoms[0] - $polynoms[$i]; $polynoms[0] = 0; //reversed polynoms == array(0, 2, 3, 5); $lfsr = 0x1; //begining state $period = 0; //gmp -- php library for long numbers; $lfsr = gmp_init($lfsr, 16); do { $bit = $lfsr; //bit = x^16 &gt;&gt; 0; for($i = 1; $i &lt; $n; $i++) { //bit ^= lfsr &gt;&gt; 2 ^ lfst &gt;&gt; 3 ^ lfst &gt;&gt; 5; $bit = gmp_xor($bit, ( gmp_div_q($lfsr, gmp_pow(2, $polynoms[$i])) )); } //bit &amp;= 1; $bit = gmp_and($bit, 1); //lfsr = $lfsr &gt;&gt; 1 | $lsfr &lt;&lt; (16 - 1); $lfsr = gmp_or( (gmp_div_q($lfsr, 2)), (gmp_mul($bit, gmp_pow(2, $input))) ); $period++; } while (gmp_cmp($lfsr, 0x1) != 0); echo '&lt;br /&gt;period = '.$period; //period == 65535 == 2^16 - 1; -- and that's correct; // I hope, at least; return $period; } </code></pre> <p><br/> <b>Problem:</b> <br />If i try to modulate work of i.e.</p> <blockquote> <p>x<sup>321</sup> + x<sup>14</sup> + x<sup>13</sup> + x<sup>11</sup> + 1;</p> </blockquote> <p>i got an error:"<strong>Fatal error: Maximum execution time of 30 seconds exceeded in /var/www/Dx02/test.php</strong>"; <br /> <br /> Can i somehow optimize (accelerate :) ) the calculation? <br /> <br />Any help is appreciated. Thank you and excuse me for my English.</p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload