programing

각 비트에 대해 0 또는 1의 확률로 의사 랜덤 비트를 생성하는 빠른 방법

minecode 2022. 10. 2. 15:02
반응형

각 비트에 대해 0 또는 1의 확률로 의사 랜덤 비트를 생성하는 빠른 방법

일반적으로 난수 발생기는 각 위치에서 0 또는 1을 관측할 확률이 동일한(즉, 50%) 비트의 스트림을 반환합니다.이것을 편견 없는 PRNG라고 부르자.

다음 속성을 가진 의사 랜덤 비트 문자열을 생성해야 합니다. 각 위치에서 1을 볼 확률은 p입니다(즉, 0을 볼 확률은 1-p입니다).파라미터 p는 0과 1 사이의 실수입니다.이 문제에서는 분해능이 0.5%인 경우가 있습니다.즉, 0%, 0.5%, 1%, 1.5%, ..., 99.5%, 100%의 값을 취할 수 있습니다.

p는 확률이지 정확한 분수가 아닙니다.n비트 스트림에서 1로 설정된 실제 비트 수는 이항 분포 B(n, p)를 따라야 합니다.

바이어스 없는 PRNG를 사용하여 각 비트(의사코드)의 값을 생성할 수 있는 간단한 방법이 있습니다.

generate_biased_stream(n, p):
  result = []
  for i in 1 to n:
    if random_uniform(0, 1) < p:
      result.append(1)
    else:
      result.append(0)
  return result

이러한 구현은 각 비트당 한 번씩 랜덤 번호 생성 함수를 호출하기 때문에 편향되지 않은 스트림을 생성하는 것보다 훨씬 느립니다. 반면 편향되지 않은 스트림 생성기는 워드 크기당 한 번 호출합니다(예를 들어 단일 호출로 32 또는 64의 랜덤 비트를 생성할 수 있습니다).

랜덤성을 약간 희생시키더라도 좀 더 빠른 구현을 원합니다.룩업 테이블을 미리 계산하는 방법이 생각납니다.p의 가능한 200개의 값 각각에 대해 느린 알고리즘을 사용하여 C 8비트 값을 계산하여 테이블에 저장합니다.고속 알고리즘은 이들 중 하나를 무작위로 선택하여 8개의 왜곡된 비트를 생성합니다.

필요한 메모리 용량을 확인하기 위한 봉투 계산의 뒷면:C는 256(가능한8비트 값의 수) 이상이어야 합니다.샘플링 효과를 피하기 위해 1024로 합시다.p에 따라 수치가 달라야 할 수도 있지만 단순하게 평균은 1024라고 합시다.p = > 에는 200개의 값이 있기 때문에 메모리 사용량은 200KB 입니다.이는 나쁘지 않으며 L2 캐시(256KB)에 들어갈 수 있습니다.편향을 유발하는 샘플링 효과가 있는지 확인하기 위해 평가해야 합니다. 이 경우 C는 증가해야 합니다.

이 솔루션의 단점은 작업이 많은 PRNG는 몇 개의 산술 명령만으로 한 번에 64비트를 생성할 수 있는 반면, 작업이 많은 PRNG는 한 번에 8비트만 생성할 수 있습니다.

룩업 테이블이 아닌 비트 조작을 기반으로 한 빠른 방법이 있는지 알고 싶습니다.예를 들어, 난수 생성 코드를 직접 수정하여 각 비트에 대한 편견을 도입할 수 있습니다.이는 편견 없는 PRNG와 동일한 성능을 달성할 수 있습니다.

3월 5일 편집

제안해 주셔서 감사합니다.재미있는 아이디어와 제안을 많이 받았습니다.다음은 상위 항목입니다.

  • p의 분해능이 1/200이 아닌 1/256이 되도록 문제 요건을 변경합니다.이를 통해 비트를 보다 효율적으로 사용할 수 있으며 최적화할 수 있는 기회도 많아집니다.내가 바꿀 수 있을 것 같아.
  • 비바이어스 제너레이터의 비트를 효율적으로 소비하려면 산술 부호화를 사용합니다.위의 해상도 변경으로 이 작업이 훨씬 쉬워졌습니다.
  • 소수의 사람들은 PRNG가 매우 빠르다고 제안했습니다.따라서 산술 부호화를 사용하면 실제로 오버헤드가 발생하기 때문에 코드가 느려질 수 있습니다.그 대신 항상 최악의 비트 수를 소비하고 코드를 최적화해야 합니다.아래 벤치마크를 참조하십시오.
  • @rici는 SIMD 사용을 제안했습니다.이는 항상 일정한 수의 비트를 소비하는 경우에만 효과가 있는 좋은 아이디어입니다.

벤치마크(산술 디코딩 없음)

주의:여러분들의 제안대로 해상도를 1/200에서 1/256으로 변경했습니다.

8개의 랜덤 비트를 취하여 1개의 바이어스 비트를 생성하는 순진한 방법의 몇 가지 구현을 작성했습니다.

  • SIMD 미포함
  • SIMD는 @rici가 제안하는 Agner Fog의 벡터 클래스 라이브러리를 사용합니다.
  • 내장 함수를 사용한 SIMD 사용

2개의 편향되지 않은 의사 난수 생성기를 사용합니다.

나는 또한 비교를 위해 편향되지 않은 PRNG의 속도를 측정한다.결과는 다음과 같습니다.


RNG: Ranvec1(Mersenne Twister for Graphics Processors + Multiply with Carry)

Method: Unbiased with 1/1 efficiency, SIMD=vectorclass (incorrect, baseline)
Gbps/s: 16.081 16.125 16.093 [Gb/s]
Number of ones: 536,875,204 536,875,204 536,875,204
Theoretical   : 104,857,600

