EPP: Generator liczb losowych

Autor: Dondu

Czasami w projektach zachodzi potrzeba użycia liczb losowych. Na szczęście kompilatory języka C mają odpowiednie funkcje, które generują pseudo-losowe liczby. Podstawową funkcją losową jest funkcja rand() dostępna w bibliotece stdlib.

W kompilatorze GCC funkcja ta losuje liczby od 0 do RAND_MAX, który jest zdefiniowany na stałe jako 0x7FFF. Oznacza to, że rand() potrafi losować liczby z zakresu od 0 do 32767.

Rozwiązania zadania:

• Generator liczb losowych by Dondu
• Generator liczb losowych by miszcz310
• ... czekamy na inne propozycje.

Zaletami rand() są przede wszystkim

• łatwość użycia 
• nie wymaga wykorzystania żadnych wewnętrznych układów mikrokontrolera.

Wadami rand() są natomiast:

• pseudo-losowość (w końcu to jest tylko program, czyli jakiś algorytm),
• zajmuje sporo miejsca w pamięci programu.

O ile pierwsza wada jest raczej mało istotna, bo funkcja jest dobrze opracowana, o tyle druga wada to już często powód, by szukać alternatywy.


Sporo miejsca to znaczy ile?
Spróbujmy to szybko sprawdzić:

#include <avr/io.h>

volatile unsigned char liczba_RND;  //wylosowana liczba

int main(void)
{
 while(1)
 {
  liczba_RND =    0;
 }
}

Taki kod zajmuje:

• Program: 430 bytes
• Data: 1 bytes

A teraz zobaczmy o ile wzrośnie gdy wykorzystamy funkcję rand():

#include <avr/io.h>
#include <stdlib.h>

volatile unsigned char liczba_RND;  //wylosowana liczba

int main(void)
{
 while(1)
 {
  liczba_RND =    rand();
 }
}

Ten kod zajmuje:

• Program: 930 bytes
• Data: 5 bytes

Jak widzisz przede wszystkim wzrosło wykorzystanie pamięci programu i to aż o 500 bajtów (!).
Dlaczego aż tyle? Ponieważ kompilator do kodu wynikowego dołączył część biblioteki stdlib, która jest niezbędna, by móc korzystać z funkcji rand().

500 bajtów - to duża strata czy mała? 
To zależy jaki mikrokontroler używasz i ile masz wolnej pamięci - czasami walczy się o kilkadziesiąt bajtów, a w skrajnych przypadkach o każdy bajt.

Jak to jest z tą losowością? Zobacz rozwiązania przedstawione powyżej.

---

Co można zrobić, by cennej pamięci nie tracić?

I to jest właśnie następne zadanie z cyklu Efektywne Planowanie Projektu.

Cel:
Opracować alternatywny sposób uzyskania generatora liczb losowych z przedziału 0-255.

Warunki:

1. ATmega8 z zegarem 8MHz,
2. generator ma pracować w tle, a liczba losowa ma być dostępna w dowolnym momencie w zmiennej globalnej: liczba_RND,
3. możesz wykorzystać dowolny wewnętrzny układ mikrokontrolera. 
4. możesz wykorzystać dodatkowe zewnętrzne elementy elektroniczne, ale priorytetem są: najniższy możliwy koszt i mała zajętość miejsca na PCB,
5. strata pamięci programu musi być sporo mniejsza niż 500 bajtów,
6. strata pamięci RAM także powinna być możliwie niewielka.
7. pozostałe określone dla całego cyklu EPP:  Efektywne Planowanie Projektu

UWAGA!!!
Kod ma być w wersji "gołej" tzn. zawierać kompletny program, ale bez dodatkowych funkcji jak np. wyświetlanie na LCD (zobacz jak to jest w moim rozwiązaniu).

Termin:
Termin nadsyłania rozwiązań do: 8 stycznia 2012r.
Termin już upłynął, ale możesz przesłać swoje rozwiązanie, jeżeli jest ono inne niż opublikowane.



Chcę przesłać swoje rozwiązanie!
Wszelkie zasady znajdziesz tutaj: EPP: Zasady uczestnictwa i publikacji

Pytania
Jeżeli masz pytania dot. tego zadania, zadawaj je w tym temacie w formie komentarza, w ten sposób wszyscy będą mogli przeczytać pytanie i moją odpowiedź.

Dotychczasowi autorzy rozwiązań z cyklu EPP:
Listę autorów, którzy nadesłali swoje rozwiązania do któregoś z artykułów z cyklu EPP, możesz znaleźć tutaj: Autorzy rozwiązań