Board.KolibriOS.org

Official KolibriOS board
It is currently Wed Apr 24, 2019 9:15 pm

All times are UTC+03:00




Post new topic  Reply to topic  [ 11 posts ] 
Author Message
PostPosted: Fri Jun 15, 2018 8:14 pm 
Offline

Joined: Mon Dec 05, 2016 11:04 am
Posts: 129
Генерация по-настоящему случайных чисел без специального устройства (список),
являющегося интерфейсом к какому-нибудь физическому явлению - невозможна,
так как все вычисления происходящие внутри компа неслучайны...

Может быть в KolibriOS есть отличный генератор псевдослучайных чисел?
(интересует что-нибудь получше чем через "метод серединных квадратов")
Нашёл HMAC из маленькой библиотеки TLS, но в KolibriOS он не входит


Top
   
PostPosted: Fri Jun 15, 2018 8:44 pm 
Offline
User avatar

Joined: Mon Nov 19, 2012 5:22 pm
Posts: 455
Если честно, то смутно припоминаю, что кто-то выкладывал вполне простой код на асме, дающий случайные псевдочисла. Но уже не вспомню где. Поиск по форуму пробовал?

_________________
Чем больше сыра, тем больше в нём дыр. Чем больше дыр, тем меньше в нём собственно сыра. Значит, чем больше сыра, тем меньше сыра!


Top
   
PostPosted: Fri Jun 15, 2018 10:20 pm 
Offline

Joined: Mon Dec 05, 2016 11:04 am
Posts: 129
GerdtR wrote:
Если честно, то смутно припоминаю, что кто-то выкладывал вполне простой код на асме, дающий случайные псевдочисла
Да, и там использовался метод серединных квадратов. а я надеюсь, что:
1) есть генератор покруче, дающий более похожие на рандом числа
2) и уже встроен в Kolibri, например какая-то системная функция в API


Top
   
PostPosted: Mon Jun 18, 2018 10:07 am 
Offline

Joined: Tue Mar 08, 2016 11:00 pm
Posts: 432
Недавно реализовывал очень простой и удобный алгоритм - но не нашел близко.

Вот нагуглилось в Хакере прямо на ассемблере
https://xakep.ru/2005/01/19/25259/

Для рандомизации же можно взять системный наносекундный таймер


Top
   
PostPosted: Mon Jun 18, 2018 12:56 pm 
Offline

Joined: Sun Oct 30, 2011 6:43 pm
Posts: 1499
Нет, системной функции, выдающей псевдослучайные числа на данный момент не существует.
Siemargl wrote:
Для рандомизации же можно взять системный наносекундный таймер
Вполне достаточно инструкции rdtsc.
GerdtR wrote:
кто-то выкладывал вполне простой код на асме
Siemargl wrote:
Вот нагуглилось в Хакере прямо на ассемблере
Найти простой код можно и на С, например http://web.tiscali.it/pas80/random.htm Но ведь автора вопроса интересует именно тот, который уже встроен в Kolibri.


Top
   
PostPosted: Sun Jun 24, 2018 12:51 am 
Offline

Joined: Mon Dec 05, 2016 11:04 am
Posts: 129
0CodErr wrote:
Нет, системной функции, выдающей псевдослучайные числа на данный момент не существует
Благодарю за ответ! Получается, если понадобится рандом - нужно будет подтянуть его в конкретное приложение, потому что я пока не знаю как добавить системную функцию; к тому же могут возникнуть споры, какой вариант рандома лучше и более достоин включения в ядро
Siemargl wrote:
Вот нагуглилось в Хакере прямо на ассемблере - https://xakep.ru/2005/01/19/25259/
Спасибо, может пригодиться! Кстати, нашёл вторую часть этот статьи - https://xakep.ru/2005/01/20/25272/
- там рандом получше, тоже на ассемблере и тоже прошёл тест DIEHARD, но его период 2^128-1 против 2^125 из прошлой
Siemargl wrote:
Для рандомизации же можно взять системный наносекундный таймер
хорошая идея; можно дополнить координатами курсора мышки


Top
   
PostPosted: Wed Jul 04, 2018 9:10 am 
Offline

Joined: Tue Mar 08, 2016 11:00 pm
Posts: 432
Нашел хороший быстрый и простой алгоритм, о котором говорил ранее
Code:
//Marsaglia's MWC (multiply with carry) algorithm
static uint32_t m_z = 333, m_w = 888;  // any seeds not null
uint32_t GetUint()
{
    m_z = 36969 * (m_z & 65535) + (m_z >> 16);
    m_w = 18000 * (m_w & 65535) + (m_w >> 16);
    return (m_z << 16) + m_w;
}

double GetUniform()
{
    // 0 <= u < 2^32
    uint32_t u = GetUint();
    // The magic number below is 1/(2^32 + 2).
    // The result is strictly between 0 and 1.
    return (u + 1.0) * 2.328306435454494e-10;
}