Method: Biased with 1/8 efficiency
Gbps/s: 0.778 0.783 0.812 [Gb/s]
Number of ones: 104,867,269 104,867,269 104,867,269
Theoretical   : 104,857,600

Method: Biased with 1/8 efficiency, SIMD=vectorclass
Gbps/s: 2.176 2.184 2.145 [Gb/s]
Number of ones: 104,859,067 104,859,067 104,859,067
Theoretical   : 104,857,600

Method: Biased with 1/8 efficiency, SIMD=intrinsics
Gbps/s: 2.129 2.151 2.183 [Gb/s]
Number of ones: 104,859,067 104,859,067 104,859,067
Theoretical   : 104,857,600

SIMD는 스칼라 방식에 비해 성능을 3배 향상시킵니다.예상대로 편향되지 않은 발전기보다 8배 느립니다.

가장 빠른 바이어스 발생기는 2.1Gb/s를 달성합니다.


RNG: xorshift128plus

Method: Unbiased with 1/1 efficiency (incorrect, baseline)
Gbps/s: 18.300 21.486 21.483 [Gb/s]
Number of ones: 536,867,655 536,867,655 536,867,655
Theoretical   : 104,857,600

Method: Unbiased with 1/1 efficiency, SIMD=vectorclass (incorrect, baseline)
Gbps/s: 22.660 22.661 24.662 [Gb/s]
Number of ones: 536,867,655 536,867,655 536,867,655
Theoretical   : 104,857,600

Method: Biased with 1/8 efficiency
Gbps/s: 1.065 1.102 1.078 [Gb/s]
Number of ones: 104,868,930 104,868,930 104,868,930
Theoretical   : 104,857,600

Method: Biased with 1/8 efficiency, SIMD=vectorclass
Gbps/s: 4.972 4.971 4.970 [Gb/s]
Number of ones: 104,869,407 104,869,407 104,869,407
Theoretical   : 104,857,600

Method: Biased with 1/8 efficiency, SIMD=intrinsics
Gbps/s: 4.955 4.971 4.971 [Gb/s]
Number of ones: 104,869,407 104,869,407 104,869,407
Theoretical   : 104,857,600

xorsshift의 경우 SIMD는 스칼라 방식에 비해 성능을 5배 향상시킵니다.이것은 편향되지 않은 발전기보다 4배 느립니다.이것은 xshift의 스칼라 실장입니다.

가장 빠른 바이어스 발생기는 4.9Gb/s를 달성합니다.


RNG: xorshift128plus_avx2

Method: Unbiased with 1/1 efficiency (incorrect, baseline)
Gbps/s: 18.754 21.494 21.878 [Gb/s]
Number of ones: 536,867,655 536,867,655 536,867,655
Theoretical   : 104,857,600

Method: Unbiased with 1/1 efficiency, SIMD=vectorclass (incorrect, baseline)
Gbps/s: 54.126 54.071 54.145 [Gb/s]
Number of ones: 536,874,540 536,880,718 536,891,316
Theoretical   : 104,857,600

Method: Biased with 1/8 efficiency
Gbps/s: 1.093 1.103 1.063 [Gb/s]
Number of ones: 104,868,930 104,868,930 104,868,930
Theoretical   : 104,857,600

Method: Biased with 1/8 efficiency, SIMD=vectorclass
Gbps/s: 19.567 19.578 19.555 [Gb/s]
Number of ones: 104,836,115 104,846,215 104,835,129
Theoretical   : 104,857,600

Method: Biased with 1/8 efficiency, SIMD=intrinsics
Gbps/s: 19.551 19.589 19.557 [Gb/s]
Number of ones: 104,831,396 104,837,429 104,851,100
Theoretical   : 104,857,600

이 실장에서는, AVX2 를 사용해 4 개의 비편향 xorsshift 제너레이터를 병렬로 실행합니다.

가장 빠른 바이어스 발생기는 19.5Gb/s를 달성합니다.

산술 디코딩 벤치마크

간단한 테스트 결과 산술 디코딩 코드는 PRNG가 아닌 병목현상이므로 가장 비싼 PRNG만 벤치마킹하고 있습니다.


RNG: Ranvec1(Mersenne Twister for Graphics Processors + Multiply with Carry)

Method: Arithmetic decoding (floating point)
Gbps/s: 0.068 0.068 0.069 [Gb/s]
Number of ones: 10,235,580 10,235,580 10,235,580
Theoretical   : 10,240,000

Method: Arithmetic decoding (fixed point)
Gbps/s: 0.263 0.263 0.263 [Gb/s]
Number of ones: 10,239,367 10,239,367 10,239,367
Theoretical   : 10,240,000

Method: Unbiased with 1/1 efficiency (incorrect, baseline)
Gbps/s: 12.687 12.686 12.684 [Gb/s]
Number of ones: 536,875,204 536,875,204 536,875,204
Theoretical   : 104,857,600

Method: Unbiased with 1/1 efficiency, SIMD=vectorclass (incorrect, baseline)
Gbps/s: 14.536 14.536 14.536 [Gb/s]
Number of ones: 536,875,204 536,875,204 536,875,204
Theoretical   : 104,857,600

Method: Biased with 1/8 efficiency
Gbps/s: 0.754 0.754 0.754 [Gb/s]
Number of ones: 104,867,269 104,867,269 104,867,269
Theoretical   : 104,857,600

Method: Biased with 1/8 efficiency, SIMD=vectorclass
Gbps/s: 2.094 2.095 2.094 [Gb/s]
Number of ones: 104,859,067 104,859,067 104,859,067
Theoretical   : 104,857,600

Method: Biased with 1/8 efficiency, SIMD=intrinsics
Gbps/s: 2.094 2.094 2.095 [Gb/s]
Number of ones: 104,859,067 104,859,067 104,859,067
Theoretical   : 104,857,600

