Как генерировать случайные числа без функции rand ()?

Question

Я хочу генерировать (псевдо) случайные числа от 0 до некоторого целого числа.Я не против, если они не слишком случайны.У меня есть доступ к текущему времени дня, но нет функции ранда.Может ли кто-нибудь придумать достаточно надежный способ их создания?Возможно, отбрасывать некоторые биты из времени суток и брать по модулю мое целое число или что-то еще?

Answer 1

Если вам нужен сверхпростой псевдослучайный генератор, вы можете просто использовать регистр сдвига с линейной обратной связью .

В статье в Википедии есть несколько фрагментов кода, которые вы можете посмотреть.на, но в основном код для 16-битного генератора будет выглядеть примерно так (слегка массируется с этой страницы ...)

  unsigned short lfsr = 0xACE1u;
  unsigned bit;

  unsigned rand()
  {
    bit  = ((lfsr >> 0) ^ (lfsr >> 2) ^ (lfsr >> 3) ^ (lfsr >> 5) ) & 1;
    return lfsr =  (lfsr >> 1) | (bit << 15);
  }

Answer 2

Для "не слишком случайных" целых чисел вы можете начать с текущего времени UNIX, а затем использовать рекурсивную формулу r = ((r * 7621) + 1) % 32768;.N-е случайное целое число от 0 (включительно) до M (исключая) будет r % M после n-й итерации.

Это называется линейным конгруэнтным генератором.

рекурсияФормула - это то, что bzip2 использует для выбора центра в своей реализации быстрой сортировки.Я бы не знал о других целях, но он отлично работает именно для этого ...

Answer 3

Посмотрите на реализацию собственного псевдослучайного генератора (что «внутри» rand()), например, Mersenne twister высоко ценится.

Answer 4

import java.io.*;
public class random{
public static class p{

}
static long reg=0;
static long lfsr()
{
    if(reg==0)
    {
        reg=145896027340307l;
    }
    long bit=(reg>>0^reg>>2^reg>>3^reg>>5)&1;
    reg=reg>>1|bit<<62;
    return reg;
}
static long getRand()
{
    String s=String.valueOf(new p());
    //System.out.println(s);
    long n=0;
    lfsr();
    for(int i=0;i<s.length();i++)
    {
        n=n<<8|+s.charAt(i);
    }
    System.out.print(n+" "+System.currentTimeMillis()+" "+reg+" ");
    n=n^System.currentTimeMillis()^reg;
    return n;
}
public static void main(String args[])throws IOException
{
    for(int i=0;i<400;i++)
    {
        System.out.println(getRand());
    }
}

}

Это генератор случайных чисел, в котором гарантируется, что последовательность никогда не повторяется.Я связал время со значением объекта (случайным образом заданным java) с LFSR.

Преимущества:

• Последовательность не повторяется
• Последовательность новаяпри каждом запуске

Недостатки:

• Совместимо только с Java.В C ++ новый объект, который создается, одинаков при каждом запуске.
• Но там тоже время и параметры LFSR привели бы к достаточной случайности
• Это медленнее, чем большинство PRNG, поскольку объект долженсоздается каждый раз, когда нужен номер

Answer 5

Если вы не генерируете свои числа слишком быстро (* 1) и ваш верхний предел достаточно низок (* 2), а ваше "время дня" включает наносекунды, просто используйте эти наносекунды.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int nanorand(void) {
    struct timespec p[1];
    clock_gettime(CLOCK_MONOTONIC, p);
    return p->tv_nsec % 1000;
}

int main(void) {
    int r, x;
    for (;;) {
        r = nanorand();
        do {
            printf("please type %d (< 50 quits): ", r);
            fflush(stdout);
            if (scanf("%d", &x) != 1) exit(EXIT_FAILURE);
        } while (x != r);
        if (r < 50) break;
    }
    puts("");
    return 0;
}

И пробный прогон ...

please type 769 (< 50 quits): 769
please type 185 (< 50 quits): 185
please type 44 (< 50 quits): 44

^{(* 1), если вы используете их в интерактивном режиме, по одному
(* 2), если вы хотите, чтобы числа до 1000}

Answer 6

Самый маленький и простой генератор случайных чисел , который работает с диапазонами , представлен ниже с полностью рабочим примером.

unsigned int MyRand(unsigned int start_range,unsigned int end_range)
  {
    static unsigned int rand = 0xACE1U; /* Any nonzero start state will work. */

    /*check for valid range.*/
    if(start_range == end_range) {
        return start_range;
    }

    /*get the random in end-range.*/
    rand += 0x3AD;
    rand %= end_range;

    /*get the random in start-range.*/
    while(rand < start_range){
        rand = rand + end_range - start_range;
    }

    return rand;
  }

int main(void)
{
    int i;
    for (i = 0; i < 0xFF; i++)
    {
    printf("%u\t",MyRand(10,20));
    }
    return 0;
}

Answer 7

Один из самых простых генераторов случайных чисел, которые не всегда возвращают одно и то же значение:

uint16_t simpleRand(void)
  {
    static uint16_t r = 5531; //dont realy care about start value
    r+=941; //this value must be relative prime to 2^16, so we use all values
    return r;
  }  

Вы можете получить время для установки начального значения, если не хотите, чтобы последовательность всегда начиналась с одного и того же значения.

Answer 8

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
int main()
{
unsigned int x,r,i;
// no of random no you want to generate
scanf("%d",&x);
// put the range of random no 
scanf("%d",&r);
unsigned int *a=(unsigned int*)malloc(sizeof(unsigned int)*x);
for(i=0;i<x;i++)
printf("%d ",(a[i]%r)+1);   
free(a);
getch();
return 0;
}

Answer 9

Вы можете получить "Tiny Mersenne Twister" здесь: http://www.math.sci.hiroshima -u.ac.jp / ~ m-mat / MT / TINYMT / index.html

это чистый c и простой в использовании. Например. просто используя время:

#include "tinymt32.h"
// And if you can't link:
#include "tinymt32.c"

#include <time.h>
#include <stdio.h>

int main(int argc, const char* argv[])
{
    tinymt32_t state;
    uint32_t seed = time(0);

    tinymt32_init(&state, seed);

    for (int i=0; i<10; i++)
            printf("random number %d: %u\n", i, (unsigned int)tinymt32_generate_uint32(&state));
}

Answer 10

Единственный «надежный» (не легко предсказуемый) способ сделать это - написать собственный генератор псевдослучайных чисел и заполнить его текущим временем. Обязательная ссылка на Википедию: http://en.wikipedia.org/wiki/Pseudorandom_number_generator