przypadkowe dzialanie procesora ?
Widzisz wersję archiwalną tematu "przypadkowe dzialanie procesora ?" z forum pl.comp.programming
popo - 26 Lip 2001, 12:36
ostatnio zastanawialem sie chyba nad ciekawym problemem i nie dałem sobie z
nim rady ---zupelnie nie wiem jak osiągnąć programowe losowanie - tak aby
rzeczywiście procesor wybierał losowo element jakiegoś zbioru. moze ktos
dysponuje pomyslem na jakiś algorytmem lub choć opisem na czym mogłaby
polegać losowa praca procesora.
pluton - 26 Lip 2001, 13:44
ostatnio zastanawialem sie chyba nad ciekawym problemem i nie dałem sobie
z
nim rady ---zupelnie nie wiem jak osiągnąć programowe losowanie - tak
aby
rzeczywiście procesor wybierał losowo element jakiegoś zbioru. moze ktos
dysponuje pomyslem na jakiś algorytmem lub choć opisem na czym mogłaby
polegać losowa praca procesora.
Tak, problem rzeczywiscie jest ciekawy.
oraz masa bibliotek programistycznych, implementujacych
rozwiazania opisane w tych ksiazkach.
cul
pluton
Edwardek - 26 Lip 2001, 14:13
zdaje sie, ze procesor sam z siebie nie pracuje losowo
- kazdy skutek w nim powinien chyba miec okreslona przyczyne
a jesli tak nie jest to chyba mamy do czynienia z procesorem
uszkodzonym.....
......bez uzywania skompolikowanych algorytmow, czytania
mnostwa ksiazek losowanie mozna zrobic za pomoca
mikstury jakie czyni czarownica: czyli jedno ucho nietoperza,
dwie nogi zielonej zaby, kropla octu - wszystko do gara,
wymieszac i pobrac lyzka ze srodka . Tlumaczac na komputerowy:
biezesz sobie aktualny czas,
biezesz sobie wartosc jaka moze siedziec gdzies w portach com/lpt
czytasz numery seryjne roznych rzeczy, czas ostatniej modyfikacji
jakiejs systemowej biblioteki, czas instalacji systemu itp itd.....
ilosc ostatnio wcisnietych klawiszy, laczysz to w jakims sobie tylko
znanym zawilym algorytmem i do dziela........ :-) ja tak robilem
w asm padajacy sniezek i wygladalo to b. realistycznie, zadnych
jakichs powtorzen, nie zauwazalo sie zadnych pewnych wzorow
- snieg padal naprawde chaotycznie i b. ladnie - zupelnie jak ten
za oknem!
Marcin 'Qrczak' Kowalczyk - 26 Lip 2001, 15:39
ostatnio zastanawialem sie chyba nad ciekawym problemem i nie dałem sobie z
nim rady ---zupelnie nie wiem jak osiągnąć programowe losowanie
Najczęściej robi się tak, że mamy deterministyczny algorytm generujący
ciąg liczb na podstawie zmieniającego się stanu. Na przykład taki
(pseudokod w stylu Pascala):
var RandSeed : Word32;
function Random (N : Integer);
begin
Random := RandSeed * (1 shl 32) div N;
RandSeed := (RandSeed * $8088405 + 1) mod (1 shl 32)
end;
Ten algorytm (z taką stałą) jest używany w Borland Pascalu
(implementacja musi być trochę inna bo zapis powyżej powoduje
przepełnienie).
Na początku programu RandSeed jest inicjalizowane wartością, która w
jakiś sposób zależy od niepowtarzalnych czynników. W Borland Pascalu
robi to funkcja Randomize, która inicjalizuje RandSeed bieżącym czasem.
Jeśli potrzeba liczb losowych naprawdę dobrej jakości, to można
zaburzać stan losowymi czynnikami częściej. Pod Linuxem są urządzenia
/dev/random i /dev/urandom, z których można odczytywać losowe bajty.
Jądro systemu miesza pulą losowości na podstawie nieprzewidywalnych
danych jak czasy uderzenia klawiatury, dane na portach komputera
albo czas wykonania operacji dyskowych. Ale do większości zastosowań
wystarczają algorytmy pseudolosowe, które potrzebują tylko małego
źródła niedeterminizmu na początku.
Piotr Wyderski - 27 Lip 2001, 10:31
ostatnio zastanawialem sie chyba nad ciekawym problemem i nie dałem sobie
z
nim rady ---zupelnie nie wiem jak osiągnąć programowe losowanie - tak
aby
rzeczywiście procesor wybierał losowo element jakiegoś zbioru.
Hm, to zalezy, co rozumiesz przez "losowo". Jesli wystarczy,
aby otrzymane liczby sprawialy wrazenie losowych, to poczytaj
posty kolegow. Jesli zas chcesz prawdziwej losowosci, to
bez wsparcia sprzetowego sie nie da (np. generator szumu
+ wzmacniacz szumu +bramka Schmitta). Na marginesie, to
chipset i815 ma generator liczb losowych, ale szczegolow nie
znam.
Pozdrawiam
Piotr Wyderski
Gayos - 27 Lip 2001, 15:03
aby otrzymane liczby sprawialy wrazenie losowych, to poczytaj
posty kolegow. Jesli zas chcesz prawdziwej losowosci, to
bez wsparcia sprzetowego sie nie da (np. generator szumu
+ wzmacniacz szumu +bramka Schmitta). Na marginesie, to
Otóż da się.
W "Sztuce Elektroniki" jest coś na ten temat. W skrócie:
Cyfrowy generator szumu jest zrealizowany na rejestrze przesuwającym (z we i
wy szeregowym). Niech rejestr ma długość m. Dodatkowa bramka XOR zaczepiona
na wyjściu (m) i pewnym bicie (n) wewnątrz rejestru wytwarza bit, który
podajemy na wejście rejestru. Jeśli odpowiednio dobierze się bit n to dla
rejestru o długości m liczba cykli po którym stan rejestru się powtórzy
wynosi 2^m-1. cytat: "Czas trwania sekwencji pseudolosowej w rejestrze
100-bitowym, taktowanym zegarem 10MHz, byłby milion razy dłuższy niż wiek
wszechświata."
Tak więc nie jest problemem wykorzystanie 3 lub 4 rejestry procesora aby
utworzyć z nich rejestr przesuwny. Problem jest znaleźć odpowiedni bit n.
Dla rejestrów m<40 są podane bity n, ale przy m=39 i n=35 liczba cykli K=
549 755 813 887 Dużo czy mało? Raczej mało jak na dzisiejsze moce
procesorów (dla 10Mips to jakieś 15h)
Warunkiem na uzyskanie maksymalnie długiego ciągu dla szukanego bitu n jest
"nieredukowalność wielomianu 1+ x^n + x^m -musi on być wielomianem
pierwszym w ciele Galois" ;-) Dla mnie czarna magia. Ale może ktoś się
pokusi znaleźć n dla m=96 (3 rejestry procka)?
A w tej chwili to możecie zrobić podany wyżej rejestr dla m=39. To zaledwie
kilkanascie linii w asemblerze.
Konrad 'kaspy' Palczynski - 28 Lip 2001, 09:52
ostatnio zastanawialem sie chyba nad ciekawym problemem i nie dałem sobie z
nim rady ---zupelnie nie wiem jak osiągnąć programowe losowanie - tak aby
rzeczywiście procesor wybierał losowo element jakiegoś zbioru. moze ktos
dysponuje pomyslem na jakiś algorytmem lub choć opisem na czym mogłaby
polegać losowa praca procesora.
Czyzybys zetkna sie z tym problemem co ja, kiedys? Pisalem cos na 51 i
potrzebowalem osiagnac cos w rodzaju niedeterminizmu - uruchamiamy
rownoczesnie ten sam program na obu procesorkach, jeden daje wyniki inne
niz drugi... Niestety, bez zewnecznych uzadzen (IMHO) nie dalo sie tego
osiagnac.
Piotr Wyderski - 28 Lip 2001, 10:38
Otóż da się.
W "Sztuce Elektroniki" jest coś na ten temat. W skrócie:
Cyfrowy generator szumu jest zrealizowany na rejestrze przesuwającym (z we
i
wy szeregowym). Niech rejestr ma długość m. Dodatkowa bramka XOR
zaczepiona
na wyjściu (m) i pewnym bicie (n) wewnątrz rejestru wytwarza bit, który
podajemy na wejście rejestru.
Ale ten LFSR bedzie generowal liczby _pseudolosowe_.
Innymi slowy, znajac budowe ukladu i zawarta w nim liczbe
mozna juz bez najmniejszego problemu wyznaczyc kolejne
wychodzace z niego liczby "losowe". Mi natomiast chodzilo
o prawdziwe liczby losowe, np. powstale ze wzmocnienia
szumow termicznych diody itp.
cytat: "Czas trwania sekwencji pseudolosowej w rejestrze
100-bitowym, taktowanym zegarem 10MHz, byłby milion razy dłuższy niż wiek
wszechświata."
Mozliwe (tzn. nie znam odpowiedniej teorii), ale dlugosc okresu
nie zmienia faktu, ze liczby beda jedynie pseudolosowe, czyli
przewidywalne. Dwa roboty sterowane takimi samymi generatorami,
ktore zainicjowano ta sama wartoscia beda wykonywaly identyczne ruchy.
Pozdrawiam
Piotr Wyderski
Marcin 'Qrczak' Kowalczyk - 28 Lip 2001, 15:42
| cytat: "Czas trwania sekwencji pseudolosowej w rejestrze | 100-bitowym, taktowanym zegarem 10MHz, byłby milion razy dłuższy niż wiek | wszechświata." Mozliwe (tzn. nie znam odpowiedniej teorii), ale dlugosc okresu
nie zmienia faktu, ze liczby beda jedynie pseudolosowe, czyli
przewidywalne. Dwa roboty sterowane takimi samymi generatorami,
ktore zainicjowano ta sama wartoscia beda wykonywaly identyczne ruchy.
Jeśli jest tak długi okres, to mogą nie istnieć dwa generatory
zainicjalizowane tymi samymi wartościami.
Piotr Wyderski - 28 Lip 2001, 16:49
Jeśli jest tak długi okres, to mogą nie istnieć dwa generatory
zainicjalizowane tymi samymi wartościami.
Hmm... a to dlaczego? Lutuje sobie dwa identyczne uklady,
wpisuje do nich _ta sama_ wartosc i od tej chwili oba dzialaja
deterministycznie, przy pomocy kartki i olowka moge generowac
wartosci identyczne jak one, bo znam schemat i ziarno.
Pozdrawiam
Piotr Wyderski
Marcin 'Qrczak' Kowalczyk - 28 Lip 2001, 18:26
| Jeśli jest tak długi okres, to mogą nie istnieć dwa generatory | zainicjalizowane tymi samymi wartościami. Hmm... a to dlaczego? Lutuje sobie dwa identyczne uklady,
wpisuje do nich _ta sama_ wartosc
Po co wpisywać do nich tę samą wartość? Nie mówię, że nie dałoby się
tego zrobić, tylko że to będą dobre generatory jeśli się tego nie zrobi
(o ile one zapamiętują stan między włączeniami zasilania).
Lucifer - 28 Lip 2001, 21:06
Witam
Ale ten LFSR bedzie generowal liczby _pseudolosowe_.
Innymi slowy, znajac budowe ukladu i zawarta w nim liczbe
mozna juz bez najmniejszego problemu wyznaczyc kolejne
wychodzace z niego liczby "losowe". Mi natomiast chodzilo
o prawdziwe liczby losowe, np. powstale ze wzmocnienia
szumow termicznych diody itp.
Wg mnie w tak mozna postapic z kazdym losowym zjawiskiem w przyrodzie -
im wiecej znasz szczegolow na jego temat z tym wieksza dokladnoscia
potrafisz okreslic kolejne zdarzenia. Wiec teoretycznie nic nie jest
losowe i spowodowane innym zdarzeniem, czynnikiem lub czynnikami.
lucifer
Piotr Wyderski - 29 Lip 2001, 07:40
Po co wpisywać do nich tę samą wartość?
Tylko po to, aby pokazac, ze generowane przez nie
liczby w rzeczywistosci nie sa losowe, a calkowicie
deterministyczne, choc rozklad "prawdopodobienstwa"
ich wystepowania moze byc interesujacy. Dokladniej,
chodzilo o to:
Ja: "Do uzyskania prawdziwej losowosci [na x86]
potrzeba wsparcia sprzetowego".
Gayos: "Nie potrzeba, wystarczy zasymulowac LFSR"
Ja: "Pokazuje, ze uklad nie generuje liczb prawdziwie
losowych, a jedynie pseudolosowe"
Nie mówię, że nie dałoby się tego zrobić, tylko
że to będą dobre generatory jeśli się tego nie zrobi
Zgadzam sie. A na marginesie, to czy ktos z Was
zna trudnosc obliczeniowa odtworzenia ziarna
LFSR, jesli sie zna budowe ukladu i dowolny, ale
skonczony ciag wygenerowanych liczb?
Pozdrawiam
Piotr Wyderski
Piotr Wyderski - 29 Lip 2001, 07:40
Warunkiem na uzyskanie maksymalnie długiego ciągu dla szukanego bitu n
jest
"nieredukowalność wielomianu 1+ x^n + x^m -musi on być wielomianem
pierwszym w ciele Galois"
A pytanie jak to stwierdzic jest ciekawe, zadalem je na pl.sci.matematyka.
W moich ksiazkach jest tylko definicja wielomianu nieredukowalnego nad
cialem, ale ani slowa o tym, jak to sprawdzic.
Pozdrawiam
Piotr Wyderski
Portale generuja straty bo to dzialalnosc reklamowa a nie dochodowa Re: Wartosc portali
Zone Alarm pod XP - uprawnienia dla Generic Host Process (svchost.exe)
Win2k (SP4): Generic Host Process for Win32 Services - robak?
Odp: openGL
telfon komorkowy
hymn juventusu
xray scanner
ksiazki somozy sa niezwykle
uw szczecinski
tatuaze com pl
alergolog
czy warto zaktualizowac debiana do wersji
copa de la vida
Katalog wypowiedzi z for internetowych ^^ Strona Główna
|
|