단순한 고정 소수점 방식은 0.25 Gb/s를 달성하지만, Naigive 스칼라 방식은 3배, Naigive SIMD 방식은 8배 더 빠릅니다.산술 디코딩 방법을 더 최적화하거나 병렬화하는 방법이 있을 수 있지만, 복잡성 때문에 여기서 멈추고 순진한 SIMD 구현을 선택하기로 결정했습니다.

도와주셔서 감사합니다.

한 가지 방법은 기본 비바이어스 제너레이터에서 여러 번 샘플을 추출하여 32비트 또는 64비트 워드를 얻은 후 비트 단위의 부울 계산을 실행하는 것입니다.들면 의 단어, 의 단어, 4개의 단어, 4개의 단어.b1,b2,b3,b4 수 , 으면 안 돼요.

expression | p(비트는 1)-----------------------+-------------b1, b2, b3, b4 | 6.25%b1 및 b2 및 b3 | 12.50%b1 & b2 & ( b3 | b4) | 18.75%b1 및 b2 | 25.00%b1 & ( b2 | ( b3 & b4) | 31.25%b1 & ( b2 | b3) | 37.50%b1 & ( b2 | b3 | b4) | 43.75%b1 | 50.00%

더 나은 해상도를 위해 유사한 구성을 만들 수 있습니다.다소 지루하고 더 많은 제너레이터 호출이 필요하지만 적어도 비트당1개는 필요하지 않습니다., 0xF니블스

원하는 0.5% 분해능의 경우 편향된 단어 하나에 8개의 비편향 단어가 필요하며, 그러면 (0.5^8) = 0.390625%의 분해능을 얻을 수 있습니다.

으로 할 준비가 p256개의 가능한 값을 바탕으로 개별 비트가 서로 독립적인 균일한 값을 생성할 수 있는 PRNG를 가진 경우 벡터화된 비교를 사용하여 단일 난수에서 여러 개의 바이어스 비트를 생성할 수 있습니다.

이는 (1) 난수 품질을 걱정하고 (2) 동일한 편향을 가진 다수의 비트가 필요할 경우에만 수행할 수 있습니다.두 번째 요건은 제안된 솔루션을 비판하는 원래의 질문에 내포되어 있는 것처럼 보입니다.이 솔루션의 단점은 작업이 많은 PRNG라도 한번에 8비트밖에 생성할 수 없는 반면, 편향되지 않은 PRNG는 몇 개의 산술 명령만으로 64비트를 생성할 수 있다는 것입니다.여기서, 그 의미는 단일 콜에서 대량의 바이어스 비트를 생성하는 것이 유용한 것으로 보입니다.

난수 품질은 어려운 주제입니다.측정이 불가능하지는 않을지 모르지만, 따라서 다른 사람들은 "랜덤"의 다른 측면을 강조하거나 평가 절하하는 다른 측정 기준을 제안할 것이다.일반적으로 난수 생성 속도를 낮은 "품질"과 교환할 수 있습니다. 이것이 가치가 있는지 여부는 정확한 용도에 따라 달라집니다.

난수 품질에 대한 가장 간단한 검정은 개별 값의 분포와 발생기의 주기 길이를 포함합니다. C의 rand Posix » Posixrandom일반적으로 함수는 분포 테스트를 통과하지만 사이클 길이가 장기 실행 애플리케이션에 적합하지 않습니다.

은 " " " " " " " " " . glibc " 입니다.random는 몇 개의 사이클만 필요로 하는 반면, 기존의 Linear Congruential Generator(LCG; 선형 합동 생성기)는 곱셈과 덧셈을 필요로 합니다(또는 glibc 구현의 경우 위의 세 개에서 31비트를 생성합니다).이 값이 품질 요구 사항을 충족하기에 충분하다면 특히 치우침 확률이 자주 변경되는 경우에는 최적화를 시도할 필요가 없습니다.

사이클 길이는 예상 샘플 수보다 훨씬 길어야 합니다.이상적으로는 이 값의 제곱보다 길어야 합니다.따라서 사이클 길이가 2인31 Linear-Connegrential Generator(LCG; 선형 일치 생성기)는 기가바이트의 랜덤 데이터가 생성될 것으로 예상되는 경우에는 적절하지 않습니다.사이클 길이가 약 2라고35 주장하는 Gnu 3항 비선형 가산 피드백 생성기조차도 수백만 개의 샘플을 필요로 하는 애플리케이션에는 사용해서는 안 됩니다.

테스트하기가 훨씬 더 어려운 또 다른 품질 문제는 연속된 표본에 대한 독립성과 관련이 있습니다.반복이 시작되면 생성된 난수가 이력 값과 정밀하게 관련되기 때문에 이 메트릭에서는 짧은 사이클 길이가 완전히 실패합니다.Gnu 3항 알고리즘은 사이클이 더 길지만 생성된 i 난수 r은thi 항상 r+ri−31 또는i−3 r+ri−31+1의 두 값 중i−3 하나이기 때문에 명확한 상관관계가 있습니다.이것은 특히 베르누이 실험에서 놀랍거나 적어도 곤혹스러운 결과를 가져올 수 있다.

여기에는 Agner Fog의 유용한 벡터 클래스 라이브러리를 사용한 구현이 있습니다. SSE 내장 함수에서 많은 성가신 세부 사항을 추상화하고 고속 벡터화 난수 생성기(에서 확인됨)를 유용하게 제공합니다.special.zip내 the의 vectorclass.zip아카이브하면 256비트 PRNG에할 수 .Dr. "256" "PRNG" "8" "256" "256" "256" " "256" "256" "Dr."왜 메르센 트위스터조차 품질에 문제가 있다고 생각하는지에 대한 포그의 설명과 그가 제안한 해결책에 대해서는 언급할 자격은 없지만 적어도 베르누이 실험에서 기대했던 결과를 얻을 수 있을 것 같습니다.

#include "vectorclass/vectorclass.h"
#include "vectorclass/ranvec1.h"

class BiasedBits {
  public:
    // Default constructor, seeded with fixed values
    BiasedBits() : BiasedBits(1)  {}
    // Seed with a single seed; other possibilities exist.
    BiasedBits(int seed) : rng(3) { rng.init(seed); }

    // Generate 256 random bits, each with probability `p/256` of being 1.
    Vec8ui random256(unsigned p) {
      if (p >= 256) return Vec8ui{ 0xFFFFFFFF };
      Vec32c output{ 0 };
      Vec32c threshold{ 127 - p };
      for (int i = 0; i < 8; ++i) {
        output += output;
        output -= Vec32c(Vec32c(rng.uniform256()) > threshold);
      }
      return Vec8ui(output);
    }

  private:
    Ranvec1 rng;
};

제 테스트에서는 260밀리초 동안 268435456비트를 생성하고 카운트했습니다.즉, 1나노초당 1비트입니다.테스트 머신은 i5이기 때문에 AVX2와 YMMV는 탑재되어 있지 않습니다.

사용 에서는, 의할 수 있습니다.p8비트 임계값의 계산은 짜증나게 정확하지 않습니다.이 부정확성이 바람직하지 않은 경우 16비트 임계값을 사용하도록 위의 값을 조정할 수 있습니다.단, 2배의 난수를 생성합니다.

또는 10비트 임계값에 기초한 벡터화를 핸드롤링할 수 있습니다.이것은 0.5%의 증분으로 매우 좋은 근사치를 얻을 수 있습니다.이는 벡터화된 임계값 비교의 표준 비트 조작 해크를 사용하여 값의 10번째 비트 감산 및 반복 임계값에서 차용 여부를 체크합니다.를 들어, 를면,와 하면,std::mt19937_6464비트 난수마다 평균 6비트를 얻을 수 있습니다.

비트의 ('비트가 있다'는 입니다.p != 0.5)는 비바이어스 스트림보다 정보가 적기 때문에 이론적으로는 비바이어스 출력 스트림의 단일 비트를 생성하기 위해 비바이어스 입력의 (평균)1비트 미만이 필요합니다.예를 들어, Bernouli 랜덤 변수의 엔트로피는 다음과 같습니다.p = 0.1-0.1 * log2(0.1) - 0.9 * log2(0.9))0.469 「」의 경우,p = 0.1비바이어스 입력 비트당 출력 스트림의 2비트를 조금 넘는 값을 생성할 수 있습니다.

