Случайные числа.

а в чём выражается "неправильность" работы первой?

>>а в чём выражается "неправильность" работы первой?

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

могу привести исходник

http://slil.ru/25135769

вообще говоря, там алгоритм генерации ключей RSA

так вот при использовании первой ф-ции публичная экспонента имеет вид

e = 4ddddddddddddf

а при использовании второй -

e = 1977ff217020f3

что правильно

алгорит один и тот же - вся разница какую функцию использовать

соответственно, неправильность в том, что при использовании второго ключа все работает, а первого - нет. не шифруется

1) вы делаете srand от time, следовательно раскрутка идёт минимум по значениям отличающимся минимум на 1 знак, те на 1 секунду. т.е. если у вас данная ф-я вызывается чаще, чем раз в секунту, то вы будете получать от неё на выходе n одинаковых чисел, где n = кл-ву вызовов данной ф-ии в секунду.

2) во первой ф-ии более грамотную и равномерную кастрацию до 255 можно реализовать так:

int my_random_number = (int)(((float)random() / (float)RAND_MAX) * 255.0)

Первая функция - просто потрясающая.
В течении целой секунды выдаёт одно и то же число :D

...

И рспределение у неё...

#include <stdio.h> 

unsigned int get_rand(void)
{
        int a=rand();
label:
        if (a>255)
        {
                a=a/3;
                goto label;//да-да, извращение
        }
}

int main()
{
    srand();

    int areas[20];
    int i;

    for(i=0; i<20; i++)
        areas[i] = 0;

    for(i=0; i<100000; i++)
        areas[20*get_rand()/256]++;


    for(i=0; i<20; i++)
        printf("%d -> %d\n", i, areas[i]);

    return 0;
}

--->

0 -> 0
1 -> 0
2 -> 0
3 -> 0
4 -> 0
5 -> 0
6 -> 4711
7 -> 12974
8 -> 12916
9 -> 12113
10 -> 13273
11 -> 10035
12 -> 4350
13 -> 4385
14 -> 4008
15 -> 4320
16 -> 4279
17 -> 4262
18 -> 4424
19 -> 3950

А чем не катит rand()%256 ??

Ахтунг! галактеко опасносте!

>>int my_random_number = (int)(((float)random() / (float)RAND_MAX) * 255.0)

действительно прямее. заменил.

но честно говоря, ничего не поменялось.

при использовании первой ф-ции экспонента по-прежнему имеет такой же вид

Кто тебя на С писать учил? циклы делать не умеем? вместо a++ небось тоже a=a+1 пишешь?

А значение а ВОЗВРАЩАТЬ за тебя кто будет? Страуструп?

К слову srand делают 1н раз в начале программы иначе у тебя будет генерироваться одна и та же последовательность и в течении некоторого промежутка времени ты будешь получать одинаковые числа.

А ещё есть такая штука, как деление по модулю. от 0 до 255 числа надо?


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

unsigned int get_rand(void)
{
        return rand() % 256;
}

int main()
{
        srand(time(0));
        printf("%d\n", get_rand());
        return 0;
}
Вот такая штука будет работать.

Господа!

Я один чтоли обратил внимание на отсутствие return в первой функции?

> при использовании первой ф-ции экспонента по-прежнему имеет такой же вид

а если srand'у передавать не секунды а микросекунды, возвращаемые gettimeofday

>>Я один чтоли обратил внимание на отсутствие return в первой функции?

эт пофиг, видимо GCC при отсутствии return возвращает единственную переменную.

я сразу после постинга return написал. но это пофиг - все равно он работал неправильно.

> А чем не катит rand()%256 ??

катит, только такое обрезание последовательности даёт менее случайные числа в данной последовательности.

хммм... а если не делать отдельной функции - все работает.

в смысле - вызывать rand()%255 прямо в основной ф-ции...

> label:	
>	if (a>255)
>	{
>		a=a/3;
>		goto label;//да-да, извращение
> 	}


Какого Проктолога лишилась медицина! Так записать while (a > 255) a /= 3; 

> Спрашивается, какого хрена программа правильно работает при использовании второй функции и неправильно при использовании первой.

"The function rand() is not reentrant or thread-safe,"

>Я один чтоли обратил внимание на отсутствие return в первой функции?

Судя по всему - да. Я, например, такого даже заподозрить не мог, потому и не увидел.

Самый прикол в том, что результат оно, таки, возвращает :D Видимо, результат в eax оказывается к месту.

>катит, только такое обрезание последовательности даёт менее случайные числа в данной последовательности.

Поясни. ИМХО, наоборот, несколько бОльшая рандомизация выходит. Уж, по крайней мере, точно будет много лучше, чем 256*rnd()/MAX_RAND :)

ИМХО, равномерное распределение при урезании диапазона по MOD никак не должно ухудшаться.

в функции не работает? не верю.

во-первых %255 - даст максимальное значение 254, а тебе надо 255 кажется было.

teferi@outlaw:/home/Progs/rand$ cat rand.c
#include <stdio.h>
#include <stdlib.h>

unsigned int get_rand(void)
{
        return rand() % 256;
}

int main()
{
        int i;
        srand(time(0));
        for(i=0;i<10;++i)
                printf("%d\n", get_rand());
        return 0;
}

teferi@outlaw:/home/Progs/rand$ ./a.out
102
23
245
106
54
216
139
213
77
43


Извините, но у меня работает и генерит. Или я что-то в проблеме не понял?

>>Судя по всему - да. Я, например, такого даже заподозрить не мог, потому и не увидел.

ну извиняюсь, извиняюсь. не углядел. все равно же некорректно работает.

так все-таки, как reentrant влияет на некорректную работу?

