Geek asks and answers

Naive LFSR, translation of a programming language into mathematics

There is a mathematical problem, it is the problem of generating a sequence of n unique random numbers (a random number is an element from N {0, ..., n} (for example, permutation, but without using memory)

I recently decided to solve this problem, and I got some result (read below, without using formal mathematics, just programming).

and it seems that this problem has already been solved in the past by constructing an LFSR (linear feedback shift register) by Galois or another mathematician. (i acctualy was first discovered from LFSR and then built my β€œown vision” because I could not understand the LFSR article on the wiki and did not want to just copy the source code)

The thing is that I do not understand the words of formal mathematics and would like to study it and compare my solution with the LFSR solution, so the question is:

You can compare what I did with this thing, and somehow transfer it to formal mathematics and vice versa. so that I can understand what I did and what formal mathematicians did (and why do they need it)?

Remember that my language is programming, I only understand memory and its address, memory states, strings of zero and one, etc., and I do not understand primitive polynomials, field theory and other mathematical words.

Thank you very much, if you can help me, I will buy you a beer when I see you.

here is my code below (u can run it in a browser, I am not saying that this is correct, but I believe that the idea should be close, I miss another idea how to solve it.):

<html>
<head>
<script>

//-------------------------------------------------

function getPlacement( num ){ //; knuth permutations
  var places = [];

  for( var i = 0; i < num; ++i )
     places.push( i );

  var last_index = num-1;
  for( var i = num; i > 0; --i ){
    var rnd_index = Random( i );
    places = swap( places, rnd_index, last_index );
    last_index--;
  }

  return places;
}

function readNum( num, placement ){
   var numstr = num.toString(2);            
   numstr = zeroextend( numstr, placement.length ); 
   var numarr = numstr.split('');           

   var ret = [];
   for( var i = 0; i < placement.length; ++i ){
      ret.push( numarr[ placement[i] ] );      
   }
   return ret.join('');
}

function UniqRndSeq( maxLength, output ){

   var placesNeeded = maxLength.toString(2).length;
   var randomPlacement = getPlacement( placesNeeded );

   var initPosition = Random( maxLength );
   var cnt = initPosition;

   var rndn;
   var numret = [];

   do{
     rndn = parseInt( readNum( cnt, randomPlacement ), 2);
     output( rndn );

     if( Containz( numret, rndn ) ) alert(rndn); 
     numret.push(rndn);     

     ++cnt;
     cnt = cnt % maxLength;

   } while( cnt != initPosition );  

}

//-------------------------------------------------
//; helper funs
var outp = [];

function display( num ){
   outp.push( num + "<br>" );
}

function Random( x ){
   return Math.floor(Math.random()*x);
}

function Containz( arr, num ){
   for( var i = 0; i < arr.length; ++i ){
      if( arr[i] == num ) return true;
   }
   return false;
}

function swap( list, a, b ){
   var tmp = list[a];
   list[a] = list[b];
   list[b] = tmp;
   return list;
}

function zeroextend( num_bin_str, length ){
   while( num_bin_str.length != length ){
      num_bin_str = "0" + num_bin_str;
   } 
   return num_bin_str;
}

//-------------------------------------------------

function init(){
   UniqRndSeq( 256, display);
   document.body.innerHTML = outp.join('');
}


</script>
</head>
<body onload="init();">

</body>
</html>
+3
source
1

(LFSR) , .. . , LFSR. , LFSR. LFSR m- n- , n - LFSR. 2 ^ n - 1 ( ). , . ( Galois LFSR 0- , ). , , 2 ^ n - 1, , :

: 1 0, . 1 , 0. , , 1 0 .

:. m + 1 m. m m 1 0.

: *, [* , - ]. , , t , t , , , . , , , .

, LFSR.

+2

More articles:


All Articles