아래에서는 바이어스 비트를 제작하는 두 가지 방법을 제시하겠습니다.양쪽 모두 가능한 한 적은 수의 입력 비트를 필요로 한다는 점에서 최적의 효율을 달성합니다.

방법 1: 산술(디코딩)

실용적인 방법은 이미 알렉시스의 답변에서 설명한 바와 같이 산술(디코딩)을 사용하여 편향되지 않은 입력 스트림을 디코딩하는 것입니다.이 간단한 경우라면 코드화하는 것은 어렵지 않습니다.다음은 최적화되지 않은 의사 코드(cough, Python)입니다.

import random

def random_bits():
    """
    Infinite generator generating a stream of random bits,
    with 0 and 1 having equal probability.
    """
    global bit_count  # keep track of how many bits were produced
    while True:
        bit_count += 1
        yield random.choice([0, 1])

def bernoulli(p):
    """
    Infinite generator generating 1-bits with probability p
    and 0-bits with probability 1 - p.
    """
    bits = random_bits()

    low, high = 0.0, 1.0
    while True:
        if high <= p:
            # Generate 1, rescale to map [0, p) to [0, 1)
            yield 1
            low, high = low / p, high / p
        elif low >= p:
            # Generate 0, rescale to map [p, 1) to [0, 1)
            yield 0
            low, high = (low - p) / (1 - p), (high - p) / (1 - p)
        else:
            # Use the next random bit to halve the current interval.
            mid = 0.5 * (low + high)
            if next(bits):
                low = mid
            else:
                high = mid

다음은 사용 예를 제시하겠습니다.

import itertools
bit_count = 0

# Generate a million deviates.
results = list(itertools.islice(bernoulli(0.1), 10**6))

print("First 50:", ''.join(map(str, results[:50])))
print("Biased bits generated:", len(results))
print("Unbiased bits used:", bit_count)
print("mean:", sum(results) / len(results))

위의 출력 예는 다음과 같습니다.

First 50: 00000000000001000000000110010000001000000100010000
Biased bits generated: 1000000
Unbiased bits used: 469036
mean: 0.100012

약속대로 소스 비편향 스트림에서 50만 비트 미만을 사용하여 출력 바이어스 스트림의 100만 비트를 생성했습니다.

최적화를 위해 이것을 C/C++로 변환할 때는 부동 소수점이 아닌 정수 기반의 고정 소수점 산술로 코드화하는 것이 타당할 수 있습니다.

방법 2: 정수 기반 알고리즘

정수를 직접 사용하도록 산술 디코딩 방법을 변환하는 대신, 여기 더 간단한 방법이 있습니다.더 이상 산술적인 디코딩은 아니지만 완전히 관련이 없는 것은 아니며 위의 부동소수점 버전과 동일한 출력 바이어스 비트/입력 바이어스 없는 비트 비율에 가깝습니다.모든 수량이 부호 없는 32비트 정수에 맞게 구성되므로 C/C++로 변환하기 쉬울 것입니다.이 코드는 다음과 같은 경우에 특화되어 있습니다.p의 정확한 배수입니다.1/200, 이 은 어떤 할 수 있습니다.p상당히 작은 분모를 가진 유리수로 표현될 수 있습니다.

