어셈블리 언어의 의사 난수 생성기

StackOverflow https://stackoverflow.com/questions/90184

  •  01-07-2019
  •  | 
  •  

문제

강좌에 할당된 어셈블러 프로그램에 대한 의사 난수 생성기 알고리즘이 필요하며 간단한 알고리즘을 선호합니다.그러나 외부 라이브러리를 사용할 수 없습니다.

어셈블리를 위한 훌륭하고 간단한 의사 난수 생성기 알고리즘은 무엇입니까?

도움이 되었습니까?

해결책

쉬운 방법은 두 개의 큰 상대 소수 a와 b를 선택한 다음 계속해서 임의의 숫자에 a를 곱하고 b를 더하는 것입니다.모듈로 연산자를 사용하여 낮은 비트를 난수로 유지하고 다음 반복을 위해 전체 값을 유지합니다.

이 알고리즘은 다음과 같이 알려져 있습니다. 선형 합동 생성기.

다른 팁

2권 컴퓨터 프로그래밍의 예술 의사 난수 생성에 대한 많은 정보가 있습니다.알고리즘은 어셈블러에서 시연되므로 어셈블러에서 가장 간단한 것이 무엇인지 직접 확인할 수 있습니다.

하지만 외부 라이브러리나 개체 파일에 연결할 수 있다면 그것이 최선의 선택이 될 것입니다.그런 다음 다음과 같이 연결할 수 있습니다. 메르센 트위스터.

대부분의 의사 난수 생성기는 다음과 같습니다. ~ 아니다 암호화에 안전하므로 안전한 난수 생성이 필요한 경우 기본 알고리즘 이상을 살펴봐야 합니다(그리고 아마도 OS별 암호화 API를 활용해야 할 수도 있습니다).

테스트를 위한 간단한 코드, 암호화와 함께 사용하지 마세요

컴퓨터 소프트웨어 테스트, 138페이지에서

32비트 수학을 사용하면 연산이 필요하지 않습니다. MOD 2^32

RNG = (69069*RNG + 69069) MOD 2^32

글쎄요 - 저는 오래된 선형 피드백 시프트 레지스터에 대한 참조를 본 적이 없기 때문에 SSE 내장 기반 C 코드를 게시합니다.단지 완전함을 위해서입니다.나는 SSE 기술을 다시 연마하기 위해 몇 달 전에 그 글을 썼습니다.

#include <emmintrin.h>

static __m128i LFSR;

void InitRandom (int Seed)
{
  LFSR = _mm_cvtsi32_si128 (Seed);
}

int GetRandom (int NumBits)
{
  __m128i seed = LFSR;
  __m128i one  = _mm_cvtsi32_si128(1);
  __m128i mask; 
  int i;

  for (i=0; i<NumBits; i++)
  {

    // generate xor of adjecting bits
    __m128i temp = _mm_xor_si128(seed, _mm_srli_epi64(seed,1));

    // generate xor of feedback bits 5,6 and 62,61
    __m128i NewBit = _mm_xor_si128( _mm_srli_epi64(temp,5),
                                    _mm_srli_epi64(temp,61));

    // Mask out single bit: 
    NewBit = _mm_and_si128 (NewBit, one);

    // Shift & insert new result bit:
    seed = _mm_or_si128 (NewBit, _mm_add_epi64 (seed,seed));
  }

  // Write back seed...
  LFSR = seed;

  // generate mask of NumBit ones.
  mask = _mm_srli_epi64 (_mm_cmpeq_epi8(seed, seed), 64-NumBits);

  // return random number:
  return _mm_cvtsi128_si32 (_mm_and_si128(seed,mask));
}

이 코드를 어셈블러로 변환하는 것은 간단합니다.내장 함수를 실제 SSE 명령어로 바꾸고 그 주위에 루프를 추가하면 됩니다.

