naive LFSR, translate programming language to mathematics
There exist mathematical problem , it is the problem of generating sequence of n unique random numbers (random number is element of N { 0, ..., n }, ( like permutation, but without using memory )
Recentyl i kinda solved that problem, and I did get some result ( read bellow, without use of formal math, just by programming).
and it seems that this problem is allready solved in past by constructing LFSR ( Linear feedback shift register ) by Galois or some other mathematician. ( i acctualy first found out of LFSR and than build my "kind of" soulution, because i couldn't understand LFSR article on wiki, and did't want to just copy paste the source code )
the thing is i don't understand a word of formal mathematics and would like to learn it and compare my solution with that of LFSR, so question is:
can u compare what i did to that thing and somehow translate it to formal math and vice versa. so i can understand what i did and what formal mathematicians did ( and why they needed it )?
remember my language is that of programming i only understand memory and its adressing, memory states, strings of zero and ones, etc. , and i don't understand primitive polynomials, field theory, and other math words.
thank you very much in advance , if u can help me i will buy you a beer when i see you.
here is my code bellow (u can run it in browser, i don't say it is correct but i belive idea should be close, i lack any other 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(){
UniqRnd开发者_JAVA技巧Seq( 256, display);
document.body.innerHTML = outp.join('');
}
</script>
</head>
<body onload="init();">
</body>
</html>
A linear feedback shift register (LFSR) is deterministic, i.e., it doesn't use any kind of random number function. So it it unlikely that your code models a LFSR. If you don't know anything about polynomial rings or finite field theory, it would be difficult to explain the mathematics behind a LFSR. However, a proper LFSR generates what is called m-sequence of n-bit digital words, where n is the number of stages in the LFSR. The length of the sequence is 2^n - 1 words (the zero word is not in the sequence). In general, we are concerned only with one bit position in the words in the sequence. (In a Galois LFSR, this is usually the 0-bit by convention, but all bits actually have the same properties). This single bit, when extracted from each word, forms a 2^n - 1 length bit sequence that has the following well-known mathematical properties related to randomness:
Balance Property: The number of 1's in the sequence approaches the number of 0's as the length of the sequence approaches infinity. The number of 1's in the sequence is actually always one greater than the number of 0's. Note that the sequence length is odd, so that the number 1's and 0's cannot be equal.
Runs Property: The number of m + 1 length runs is one half the number of m length runs. An m length run is an m length bit sequence of all 1's or all 0's.
Correlation Property: The auto-correlation of the sequence approaches zero* as the length of the sequence approaches infinity [* more precisely, a Kronecker delta function]. That is, if one takes the sequence and compares it to itself shifed in time by t number of bits, where t is not equal to the sequence length, the number of bit positions where the comparison is equal is roughly equal to the number of positions where the comparison is unequal. What this means, essentially, is that sequence is devoid of periodic subsequences.
You can compare the results of your code with these properties and draw your own conclusions as to how closely the results approximate an LFSR.
加载中,请稍侯......
精彩评论