def bernoulli_int(p):
    """
    Infinite generator generating 1-bits with probability p
    and 0-bits with probability 1 - p.

    p should be an integer multiple of 1/200.
    """
    bits = random_bits()
    # Assuming that p has a resolution of 0.05, find p / 0.05.
    p_int = int(round(200*p))

    value, high = 0, 1
    while True:
        if high < 2**31:
            high = 2 * high
            value = 2 * value + next(bits)
        else:
            # Throw out everything beyond the last multiple of 200, to
            # avoid introducing a bias.
            discard = high - high % 200
            split = high // 200 * p_int
            if value >= discard:  # rarer than 1 time in 10 million
                value -= discard
                high -= discard
            elif value >= split:
                yield 0
                value -= split
                high = discard - split
            else:
                yield 1
                high = split

한 while "루프",value [0, high)는 이전에 출력된 모든 비트와는 무관합니다.완벽한 정확성보다 속도를 중시한다면discard 및value >= discard입니다.: 출력하기 것입니다.0 ★★★★★★★★★★★★★★★★★」1정확한 확률로 말이죠그 복잡함을 배제하고, 대신 거의 정확한 확률을 얻을 수 있을 것이다.또, 만약 당신이 의 각오를 한다면p에 equal 1/2561/200따라서 잠재적으로 시간이 많이 걸리는 분할 및 모듈로 연산을 비트 연산으로 대체할 수 있습니다.

하지만, 사용법은 동일합니다.bernoulli_intbernoulli 대해서는 다음과 수 있습니다.p=0.1:

First 50: 00000010000000000100000000000000000000000110000100
Biased bits generated: 1000000
Unbiased bits used: 467997
mean: 0.099675

1을 6,25%(1/16)를 사용하다.4 비트패턴 16 비트패턴이 있어요0000,0001, ..., 1110,1111.

숫자를 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아,1111한 입 베어물고1그 외 모든 것을,0.

다른 가능성에 따라 적절히 조정합니다.

산술 부호화를 사용하여 접근하면 이론적으로 최적의 동작을 얻을 수 있습니다. 즉, 난수 발생기를 진정으로 최소화하고 확률 p를 정확하게 모델링할 수 있습니다.

산술 부호화는 메시지를 번호 범위의 하위 간격으로 나타내는 데이터 압축의 한 형태입니다.이론적으로 최적의 인코딩을 제공하며 각 입력 기호에 대해 소수 비트 수를 사용할 수 있습니다.

아이디어는 다음과 같습니다.확률 p를 가진 1의 랜덤 비트 시퀀스가 있다고 가정합니다.편의상, 대신 사용하겠습니다.q(q = 1-p).산술 부호화는 번호 범위의 각 비트 부분에 할당됩니다.첫 번째 비트에 대해 입력이 0이면 간격 [0, q)을 할당하고 입력이 1이면 간격 [q, 1)을 할당합니다.후속 비트는 현재 범위의 비례 하위 간격을 할당합니다.예를 들어 q = 1/3 입력 1 0 0 은 다음과 같이 부호화된다고 가정합니다.

Initially       [0, 1),             range = 1
After 1         [0.333, 1),         range = 0.6666        
After 0         [0.333, 0.5555),    range = 0.2222   
After 0         [0.333, 0.407407),  range = 0.074074

첫 번째 자리인 1은 범위의 상위 2/3(1-q)를 선택하고, 두 번째 자리인 0은 하위 1/3을 선택하는 방식으로 수행됩니다.첫 번째 스텝과 두 번째 스텝 후에는 간격이 중간점을 가로지릅니다.단, 세 번째 스텝 후에는 중간점보다 완전히 낮기 때문에 첫 번째 압축된 숫자를 출력할 수 있습니다.0가 계속 진행되며,한 ★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★」EOF이치노

이게 당신 문제와 무슨 상관이죠?압축된 출력에는 랜덤 0과 같은 확률의 1이 포함됩니다.따라서 확률 p의 비트를 취득하려면 RNG의 출력이 위와 같은 산술 부호화의 결과라고 가정하고 디코더 프로세스를 적용합니다.즉, 회선 간격을 작은 조각과 작은 조각으로 분할하는 것처럼 비트를 읽습니다.예를 들어, 우리가 읽은 후에01RNG에서는 [0.25, 0.5] 범위에 들어갑니다.충분한 출력이 "디코딩"될 때까지 비트를 계속 읽습니다.네가 압축 해제 흉내를 내고 있기 때문에, 네가 넣는 것보다 더 많은 랜덤한 조각들이 나오게 될 거야.산술 부호화는 이론적으로 최적이기 때문에 랜덤성을 희생하지 않고 RNG 출력을 보다 편향된 비트로 변환하는 방법은 없습니다.진정한 최대값을 얻을 수 있습니다.

몇 줄의 코드로 이 작업을 수행할 수 없다는 것이 단점입니다.또한 제가 가리킬 수 있는 라이브러리가 있는지 모르겠습니다(사용할 수 있는 라이브러리가 있을 것입니다).그래도 꽤 간단해위 문서에서는 범용 인코더 및 디코더 코드를 C로 나타냅니다.이것은 매우 간단하며 임의의 확률로 여러 입력 기호를 지원합니다. 이 경우 확률 모델은 사소한 것이므로 훨씬 더 간단한 구현이 가능합니다(Mark Dickinson의 답변에서 알 수 있음).확장 사용의 경우, 각 비트에 대해 많은 부동 소수점 계산을 수행하지 않는 견고한 구현을 작성하려면 조금 더 많은 작업이 필요합니다.

위키피디아는 또한 기수 변경으로 간주되는 산술 인코딩에 대한 흥미로운 토론이 있는데, 이것은 당신의 과제를 보는 또 다른 방법이다.

