Форум 'Проект Entropy' на RSDN.RU

[Sources] Получение истинно случайных последовательностей

Sun, 26 Jun 2011 07:39:38 GMT

Добрый день!
Случайно наткнулся на ветку
У меня была тема диплома, связанная с получением истинно случайных последовательностей (использовалось 3 различных метода) из псевдослучайной.
Плюс некоторые исследования. Если необходимо, могу найти (исходники на c#)

Как проверить случайность чисел?

Mon, 19 Nov 2007 13:49:39 GMT

У меня есть генератор случайных чисел(недавно написал.) Думаю(надеюсь), что он может выдавать совершенно разные значения.
Как его проверить? Генерирует по 128бит. Скорость должна быть офигенной(не проверял), ну не меньше 10 000 ключей в секунду. Если кому интересно могу нагенерировать и прислать.

Все украдено до нас

Sat, 01 Sep 2007 23:54:18 GMT

http://random.irb.hr/index.php
Типа самый истинный изо всех истинных генераторов случайностей.

А что это за проект?

Sun, 15 Jul 2007 13:21:34 GMT

А что это за проект? что ни одного сообщения

... << RSDN@Home 1.1.4 stable SR1 rev. 568>>

Источник энтропии

Sun, 01 Jul 2007 17:06:52 GMT

Можно попробовать использовать в качестве источника энтропии генератор белого шума.Есть и готовые схемы и готовые генераторы.
Главное достоинство белого шума — случайная частота сигнала в некотором диапазоне частот. Можно выделить спектр белого шума с помощью быстрого преобразования фурье (для этого можно использовать любой микроконтроллер) и передавать отсчёты в компьютер по COM или USB, а лучше предусмотреть и то и другое. На высокие частоты не лезть, использовать диапазон звуковых частот (сильно уменьшит затраты на микроконтроллер).
К основным недостаткам надо отнести то, что на входе компьютера имеем УПОРЯДОЧЕННУЮ случайную последовательность.

Самое лучшее решение - генерирование de Bruijn sequences!

Wed, 27 Jun 2007 03:38:37 GMT

Самое лучшее решение — генерирование длинных нелинейных de Bruijn последовательностей.
Случайности там будет много.

А чем этот проект лучше http://www.random.org/?

Thu, 22 Feb 2007 10:28:03 GMT

http://www.random.org/

Join

Fri, 10 Nov 2006 15:02:30 GMT

Хотелось бы поучавствовать в проэкте. Что для этого нужно?
Пару слов о себе и интересах — закончил математический, кафедра теории вероятности и мат. статистики, так что интерес к поставленной задаче большой, есть моного идей, ну и наработки тоже имеются...

Энтропия шума зв.карты, радиошума=?

Sat, 06 Aug 2005 20:01:40 GMT

Всем привет! Вопрос, в первую очередь, к участникам проекта: проверил ли кто-нибудь сабж?

Ревизия 6

Sun, 31 Jul 2005 09:57:41 GMT

Снапшот: http://www.rsdn.ru/File/1951/Library.zip

Отдельно от всего того, что было ранее. Добавлена директория Library, содержащая функции для работы с нормальным распределением, случайными числами (разных видов), а также plain-vanila derivatives (нормального перевода на русский не знаю).

Содержание

Maths

Entropy.Maths.Statistics — пока что только один класс NormalDistibution — плотность, функция распределения, обратная функция распределения (думаю, что нашёл лучшие алгоритмы, имеющиеся в инете). Есть идея добавить другие распределения...

Entropy.Maths.RandomNumbers:
Box-Muller — алгоритм для получения номально распределённых случайных чисел. Не шибко эффективен, но прост для понимания.
Halton — самый простой алгоритм из семейства квази-случайных генераторов чисел. TODO: заменить его на алгоритм Sobol (Соболь).
Moro — алгоритм для получения номально распределённых случайных чисел из квази-случайных. Алгоритм позволяет сохранить все приятные свойства квази-случайных чисел.
Pseudo — класс-обёртка над System.Random.
Ziggurat — алгоритм для получения номально распределённых случайных чисел. Самый эффективный алгоритм, который я смог найти.

Finance

Система состоит из следующих частей:
Trade — описание финансовых инструментов (даны примеры европейских опций).
Model — описание моделей, с помощью которых производится оценка финансовых инструментов и их рисков (Black-Sholes model, точные формулы для вычисления цены европейских опций и их greeks: delta, gamma, vega, theta, rho).
Model Data — данные для модели (drift, volatility, etc.)
Valuation Parameters — параметры моделей (какой алгоритм случайных чисел используется, количество путей и шагов разбиения)

Entropy.Finance.Volatility:
Отдельно от всего остального, содержит класс для получения implied volatility по имеющимся ценам на европейские опции.

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

P.S. Финансовая часть библиотеки пока что содержит только элементарные вещи, но может быть использована на практике. За правильность я ответсвенности не несу, применяйте на свой страх и риск.

Жив ли проект?

Thu, 21 Jul 2005 13:38:39 GMT

Собственно, subj.

И еще вопрос: развлекался ли кто-нибудь с физическим источником энтропии? Как результаты? Просматриваются ли сетевые наводки? Пробовал ли кто-нибудь записывать случайную последовательность в течение длительного времени (например, недели)?

Алгоритмы для нормального распределения

Thu, 14 Jul 2005 15:15:53 GMT

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

namespace Entropy
{
    public class NormalDistibution
    {
        private readonly static double[] a = {-3.969683028665376e+01, 2.209460984245205e+02, -2.759285104469687e+02, 1.383577518672690e+02, -3.066479806614716e+01, 2.506628277459239e+00};
        private readonly static double[] b = {-5.447609879822406e+01, 1.615858368580409e+02, -1.556989798598866e+02, 6.680131188771972e+01, -1.328068155288572e+01};
        private readonly static double[] c = {-7.784894002430293e-03, -3.223964580411365e-01, -2.400758277161838e+00, -2.549732539343734e+00, 4.374664141464968e+00,  2.938163982698783e+00};
        private readonly static double[] d = {7.784695709041462e-03, 3.224671290700398e-01, 2.445134137142996e+00, 3.754408661907416e+00};

        /// <summary>
        /// http://www.cam.wits.ac.za/mfinance/papers/accuratecumnorm.pdf
        /// </summary>
        public static double CDF(double x)
        {
            double absX = Math.Abs(x);
            if (absX > 37)
                return 0;
            double exp = Math.Exp(-0.5 * absX * absX);
            double result = 0;
            if (absX < 7.07106781186547)
            {
                double tmp = 3.52624965998911e-02 * absX + 0.700383064443688;
                tmp = tmp * absX + 6.37396220353165;
                tmp = tmp * absX + 33.912866078383;
                tmp = tmp * absX + 112.079291497871;
                tmp = tmp * absX + 221.213596169931;
                tmp = tmp * absX + 220.206867912376;
                result = exp * tmp;
                tmp = 8.83883476483184e-02 * absX + 1.75566716318264;
                tmp = tmp * absX + 16.064177579207;
                tmp = tmp * absX + 86.7807322029461;
                tmp = tmp * absX + 296.564248779674;
                tmp = tmp * absX + 637.333633378831; 
                tmp = tmp * absX + 793.826512519948;
                tmp = tmp * absX + 440.413735824752;
                result /= tmp;
            }
            else
            {
                double tmp = absX + 0.65;
                tmp = absX + 4.0 / tmp;
                tmp = absX + 3.0 / tmp;
                tmp = absX + 2.0 / tmp;
                tmp = absX + 1.0 / tmp;
                result = exp / tmp / 2.506628274631;
            }
            return x < 0 ? result : 1.0 - result;
        }
 
        /// <summary>
        /// http://home.online.no/~pjacklam/notes/invnorm/
        /// </summary>
        public static double InverseCDF(double probability)
        {
            double p_low  = 0.02425;
            double p_high = 1 - p_low;

            if (probability > p_low && probability < p_high)
            {
                double q = probability - 0.5;
                double r = q * q;
                return (((((a[0] * r + a[1]) * r + a[2]) * r + a[3]) * r + a[4]) * r + a[5]) * q /
                    (((((b[0] * r + b[1]) * r + b[2]) * r + b[3]) * r + b[4]) * r + 1);
            }
            else if (probability < p_low) 
            {
                double q = Math.Sqrt(-2 * Math.Log(probability));
                return (((((c[0] * q + c[1]) * q + c[2]) * q + c[3]) * q + c[4]) * q + c[5]) /
                    ((((d[0] * q + d[1]) * q + d[2]) * q + d[3]) * q + 1);
            }
            else
            {
                double q = Math.Sqrt(-2 * Math.Log(1 - probability));
                return -(((((c[0] * q + c[1]) * q + c[2]) * q + c[3]) * q + c[4]) * q + c[5]) /
                    ((((d[0] * q + d[1]) * q + d[2]) * q + d[3]) * q + 1);
            }
        }
   }
}

Продолжаем разговор (алгоритм Ziggurat)

Thu, 14 Jul 2005 13:43:06 GMT

После почти никакого начала...
В общем, меняю цель проекта, а точнее возвращаюсь к тому, зачем всё это затевалось. А имеено написание библиотеки для оценки финансовых инструментов. Истинно случайные числа оказывается для этого не нужны и даже вредны. Необходимы так называемые квази-случайные числа Подобные числа обеспечивают быструю сходимость метода Монте-Карло.
До этого дела доберусь как только, так сразу.
Сейчас же выкладываю код для получения нормально-распределённых случайных чисел N(0,1) по методу Ziggurat. Может кому пригодится. Описание алгоритма находится здесь.

namespace Entropy
{
    public interface IRandom
    {
        double Next{get;}
    }

    public class ZigguratRandom : IRandom
    {
        private const double LAST_POINT = 3.6541528853610088;
        private const double AREA = 0.00492867323399;
        private double[] _x = new double[256];
        private double[] _r = new double[255];
        private Random _random;

        public ZigguratRandom()
        {
            _random = new Random();
            this.Init();
        }

        public ZigguratRandom(int seed)
        {
            _random = new Random(seed);
            this.Init();
        }

        public double Next
        {
            get
            {
                while (true)
                {
                    double u = 2.0 * _random.NextDouble() - 1.0;
                    int i = _random.Next() & 255;
                    if (Math.Abs(u) < _r[i])
                        return u * _x[i];
                    if (i == 0)
                        return this.GetFromTail(u < 0);
                    double x = u * _x[i];
                    double f0 = Math.Exp(-0.5 * (_x[i] * _x[i] - x * x));
                    double f1 = Math.Exp(-0.5 * (_x[i + 1] * _x[i + 1] - x * x));
                    if (f1 + _random.NextDouble() * (f0 - f1) < 1.0)
                        return x;
                }
            }
        }

        private void Init()
        {
            double r = LAST_POINT;
            double f = Math.Exp(-0.5 * r * r);

            _x[0] = AREA / f;
            _x[1] = r;
            _x[255] = 0;

            for (int i = 2; i < 255; ++i)
            {
                _x[i] = Math.Sqrt(-2.0 * Math.Log(AREA / _x[i - 1] + f));
                f = Math.Exp(-0.5 * _x[i] * _x[i]);
            }

            for (int i = 0; i < 255; ++i)
                _r[i] = _x[i + 1] / _x[i];
        }

        private double GetFromTail(bool isNegative)
        {
            double x, y;
            do
            {
                x = Math.Log(_random.NextDouble()) / LAST_POINT;
                y = Math.Log(_random.NextDouble());
            }
            while (-2.0 * y < x * x);
            return isNegative ? x - LAST_POINT : LAST_POINT - x;
        }
    }
}

Прошивка для PIC16 залита.

Fri, 10 Jun 2005 17:47:28 GMT

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

папка Hardware.

Пароли отправлены

Fri, 10 Jun 2005 17:35:22 GMT

Пароли отправлены, подтвердите, что всё нормально.

хотим пароль!

Thu, 09 Jun 2005 05:28:40 GMT

САБЖ

А зачем все это?

Sun, 05 Jun 2005 22:33:39 GMT

Насколько мне известно, большинство системных плат созданных на базе Intel chipset имеют встроенный генератор случайных чисел Intel 82802 (RNG).
Windows CRYPTO API его использует, для LINUX-а также имеются драйверы...

Свежая струя

Mon, 23 May 2005 12:49:20 GMT

Так. походу никто и не колышится с этим проектом. ну что ж. начнемс. какие задачи сейчас стоят. как я понимаю необходим истояник энтропии, т.е. исходных данных для генератора.
ясно что программное придумывать — лажа.
тогда остаётся аппаратное.
что в качестве аппаратного? генераторы белого шума. как будем анализировать? у меня есть некоторая разработка (моя) FFTek для спектральной оценки экспериментальных данных. так вот. может её заюзать?

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

В качестве дополнения к проекту

Wed, 04 May 2005 14:37:00 GMT

В качестве дополнения к проекту я собираюсь добавить получение нормально распределённых чисел.
Хочется реализовать что-нибудь очень быстрое и точное. Пока что есть идея реализовать алгоритм под названием "ziggurat".
Есть ли какие-нибудь предложения, пожелание, etc? Есть ли желающие написать этот алгоритм на С#?

Все уже украдено до нас :)

Mon, 02 May 2005 08:43:01 GMT