个人中心
gpt4 book ai didi

algorithm - 朴素的 LFSR，将编程语言翻译成数学

转载 作者：塔克拉玛干 更新时间：2023-11-03 03:19:12 29 4
gpt4 key购买 nike

存在一个数学问题，就是生成n个唯一随机数序列的问题(随机数是N { 0, ..., n }的元素，(类似排列，但不占用内存)

最近我有点解决了这个问题，我确实得到了一些结果(阅读下面的内容，没有使用形式数学，只是通过编程)。

而且似乎这个问题在过去已经通过伽罗瓦或其他数学家构造 LFSR(线性反馈移位寄存器)来解决了。 (我首先发现了 LFSR，而不是构建我的“某种”解决方案，因为我无法理解 wiki 上的 LFSR 文章，并且不想只复制粘贴源代码)

问题是我不懂形式数学，想学习它并将我的解决方案与 LFSR 的解决方案进行比较，所以问题是:

你能比较我对那件事所做的事情，并以某种方式将其转化为形式数学，反之亦然。这样我就可以理解我做了什么以及正式数学家做了什么(以及他们为什么需要它)？

记住我的语言是编程语言，我只理解内存及其寻址、内存状态、0 和 1 的字符串等，我不理解原始多项式、场论和其他数学词汇。

先谢谢你，如果你能帮我，我见到你就请你喝啤酒。

下面是我的代码(你可以在浏览器中运行它，我不认为它是正确的，但我相信想法应该很接近，我不知道如何解决它。):

<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>

最佳答案

线性反馈移位寄存器 (LFSR) 是确定性的，即它不使用任何类型的随机数函数。因此，您的代码不太可能对 LFSR 建模。如果您对多项式环或有限域理论一无所知，就很难解释 LFSR 背后的数学原理。然而，适当的 LFSR 会生成所谓的 n 位数字字的 m 序列，其中 n 是 LFSR 中的级数。序列的长度是 2^n - 1 个单词(零单词不在序列中)。通常，我们只关心序列中单词的一位位置。 (在 Galois LFSR 中，这通常是约定的 0 位，但实际上所有位都具有相同的属性)。从每个单词中提取的这个单个位形成一个 2^n - 1 长度的位序列，该序列具有以下与随机性相关的众所周知的数学属性:

平衡特性:随着序列长度趋近于无穷大，序列中 1 的数量也趋近于 0 的数量。序列中 1 的数量实际上总是比 0 的数量大 1。注意序列长度是奇数，所以1和0的个数不能相等。

运行属性: m + 1 长度运行的数量是 m 长度运行数量的一半。 m长度的游程是m长度的全1或全0的位序列。

相关性:随着序列的长度趋近于无穷大，序列的自相关趋近于零*[*更准确地说，是克罗内克增量函数]。也就是说，如果一个人获取序列并将其与自身进行比较，在时间上移动了 t 个位数，其中 t 不等于序列长度，则位数比较相等的位置数大致等于比较不相等的位置数。从本质上讲，这意味着该序列没有周期性子序列。

您可以将代码的结果与这些属性进行比较，并就结果与 LFSR 的接近程度得出自己的结论。

关于algorithm - 朴素的 LFSR，将编程语言翻译成数学，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5368405/

29 4 0
文章推荐： algorithm - 当一个节点消失时如何组织MST？
文章推荐： Java:从服务器而不是系统时钟获取当前日期和时间
文章推荐： java - java中的局部变量
文章推荐： algorithm - 交叉点 : Strassen's Algorithm
塔克拉玛干
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com