의사 난수 생성기는 일반적으로 꽤 빠르죠이 언어가 어떤 언어인지 잘 모르겠습니다(Python, 아마도). 그러나 "result.append"(메모리 할당 포함)는 "random_uniform"(약간의 계산을 수행할 뿐)보다 느릴 수 있습니다.

이 코드의 퍼포먼스를 최적화하려면 , 다음의 순서에 따릅니다.

  1. 문제가 있는 것을 확인합니다.최적화는 약간의 작업이므로 코드를 유지하기가 더 어렵습니다.꼭 필요한 경우가 아니면 하지 마세요.
  2. 프로파일링 하세요.몇 가지 테스트를 실행하여 코드의 어느 부분이 실제로 가장 느린지 확인합니다.이것들은 속도를 높이는 데 필요한 부품입니다.
  3. 변경을 가하여 실제로 더 빠른지 확인합니다.컴파일러는 매우 스마트합니다.많은 경우 클리어 코드는 복잡한 것이 더 빨리 보일 수 있는 더 좋은 코드로 컴파일됩니다.

컴파일된 언어(JIT 컴파일된 언어도 포함)로 작업하는 경우 제어의 모든 전송(함수 호출의 경우, 실행 중 등)에 대해 퍼포먼스가 저하됩니다.네가 할 수 있는 걸 제거해.메모리 할당도 (통상) 꽤 비쌉니다.

통역 언어로 작업하는 경우 모든 베팅이 취소됩니다.가장 간단한 코드가 최선일 가능성이 높습니다.통역사의 오버헤드는 무엇을 하든 작아지므로 가능한 한 그 일을 줄여라.

성능 문제가 어디에 있는지 추측할 수 있을 뿐입니다.

  1. 메모리 할당어레이를 풀사이즈로 미리 할당하고 나중에 엔트리를 입력합니다.이것에 의해, 엔트리를 추가하는 동안 메모리를 재할당할 필요가 없어집니다.
  2. 나뭇가지.당신은 결과나 비슷한 것을 캐스팅함으로써 "만약"을 피할 수 있을 것이다.이것은 컴파일러에 크게 의존합니다.어셈블리(또는 프로파일)를 체크하여 원하는 기능을 하는지 확인합니다.
  3. 숫자 타입난수 생성기가 기본적으로 사용하는 유형을 찾아 해당 유형으로 산술을 수행합니다.예를 들어 생성기가 32비트 부호 없는 정수를 자연스럽게 반환하는 경우 먼저 "p"를 해당 범위로 축척한 다음 비교에 사용합니다.

덧붙여서, 가능한 한 최소의 랜덤 비트를 사용하고 싶다면, 랜덤 스트림을 디코딩하기 위해서 「산술 부호화」를 사용해 주세요.빠르지 않을 거야.

정확한 결과를 얻을 수 있는 한 가지 방법은 먼저 이항 분포에 따라 k비트 블록에 대해 무작위로 1비트 수를 생성한 다음 여기서 설명하는 방법 중 하나를 사용하여 정확히 그 수의 비트를 가진 k비트 워드를 생성하는 것입니다.예를 들어 mic006의 메서드에서는 로그 k비트의 랜덤 번호만 필요하며, 내 메서드에서는 1개만 필요합니다.

p가 0에 가까우면 n번째 비트가 1인 첫 번째 비트일 확률을 계산할 수 있습니다. 그런 다음 0과 1 사이의 난수를 계산하고 그에 따라 n을 선택합니다.예를 들어, p = 0.005(0.5%)이고 난수가 0.638128이면 n = 321을 계산할 수 있으므로 321 0비트와 1비트 세트로 채울 수 있습니다.

p가 1에 가까울 경우 p 대신 1-p를 사용하여 1비트에 0비트를 추가합니다.

p가 1 또는 0에 가깝지 않은 경우 8비트의 모든 256개의 시퀀스를 표로 만들고 누적 확률을 계산한 다음 난수를 가져와 누적 확률 배열에서 이진 검색을 수행하면 8비트를 설정할 수 있습니다.

할 수 하면, 해, 「할 수 .p된 값이 크거나 크거나 작은 것을 할 수 합니다.p.

을 클릭합니다.p:

  1. 「 」부터 합니다.0.
  2. 비트를 붙입니다.를 들어, 덤덤비 ; append; ; append append append;; append 。1★★★★★★★★★★★★★★★★★★★★★★★★★★0.1
  3. 가 (이진표기법)보다 p, , 출력1
  4. 가 입증 한 한 더 같은 p, , 출력0
  5. 그렇지 않은 경우(둘 다 배제할 수 없는 경우) 순서2로 넘어갑니다.

해 볼까요?p에서는 '이진법'입니다.0.1001101...이 중 되는 경우:0.0,0.1000,0.10010이 ,,,,보다 수 panyone; (중)0.11,0.101,0.100111 ...가은 , ...보다 수 .가 생성됩니다.은음p.

이 방법은 대략 두 개의 랜덤비트를 사용하는 것으로 보입니다.산술 부호화(Mark Dickinson의 답변에 나타난 바와 같이)는 고정 비트당 최대 1개의 랜덤 비트를 소비합니다(평균).p 변경 비용; 변경 비용p명확합합니니다

기능

이 구현에서는 "/dev/urandom" 특수 문자 파일의 인터페이스를 통해 랜덤 디바이스 커널 모듈에 단일 호출을 수행하여 주어진 해상도의 모든 값을 나타내는 데 필요한 랜덤 데이터 수를 가져옵니다.0.005는 다음과 같이 나타낼 수 있도록 가능한 최대 분해능은 1/256^2입니다.

328/256^2,

예:

해상도: 256*256

x: 328

