Порт генератора случайных чисел от C до Java?
Джордж Марсалья написал отличный генератор случайных чисел, который очень быстрый, простой и имеет гораздо больший период, чем тварь Мерсенна. Вот код с описанием:
хороший генератор случайных чисел C
Я хотел перенести код 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? Как это работает, если у вас есть только подписанные номера?
РЕДАКТИРОВАТЬ: Спасибо всем за быстрые ответы! Похоже, что для первых 100 миллионов чисел этот код Java дает тот же результат, что и код Си. Это в 3 раза быстрее, чем Java java.util.Random.
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;
}
}
7 ответов
Кто-нибудь может перенести это на Java? Как это работает, если у вас есть только подписанные номера?
Нет стресса! a=18782 так самый большой t может быть недостаточно велико, чтобы вызвать проблемы со знаком и без знака. Вы должны были бы "обновить" результат использования Q до значения, равного 32-битному числу без знака, прежде чем использовать его где-либо. например, если Q является int (32-разрядная подпись), то вам придется сделать это, прежде чем использовать его в t=a*Q[i]+c утверждение, например
t=a*(((long)Q[i])&0xffffffffL)+c
где этот бизнес (((long)Q[i])&0xffffffffL) продвигает Q [i] до 64-битного # и гарантирует, что его старшие 32 бита равны 0. (edit: ПРИМЕЧАНИЕ: вам нужен 0xffffffffL здесь. Java делает неправильную вещь, если вы используете 0xffffffff, похоже, что он "оптимизирует" себя до неправильного ответа и вы получите отрицательное число, если старший бит Q [i] равен 1.)
Вы должны убедиться в этом, запустив алгоритмы на C++ и Java для сравнения результатов.
редактировать: вот выстрел в это. Я попытался запустить его в C++ и Java для N=100000; они оба совпадают. Извиняюсь, если я использовал плохие идиомы 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.
Для сложения, вычитания, умножения, сдвига влево, логических операций, равенства и приведения к меньшему числовому типу не имеет значения, являются ли операнды знаковыми или беззнаковыми, результат будет одинаковым независимо, если рассматривать его как битовый шаблон.
Для перехода вправо используйте >> для подписи, >>> для неподписания.
Для подписанного приведения к большему типу просто сделайте это.
Для литья без знака от меньшего типа к длинному использованию и с маской типа long для меньшего типа. Например, от короткого до длинного: s & 0xffffL.
Для приведения типов без знака к типу int используйте & с маской типа int. Например, байт до int: b & 0xff.
В противном случае сделайте как в случае int и примените приведение сверху. Например, от короткого байта: (короткий) (b & 0xff).
Для операторов сравнения<и т. Д. И деления проще всего привести к большему типу и выполнить операцию там. Но существуют и другие варианты, например, делать сравнения после добавления соответствующего смещения.
Если вы реализуете ГСЧ в Java, то лучше выделить подкласс класса java.util.Random и переопределить защищенный метод next(int) (тогда ваш ГСБ станет заменой java.util.Random.). Следующий (int) метод связан со случайно генерируемыми битами, а не с теми значениями, которые эти биты могут представлять. Другие (публичные) методы java.util.Random используют эти биты для создания случайных значений различных типов.
Чтобы обойти отсутствие в Java беззнаковых типов, вы обычно храните числа в переменном типе большего размера (поэтому шорты обновляются до целых, от длинных до целых). Поскольку здесь вы используете длинные переменные, вам придется перейти к BigInteger, который, вероятно, разрушит любой прирост скорости, который вы получаете из алгоритма.
Так же, как краткий справочник, который может (или не может) помочь вам, я нашел эту ссылку:
Примечание. В вашем коде C я сделал вывод, чтоlongимеет ширину 32 бита иlong longимеет ширину 64 бита.
Вот мой способ переноса этого кода на Java с минимальным количеством изменений:
/* choose random initial 0<=c<809430660 and */
/* 4096 random 32-bit integers for Q[] */
int[] Q = new int[4096];
int c = 362436;
int i = 4095;
int CMWC4096() {
long a = 18782;
int r = 0xfffffffe;
i = (i + 1) & 4095;
long t = a * Q[i] + c;
c = (int)(t >>> 32);
int x = (int)(t + c);
if (0 <= x && x < c) {
x++;
c++;
}
return (Q[i] = r - x);
}
Вы можете использовать числа со знаком при условии, что значения не переполняются... например, long в java - это 64-битное целое число со знаком. Однако, похоже, что в этом алгоритме используется 64-разрядное значение без знака, и в этом случае, я думаю, вам не повезет с основными типами.
Вы можете использовать целочисленные целые числа, представленные в библиотеках классов Java ( BigInteger). Или вы можете реализовать свой собственный 64-битный беззнаковый тип в виде объекта, содержащего два длинных java для представления наименее значимых и наиболее значимых слов (но вам придется самостоятельно выполнять основные арифметические операции в классе).