Btw - 이 코드가 생성하는 시퀀스는 4.61169E+18 숫자 이후에 반복됩니다.이는 소수 방법과 32비트 산술을 통해 얻을 수 있는 것보다 훨씬 더 많은 것입니다.펼치면 더 빨라집니다.

@jjrv
당신이 설명하는 것은 실제로 선형 합동 생성기입니다.가장 임의의 비트가 가장 높은 비트입니다.0..N-1에서 숫자를 얻으려면 전체 값에 N(32비트 x 32비트를 곱하여 64비트 제공)을 곱하고 상위 32비트를 사용합니다.

어떤 번호도 사용해서는 안 됩니다. ㅏ (하나의 전체 값에서 다음 값으로 진행하기 위한 승수) Knuth(표 1 섹션 3.3.4 TAOCP vol 2 1981)에서 권장되는 숫자는 1812433253, 1566083941, 69069 및 1664525입니다.

홀수를 선택하면 됩니다. 비.(추가).

왜 외부 라이브러리를 사용하지 않습니까 ???그 바퀴는 수백 번이나 발명됐는데 왜 다시 하는 걸까요?

RNG를 직접 구현해야 하는 경우 요청에 따라 숫자를 생성해야 합니까?rand() 함수를 구현하고 있습니까? 아니면 난수 스트림을 생성해야 합니까?메모리 테스트를 위해?

암호화 강도가 뛰어난 RNG가 필요합니까?반복되기까지 얼마나 걸리나요?모든 비트의 균일한 배포를 절대적으로 확실하게 보장해야 합니까?

몇 년 전에 내가 사용했던 간단한 해킹이 있습니다.나는 임베디드 작업을 하고 있었고 전원을 켤 때 RAM을 테스트해야 했고 아주 작고 빠른 코드와 아주 적은 상태를 원했고 다음과 같이 했습니다.

  • 시드에 대한 임의의 4바이트 상수로 시작하십시오.
  • 해당 4바이트의 32비트 CRC를 계산합니다.그러면 다음 4바이트가 제공됩니다.
  • 마치 추가된 것처럼 해당 4바이트를 CRC32 알고리즘에 피드백합니다.해당 8바이트의 CRC32가 다음 값입니다.
  • 원하는 만큼 반복하세요.

이는 코드가 거의 필요하지 않고(crc32 함수에 대한 테이블이 필요하더라도) 상태가 거의 없지만 의사 무작위 출력 스트림은 반복되기 전에 주기 시간이 매우 깁니다.또한 프로세서에 SSE가 필요하지 않습니다.그리고 CRC32 기능이 편리하다고 가정하면 구현하기가 쉽습니다.

masm615를 사용하여 컴파일러:

delay_function macro
    mov cx,0ffffh
.repeat
    push cx
    mov cx,0f00h
    .repeat
        dec  cx
        .until cx==0
    pop cx
    dec cx
    .until cx==0
endm

random_num macro
   mov  cx,64    ;assum we want to get 64 random numbers
   mov  si,0

get_num:    
   push cx
   delay_function    ;since cpu clock is fast,so we use delay_function
   mov  ah,2ch  
   int  21h
   mov  ax,dx     ;get clock 1/100 sec
   div  num       ;assume we want to get a number from 0~num-1
   mov  arry[si],ah   ;save to array you set
   inc  si
   pop  cx
   loop get_num   ;here we finish the get_random number

또한 별도의 비트 사이에 XOR 합계 요소를 사용하여 이동 레지스터를 에뮬레이트할 수 있으며, 이는 의사 무작위 숫자 시퀀스를 제공합니다.

선형 합동(X = AX+C mod M) PRNG는 학생들이 2^31 이상의 중간 AX 결과에 대한 캐리 비트를 처리하고 계수를 계산해야 하기 때문에 어셈블러 과정에 할당하는 것이 좋은 것일 수 있습니다.당신이 학생이라면 어셈블러에서 구현하기가 매우 간단하며 강사가 염두에 둔 것일 수도 있습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top