에러 0.000004883이 표시됩니다.

그 구조

됩니다.bits_per_byte하는 데 . 해상도를 나타냅니다.@resolution 디바이스("/dev/")에 단일 콜을 발신합니다("/dev/urandom」)에 단일 콜을 합니다.URANDOM_DEVICE에서 "/을 통해 추가 이 노이즈는 비트 수를 하고 어레이를 수 있습니다.그렇지 않으면 디바이스 드라이버에서 "/dev/display"에 대한 호출을 통해 추가 노이즈를 사용합니다.이 노이즈는 비트 단위의 엔트로피가 부족할 경우 차단되어 균등하게 분산된 바이트 수를 취득하여 어레이를 채웁니다.rnd_bytes츠요시의 각 에서 각 을 "bytes_per_bytes"에 의해 단일 합니다.x/resolution. , 이이음음, 음음음음음 of of of of of of of of of of of of of of of of of of of of of of of of of of의 에 x/resolution【0, x/resolution】그먼트로 선택한 후 성공을 기록하고 1을 결과 어레이에 삽입합니다.

랜덤 디바이스에서 읽기:

/* if defined use /dev/urandom (will not block),
 * if not defined use /dev/random (may block)*/
#define URANDOM_DEVICE 1

/*
 * @brief   Read @outlen bytes from random device
 *          to array @out.
 */
int
get_random_samples(char *out, size_t outlen)
{
    ssize_t res;
#ifdef URANDOM_DEVICE
    int fd = open("/dev/urandom", O_RDONLY);
    if (fd == -1) return -1;
    res = read(fd, out, outlen);
    if (res < 0) {
        close(fd);
        return -2;
    }
#else
    size_t read_n;
    int fd = open("/dev/random", O_RDONLY);
    if (fd == -1) return -1;
    read_n = 0;
    while (read_n < outlen) {
       res = read(fd, out + read_n, outlen - read_n);
       if (res < 0) {
           close(fd);
           return -3;
       }
       read_n += res;
    }
#endif /* URANDOM_DEVICE */
    close(fd);
    return 0;
}

베르누이 샘플의 벡터 입력:

/*
 * @brief   Draw vector of Bernoulli samples.
 * @details @x and @resolution determines probability
 *          of success in Bernoulli distribution
 *          and accuracy of results: p = x/resolution.
 * @param   resolution: number of segments per sample of output array 
 *          as power of 2: max resolution supported is 2^24=16777216
 * @param   x: determines used probability, x = [0, resolution - 1]
 * @param   n: number of samples in result vector
 */
int
get_bernoulli_samples(char *out, uint32_t n, uint32_t resolution, uint32_t x)
{
    int res;
    size_t i, j;
    uint32_t bytes_per_byte, word;
    unsigned char *rnd_bytes;
    uint32_t uniform_byte;
    uint8_t bits_per_byte;

    if (out == NULL || n == 0 || resolution == 0 || x > (resolution - 1))
        return -1;

    bits_per_byte = log_int(resolution);
    bytes_per_byte = bits_per_byte / BITS_PER_BYTE + 
                        (bits_per_byte % BITS_PER_BYTE ? 1 : 0);
    rnd_bytes = malloc(n * bytes_per_byte);
    if (rnd_bytes == NULL)
        return -2;
    res = get_random_samples(rnd_bytes, n * bytes_per_byte);
    if (res < 0)
    {
        free(rnd_bytes);
        return -3;
    }

    i = 0;
    while (i < n)
    {
        /* get Bernoulli sample */
        /* read byte */
        j = 0;
        word = 0;
        while (j < bytes_per_byte)
        {
            word |= (rnd_bytes[i * bytes_per_byte + j] << (BITS_PER_BYTE * j));
            ++j;
        }
        uniform_byte = word & ((1u << bits_per_byte) - 1);
        /* decision */
        if (uniform_byte < x)
            out[i] = 1;
        else
            out[i] = 0;
        ++i;
    }

    free(rnd_bytes);    
    return 0;
}

사용방법:

int
main(void)
{
    int res;
    char c[256];

    res = get_bernoulli_samples(c, sizeof(c), 256*256, 328); /* 328/(256^2) = 0.0050 */
    if (res < 0) return -1;

    return 0;
}

완전한 코드, 결과

비록 이 질문이 5년 전이지만, 저는 뭔가 더 가치 있는 것이 있다고 생각합니다.SIMD와 산술 디코딩은 의심할 여지 없이 훌륭한 기술이지만 @mindriot이 제안하는 비트 부울 산술은 매우 간단하고 이해하기 쉽다는 것을 무시하기 어렵다.

그러나 이 솔루션을 효율적이고 신속하게 구현할 수 있는 방법은 명확하지 않습니다.256비트(0.00390625)의 분해능에서는 256개의 케이스로 스위치스테이트먼트를 쓴 후 케이스별로 필요한 부울식을 수동으로 결정할 수 있습니다.프로그래밍에 시간이 걸리지만 C/C++에서 매우 빠른 점프 테이블로 컴파일됩니다.

단, 2^16비트의 해상도나 2^64의 해상도를 원하시면 어떻게 하시겠습니까?후자의 해상도는 5.4210109E-20으로, 우리 대부분이 필요로 하는 것보다 정확합니다.이 작업은 수작업으로는 절대 불가능하지만, 실제로는 작은 가상 머신을 구성하여 30줄의 C 코드만으로 신속하게 수행할 수 있습니다.

256달러입니다.probability = resolution/256를 들어, 「」가 되었을 경우, 「」가 됩니다resolution = 64 , , , 「 」probability = 0.25알고 보니 분자(해상도)는 실제로 필요한 부울 연산을 바이너리 표현으로 암묵적으로 부호화합니다.

를 들어, 어떤 에 의해 「」, 「」가 되는가.probability = 0.69140625 = 177/256로는 177입니다10110001 .락 렛츠.AND = 0 ★★★★★★★★★★★★★★★★★」OR = 10이 아닌 첫 번째 최하위 비트부터 시작하여 최상위 비트를 향해 읽습니다.0/1을 AND/OR에 매핑합니다.따라서 b1에서 시작하여 오른쪽에서 왼쪽으로 읽으면 부울식을 생성합니다.(((((((b1 and b2) and b3) and b4) or b5) or b6) and b7) or b8)컴퓨터 생성 진실표를 통해 177건의 사례가 사실임을 확인할 수 있습니다.의 예를, '하다' 입니다.probability = 0.4375 = 112/256.01110000. 이 아닌첫 LSB(0) 이후 011의 설명입니다.((b1 | b2) | b3) & b4).