функция три раза-то и запускается

>>Извините, но у меня работает и генерит. Или я что-то в проблеме не понял?

Исходник по ссылке скомпиль.

там в трех местах вызывается get_rand или get_random

http://slil.ru/25135976

обновленная ссылка

не reentrant функции некорректно работают, если запускаются 2й раз, пока первая ещё не закончилась. Если у вас такая ситуация, в чём я несколько сомневаюсь - то действительно на работу это повлияет.

http://en.wikipedia.org/wiki/Reentrant

>так все-таки, как reentrant влияет на некорректную работу?

Так я не понял, что не работает-то? Если то, что выдаётся одно и то же
число - так про srand уже написали.

Если то, что распределение неравномерное - так там и фишка в том, что
нельзя просто так случайные числа делить. Распределение съезжает при
этом. Я, вон, дал код, по которому можно в первом приближении
равномерность прикинуть. Вот, чуть улучшенный вариант и результат для rand()%256:

#include <stdio.h> 

#define AREAS 20 
#define TIMES 100000 

int main()
{
    srand();

    int areas[AREAS];
    int i;

    for(i=0; i<AREAS; i++)
        areas[i] = 0;

    for(i=0; i<100000; i++)
        areas[AREAS*(rand()%256)/256]++;

    for(i=0; i<AREAS; i++)
        printf("%d -> %.2f\n", i, 1.0*areas[i]*AREAS/TIMES);

    return 0;
}


---->

0 -> 1.01
1 -> 1.01
2 -> 1.01
3 -> 1.01
4 -> 0.96
5 -> 1.01
6 -> 1.00
7 -> 1.02
8 -> 1.02
9 -> 0.94
10 -> 0.99
11 -> 1.04
12 -> 1.04
13 -> 1.01
14 -> 0.94
15 -> 1.02
16 -> 1.00
17 -> 1.02
18 -> 1.02
19 -> 0.95

Слушайте. ну вам сколько раз уже сказали, что srand надо вызывать 1н раз в начале программы. А она у вас вызывается каждый раз при вызове get_rand.

к тому же у меня не компилится, хотя бы по причине отсутствия "gmp.h"

>>Так я не понял, что не работает-то?

по ссылке на slil - генератор RSA-ключей

в нем три раза используется get_rand либо get_random из первого поста

вот если использовать get_rand - получается нерабочий ключ.

если get_random - рабочий.

в остальном все одинаково.

теперь вопрос - почему.

>>Слушайте. ну вам сколько раз уже сказали, что srand надо вызывать 1н раз в начале программы. А она у вас вызывается каждый раз при вызове get_rand.

BINGO!!!

чувак - ты гений. убрал srand из функции в начало программы - все заработало.

>>к тому же у меня не компилится, хотя бы по причине отсутствия "gmp.h"

блин... это GNU MP library

для больших чисел.

Фух. Пожмём друг другу руки. Я рад, что заработало. =)

в младших байта случайности мало...

сразу видно человека не заглядывавшего ни разу в жизни во второй томик дедушки кнута

???

int(drand48()*255);

>в младших байта случайности мало...

Однако больше, чем в старших :)

>сразу видно человека не заглядывавшего ни разу в жизни во второй томик дедушки кнута

Да, когда я ПСЧ изучал, Кнут был в стране просто недоступен :) А потом уже не нужно было. Но тех источников, что были, достаточно для предположения о том, что младшие байты ничуть не хуже старших.

выпий йаду

>>в младших байта случайности мало...

> Однако больше, чем в старших :)

"rand(3) produces a much less random sequence -- in fact, the low dozen bits generated by rand go through a cyclic pattern."

цитата из man 3 random, FreeBSD6

"These interfaces are obsoleted by random(3)" цитата из man 3 rand, FreeBSD6

Ты нифиге не прав.

> >сразу видно человека не заглядывавшего ни разу в жизни во второй томик дедушки кнута

> Да, когда я ПСЧ изучал, Кнут был в стране просто недоступен :) А потом уже не нужно было. Но тех источников, что были, достаточно для предположения о том, что младшие байты ничуть не хуже старших.

Это очень зависит от генератора.

"The versions of rand() and srand() in the Linux C Library use the same random number generator as random() and srandom(), so the lower-order bits should be as random as the higher-order bits. However, on older rand() implementations, and on current implementations on different systems, the lower-order bits are much less random than the higher-order bits. Do not use this function in applications intended to be portable when good randomness is needed."

http://www.linuxmanpages.com/man3/rand.3.php

А OP вообще неправ, генерируя ключи таким образом...

>Это очень зависит от генератора.

Это, безусловно, так. Но когда генератор херовый, то помочь ему уже ничем почти нельзя. Поэтому речь идёт о ХОРОШИХ генераторах, а не о Фортрановском RANDU или ГСЧ на Фокале в БК-0010 :)

>Кнут был в стране просто недоступен :)

враки, у меня на полке стоит кнут 76года издания, так что либо вам за 50 либо вы звезд^Wобманываете нас

PS: Генератор случайных чисел во многом подобен сексу: когда он хорош - это прекрасно, когда он плох, все равно приятно (Джорж Марсалья) (с) цитатка из 2тома кнута :)

>Однако больше, чем в старших :)

4.2

>враки, у меня на полке стоит кнут 76года издания

Заметь, что "недоступен" != "не издавался".

В свободной продаже Кнут появился только в 1990-е гг., но тогда он был по неподъёмным для студента деньгам :) Так что Кнута я смог купить только в самом конце 1990-х гг. А в 1980-е изучал теорию программирования по Лэнгсаму/Огенстайну/Таненбауму... :)