C에서 Java까지 임의의 생성기 포트?
https://stackoverflow.com/questions/397867
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
George Marsaglia는 매우 빠르고 단순하며 Mersenne Twister보다 훨씬 높은 랜덤 숫자 생성기를 작성했습니다. 설명이있는 코드는 다음과 같습니다.
CMWC4096 코드를 Java로 포트하고 싶었지만 서명되지 않은 여러 데이터 유형을 사용 하므로이 작업을 제대로 수행하는 방법이 확실하지 않습니다. 전체 C 코드는 다음과 같습니다.
/* choose random initial c<809430660 and */
/* 4096 random 32-bit integers for Q[] */
static unsigned long Q[4096],c=362436;
unsigned long CMWC4096(void) {
unsigned long long t, a=18782LL;
static unsigned long i=4095;
unsigned long x,r=0xfffffffe;
i = (i+1) & 4095;
t = a*Q[i] + c;
c = (t>>32);
x = t + c;
if (x < c) {
x++;
c++;
}
return (Q[i] = r - x);
}
누구든지 이것을 Java에 포트 할 수 있습니까? 이용 가능한 숫자 만 서명했을 때 어떻게 작동합니까?
편집하다: 빠른 답변에 감사드립니다! 처음 1 억 개의 숫자의 경우이 Java 코드는 C 코드와 동일한 결과를 생성하는 것으로 보입니다. Java의 java.util.random보다 3 배 빠릅니다.
public class ComplimentaryMultiplyWithCarryRandom {
/**
* Choose 4096 random 32-bit integers
*/
private long[] Q;
/**
* choose random initial c<809430660
*/
private long c = 362436;
private int i;
public ComplimentaryMultiplyWithCarryRandom() {
Random r = new Random(1);
Q = new long[4096];
// TODO initialize with real random 32bit values
for (int i = 0; i < 4096; ++i) {
long v = r.nextInt();
v -= Integer.MIN_VALUE;
Q[i] = v;
}
i = 4095;
}
int next() {
i = (i + 1) & 4095;
long t = 18782 * Q[i] + c;
c = t >>> 32;
long x = (t + c) & 0xffffffffL;
if (x < c) {
++x;
++c;
}
long v = 0xfffffffeL - x;
Q[i] = v;
return (int) v;
}
}
해결책
누구든지 이것을 Java에 포트 할 수 있습니까? 이용 가능한 숫자 만 서명했을 때 어떻게 작동합니까?
스트레스없는! a=18782 그래서 가장 큰 t 서명되지 않은 문제와 서명되지 않은 문제를 일으킬만큼 충분히 크지 않을 수 있습니다. 어디서나 사용하기 전에 q를 32 비트 부호없는 숫자와 같은 값으로 "업그레이드"해야합니다. Q가 an 인 경우 int (32 비트 서명) 그러면 사용하기 전에이 작업을 수행해야합니다. t=a*Q[i]+c 진술, 예를 들어
t=a*(((long)Q[i])&0xffffffffL)+c
이 ((long) q [i]) & 0xfffffffffl) 비즈니스는 Q [i]를 64 비트 #로 홍보하고 높은 32 비트가 0임을 확인합니다. (편집 : 참고 : 여기서 0xfffffffl이 필요합니다. Java는 0xffffffff를 사용하면 잘못된 일을합니다. Q [i]의 높은 비트가 1 인 경우 0xffffffff를 사용하면 "최적화"자체가 "최적화"되는 것처럼 보입니다. )
C ++ 및 Java의 알고리즘을 실행하여 출력을 비교하여이를 확인할 수 있어야합니다.
편집 : 여기에 샷이 있습니다. C ++에서 실행하려고 시도했지만 n = 100000의 Java; 둘 다 일치합니다. 사과 드 Java 관용구를 사용했다면 여전히 Java를 처음 사용합니다.
C ++ :
// marsaglia2003.cpp
#include <stdio.h>
#include <stdlib.h> // for atoi
class m2003
{
enum {c0=362436, sz=4096, mask=4095};
unsigned long Q[sz];
unsigned long c;
short i;
public:
m2003()
{
// a real program would seed this with a good random seed
// i'm just putting in something that makes the output interesting
for (int j = 0; j < sz; ++j)
Q[j] = j + (j << 16);
i = 4095;
c = c0;
}
unsigned long next()
{
unsigned long long t, a=18782LL;
unsigned long x;
unsigned long r=0xfffffffe;
i = (i+1)&mask;
t=a*Q[i]+c;
c=(unsigned long)(t>>32);
x=(unsigned long)t + c;
if (x<c)
{
x++;
c++;
}
return (Q[i]=r-x);
}
};
int main(int argc, char *argv[])
{
m2003 generator;
int n = 100;
if (argc > 1)
n = atoi(argv[1]);
for (int i = 0; i < n; ++i)
{
printf("%08x\n", generator.next());
}
return 0;
}
Java : (컴파일 된 C ++보다 느리지 만 n = 100000과 일치합니다)
// Marsaglia2003.java
import java.util.*;
class Marsaglia2003
{
final static private int sz=4096;
final static private int mask=4095;
final private int[] Q = new int[sz];
private int c=362436;
private int i=sz-1;
public Marsaglia2003()
{
// a real program would seed this with a good random seed
// i'm just putting in something that makes the output interesting
for (int j = 0; j < sz; ++j)
Q[j] = j + (j << 16);
}
public int next()
// note: returns a SIGNED 32-bit number.
// if you want to use as unsigned, cast to a (long),
// then AND it with 0xffffffffL
{
long t, a=18782;
int x;
int r=0xfffffffe;
i = (i+1)&mask;
long Qi = ((long)Q[i]) & 0xffffffffL; // treat as unsigned 32-bit
t=a*Qi+c;
c=(int)(t>>32);
// because "a" is relatively small this result is also small
x=((int)t) + c;
if (x<c && x>=0) // tweak to treat x as unsigned
{
x++;
c++;
}
return (Q[i]=r-x);
}
public static void main(String args[])
{
Marsaglia2003 m2003 = new Marsaglia2003();
int n = 100;
if (args.length > 0)
n = Integer.parseInt(args[0]);
for (int i = 0; i < n; ++i)
{
System.out.printf("%08x\n", m2003.next());
}
}
};
다른 팁
대부분의 경우 Java에서 서명되지 않은 유형을 시뮬레이션하기 위해 더 큰 숫자 유형을 사용할 필요가 없습니다.
추가, 뺄셈, 곱셈, 왼쪽 이동, 논리적 작업, 평등 및 더 작은 숫자 유형으로의 주조를 위해 피연산자가 서명되었는지 또는 서명되지 않았는지 여부에 관계없이 상관없이 결과는 비트 패턴으로 간주됩니다.
올바른 사용으로 이동하려면 >> 서명 된 경우 >>> 서명되지 않은 경우.
더 큰 유형으로 서명 된 캐스팅의 경우 그냥하십시오.
더 작은 유형에서 긴 사용으로 서명되지 않은 캐스팅의 경우, 작은 유형의 유형 마스크가 있습니다. 예를 들어, 짧은 ~ 길이 : s & 0xffffl.
더 작은 유형에서 int 사용 및 유형의 마스크와 함께 서명되지 않은 캐스팅의 경우. 예를 들어, 바이트 ~ int : b & 0xff.
그렇지 않으면 INT 케이스에서 좋아하고 맨 위에 캐스트를 적용하십시오. 예를 들어, 바이트에서 짧게 : (짧은) (b & 0xff).
비교 연산자 <등을 위해 가장 쉬운 것은 더 큰 유형으로 캐스트하고 그곳에서 작업을 수행하는 것입니다. 그러나 다른 옵션도 존재합니다. 예를 들어 적절한 오프셋을 추가 한 후 비교를합니다.
Java에서 RNG를 구현하는 경우 하위 클래스 java.util.random 수업과 보호 된 수업을 과도하게 늘립니다 다음 (int) 메소드 (RNG는 java.util.random의 드롭 인 교체)입니다. 다음 (int) 방법은 무작위로 생성 된 비트와 관련이 있으며, 그 비트가 나타낼 수있는 밸브가 아닙니다. java.util.random의 다른 (공개) 방법은이 비트를 사용하여 다른 유형의 임의 값을 구성합니다.
Java의 서명되지 않은 유형이 부족하여 일반적으로 숫자를 더 큰 가변 유형으로 저장합니다 (따라서 반바지는 ints로 업그레이드됩니다). 여기서 긴 변수를 사용하고 있으므로 BigInteger로 올라 가야합니다. 이는 아마도 알고리즘에서 벗어나는 속도 이득을 망칠 것입니다.
도움이 될 수있는 빠른 참조 시점처럼이 링크를 찾았습니다.
값이 오버플로되지 않으면 서명 된 숫자를 사용할 수 있습니다 ... 예를 들어 Java의 Long은 64 비트 서명 정수입니다. 그러나이 알고리즘의 의도는 64 비트 서명되지 않은 값을 사용하는 것 같습니다. 그렇다면 기본 유형에 운이 좋지 않을 것이라고 생각합니다.
Java 클래스 라이브러리에 제공된 Multiprecision 정수를 사용할 수 있습니다 (Biginteger). 또는 자신의 64 비트 부호없는 유형을 2 개의 Java Long을 포함하는 객체로 구현하여 가장 중요하고 가장 중요한 단어를 나타냅니다 (그러나 클래스에서 기본 산술 연산을 직접 구현해야합니다).