한 AND ★★★★★★★★★★★★★★★★★」OR이 해상도는 필요한 정확한 부울식을 인코딩하므로 해상도를 비트 코드로 해석하는 가상 머신을 프로그래밍할 수 있습니다. AND ★★★★★★★★★★★★★★★★★」OR편향되지 않은 난수 발생기의 출력에 즉시 작용하는 연산 코드입니다.샘플 C 코드는 다음과 같습니다.

uint64_t rng_bias (uint64_t *state, const uint8_t resolution)
{
    if (state == NULL) return 0;
    
    //registers
    uint64_t R0 = 0;
    uint8_t  PC = __builtin_ctz(resolution|0x80);
    
    //opcodes
    enum
    {
        OP_ANDI = 0,
        OP_ORI  = 1,
    };
    
    //execute instructions in sequence from LSB -> MSB
    while (PC != (uint8_t) 0x8)
    {
        switch((resolution >> PC++) & (uint8_t) 0x1)
        {
            case OP_ANDI:
                R0 &= rng_generator(state);
                break;
                
            case OP_ORI:
                R0 |= rng_generator(state);
                break;
        }
    }
    
    return R0;
}

가상 시스템은 2개의 레지스터와 2개의 opcode에 지나지 않습니다.GCC의 함수 GCC를 .ctz 제로 의 LSB를쉽게 수 합니다. - theた i i 。ctz인수가 0x80인 것은 패스워드가 정의되어 있지 않기 때문입니다.다른 컴파일러도 같은 기능을 가지고 있을 것입니다.여기서 설명한 예시와 달리 VM은 비트 코드를 0이 아닌 첫 번째 LSB부터 해석합니다.이는 PRNG에 적어도1개의 콜을 발신하여 베이스를 생성해야 하기 때문입니다.p=0.5 ★★★★★★★★★★★★★★★★★」p=0.0[cases . ]를 합니다.

state 및 " " "rng_generator()콜은 랜덤 번호 생성기와의 인터페이스에 사용됩니다.Marsaglia Xorsshift64 입니다.

uint64_t rng_generator(uint64_t *state)
{
    uint64_t x = *state;
    
    x ^= x << 13;
    x ^= x >> 7;
    x ^= x << 17;
    
    return *state = x;
}

.uint64_t state함수를 .

2^64를 사용하다ctzll ★★★★★unsigned long long, "", "uint8_tuint64_t8이 while loop 8은 64로 변경합니다.으로 5. 할 수 .PRNG는 64개입니다.이것에 의해, 5.4210109E-20 의 해결에 액세스 할 수 있습니다.

여기서 중요한 것은 우리가 실질적으로 무료로 비트코드를 얻을 수 있다는 것이다.렉싱, 해석 또는 기타 일반적인 VM 인터프리터 태스크는 없습니다.사용자가 모르는 사이에 해상도를 통해 제공합니다.그들에 관한 한, 그것은 확률의 분자일단순히 확률의 분자일 뿐이다.구현자들은 VM이 해석할 수 있는 비트코드 문자열에 불과하다고 생각합니다.

비트코드가 작동하는 이유를 설명하는 것은 완전히 다른, 훨씬 더 긴 에세이를 필요로 한다.확률론에서 문제는 주어진 확률의 발생 사건(모든 표본 점 집합)을 결정하는 것입니다.밀도 함수에서 난수를 생성하는 일반적인 역 누적분포함수 문제와 다르지 않습니다.컴퓨터 과학의 관점에서 256비트 해상도의 경우, 우리는 각 노드가 확률을 나타내는 깊이 8의 이진 트리를 횡단하고 있습니다.는 " " 입니다.p=0.5 " "를 나타냅니다.AND은 「」, 「」를 나타냅니다.OR트래버설과 노드의 깊이는 앞에서 설명한 LSB->MSB 비트 부호화에 직접 매핑됩니다.

언급URL : https://stackoverflow.com/questions/35795110/fast-way-to-generate-pseudo-random-bits-with-a-given-probability-of-0-or-1-for-e

반응형
저작자표시

'programing' 카테고리의 다른 글

JavaScript에서 REST 웹 서비스 API를 호출하려면 어떻게 해야 합니까?  (0) 2022.10.02
SQLite3를 MySQL로 빠르게 마이그레이션하는 방법  (0) 2022.10.02
Firebase 및 Firebase를 갖춘 Nuxt 미들웨어UI: 오류: 네비게이션 가드를 통해 "/anything"에서 "/login"으로 이동할 때 방향 수정됨  (0) 2022.10.02
Java 7 컴파일 코드를 Java 8로 업그레이드하면 어떤 이점이 있습니까?  (0) 2022.10.02
C에서 함수 포인터의 배열을 정의하는 방법  (0) 2022.10.02

'programing'의 다른글

  • 현재글각 비트에 대해 0 또는 1의 확률로 의사 랜덤 비트를 생성하는 빠른 방법

관련글

댓글

티스토리툴바