скомпилированная в ассемблер целочисленная
Code:
GetUint:
  mov eax, DWORD PTR m_z
  movzx edx, ax
  imul edx, edx, 36969
  shr eax, 16
  add eax, edx
  mov DWORD PTR m_z, eax
  mov edx, DWORD PTR m_w
  movzx ecx, dx
  imul ecx, ecx, 18000
  shr edx, 16
  add edx, ecx
  mov DWORD PTR m_w, edx
  sal eax, 16
  add eax, edx
  ret
m_w:
  .long 888
m_z:
  .long 333


Top
   
PostPosted: Thu Jul 05, 2018 5:19 pm 
Offline

Joined: Mon Dec 05, 2016 11:04 am
Posts: 129
Siemargl wrote:
Нашел хороший быстрый и простой алгоритм, о котором говорил ранее
Благодарю, довольно эффективный код и не должно составить труда адаптировать для FASM

Честно признаться, я поздно заметил твоё сообщение и в итоге извлёк PRNG из библиотеки TLS-Library, там HMAC / PFR :

https://board.kolibrios.org/viewtopic.php?f=2&t=3736 Example of using TLS-Library parts for generating PRNG numbers

Разумеется он намного жирнее, остаётся лишь надеятся что эта "жирнота" оправдана и он хоть нанемного лучше в плане рандомности...

А в качестве сида я использую энтропию извлекаемую из 5 функций:

https://board.kolibrios.org/viewtopic.php?f=2&t=3735 Функции-"источники энтропии" для качественного рандома? + пример


Top
   
PostPosted: Fri Jul 06, 2018 12:30 am 
Offline
Mentor/Kernel Developer
User avatar

Joined: Fri Jun 30, 2006 9:01 am
Posts: 1247
http://www.agner.org/random/
http://websvn.kolibrios.org/filedetails ... random.inc

Of course, you need to properly seed it.

_________________
"Any intelligent fool can make things bigger, more complex, and more violent. It takes a touch of genius -- and a lot of courage -- to move in the opposite direction." Albert Einstein


Top
   
PostPosted: Sun Jul 15, 2018 6:34 pm 
Offline

Joined: Sun Oct 30, 2011 6:43 pm
Posts: 1499
Вот на этом сайте http://simul.iro.umontreal.ca есть некоторые генераторы: http://simul.iro.umontreal.ca/rng
Например
Code:
/*
   32-bits Random number generator U[0,1): lfsr113
   Author: Pierre L'Ecuyer,
   Source: http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme2.ps
   ---------------------------------------------------------
*/

#include "lfsr113.h"
#include <stdint.h>


/**** VERY IMPORTANT **** :
  The initial seeds z1, z2, z3, z4  MUST be larger than
  1, 7, 15, and 127 respectively.
****/

#define SEED 987654321

static uint32_t z1 = SEED, z2 = SEED, z3 = SEED, z4 = SEED;


double lfsr113 (void)
{
   uint32_t b;
   b  = ((z1 << 6) ^ z1) >> 13;
   z1 = ((z1 & 4294967294U) << 18) ^ b;
   b  = ((z2 << 2) ^ z2) >> 27;
   z2 = ((z2 & 4294967288U) << 2) ^ b;
   b  = ((z3 << 13) ^ z3) >> 21;
   z3 = ((z3 & 4294967280U) << 7) ^ b;
   b  = ((z4 << 3) ^ z4) >> 12;
   z4 = ((z4 & 4294967168U) << 13) ^ b;
   return (z1 ^ z2 ^ z3 ^ z4) * 2.3283064365386963e-10;
}
Возможно, кому-то будет интересно http://www-labs.iro.umontreal.ca/~simul ... /tu01.html
Quote:
collection of utilities for the empirical statistical testing of uniform random number generators
В User’s guide http://www-labs.iro.umontreal.ca/~simul ... estu01.pdf есть описания и формулы генераторов.


Top
   
PostPosted: Mon Aug 13, 2018 11:00 am 
Offline

Joined: Sun Oct 30, 2011 6:43 pm
Posts: 1499
Для не очень критичных задач вполне подойдут более простые способы, например, такой:
Code:
.Data
RandSeed Dword 0
.Code
; ******************************************************************************
; Initialize the random-number generator
Randomize Proc
  rdtsc
  mov RandSeed, eax
  ret
Randomize EndP
; ******************************************************************************
; Produce random values in a given range [MinValue..MaxValue]
Random Proc MinValue:Dword, MaxValue:Dword
  mov eax, 134775813
  mul RandSeed
  inc eax
  mov RandSeed, eax
  mov edx, MaxValue
  sub edx, MinValue
  inc edx
  mul edx
  mov eax, edx
  add eax, MinValue
  ret
Random EndP
В архиве пример для UASM и KolibriOS.lib
Attachment:
Random.7z [1.87 KiB]
Downloaded 37 times
Вывод результата:
Spoiler: Show
Attachment:
random.PNG
random.PNG [ 9.74 KiB | Viewed 1388 times ]


Top
   
Display posts from previous:  Sort by  
Post new topic  Reply to topic  [ 11 posts ] 

All times are UTC+03:00


Who is online

Users browsing this forum: No registered users and 2 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Limited