Algorithms

Moderators: None (Apply to moderate this forum)
Number of threads: 402
Number of posts: 786

This Forum Only
Post New Thread
Single Post View       Linear View       Threaded View      f

Report
About random question Posted by zydgyy on 27 Sept 2009 at 10:01 PM
Hi, guys!
I have read a lot algorithms about random-generation,most of them use the system time as the seed,and then calculate it with
formula Rand_Number = (Rand_Seed * X + Y) mod Z, why use the system time as the seed,is it random enough? then if the seed is random,why calculate it again through this formula?
Report
Re: About random question Posted by anthrax11 on 28 Sept 2009 at 12:56 AM
It depends.

For security-related applications, where you would want to create random keys so that a third party couldn't guess them, using only the time is not enough. The operating system typically provides means of creating better random values (Linux and Mac have /dev/random, Windows has a cryptography API). The OS uses seeds such as disk writes per second, processor cache misses, port I/O, time, etc.

For artificial intelligence, fuzzy logic or things like that, using 1-2 seeds is fine. But because time is very predictable and changes at a fixed rate, then in some cases it might not seem random enough. Then you would use a formula like you described to constantly recalculate the seed number based on the current time and the previous seed number.

Time is a good seed, because it is one of the few metrics that are readily available for all programs at any permission levels. You would need admin access to get values from other system hardware. Another value that is often used in games is the time between keypresses, however many other applications don't get any keyboard input at all.

The formula Rand_Number = (Rand_Seed * X + Y) mod Z is good, because there is a good chance the number will overflow because of the multiplication. This means the higher digits are discarded, because they won't fit into the 32 or 64 bits the computer uses to store the number. Without the formula, the seed number would only change linearly, because time is linear.
Report
Re: About random question Posted by zydgyy on 28 Sept 2009 at 7:35 AM
If I use a 8-bit MCU,there is no explicit system time,so how can i
get the seed source?!Thank you!
Report
Re: About random question Posted by anthrax11 on 4 Oct 2009 at 1:08 PM
I don't know what hardware you have or what the purpose is, but there are a few generic options.

The last used seed number could be stored into permanent memory (if available) and used the next time when needed. This way the random values are good as long as the seed isn't lost.

Maybe you don't even need very good random values? That would be the case if the values are needed for doing something not so important, like making a visual effect, for example. Then you could just use any preset seed value.

If you have some input to your MCU, then you can sample values from it. For example, consider an electronic dice. One way to get a random value is to measure the time between pressing the key and releasing it. (You may not have time, but maybe you have a timer). Be creative!

There are special additional chips for generating random bits, but you can also use things like accelerometers, thermistors, photoresistors, etc. to gather variable data from the environment.



 

Recent Jobs

Official Programmer's Heaven Blogs
Web Hosting | Browser and Social Games | Gadgets

Popular resources on Programmersheaven.com
Assembly | Basic | C | C# | C++ | Delphi | Flash | Java | JavaScript | Pascal | Perl | PHP | Python | Ruby | Visual Basic
© Copyright 2011 Programmersheaven.com - All rights reserved.
Reproduction in whole or in part, in any form or medium without express written permission is prohibited.
Violators of this policy may be subject to legal action. Please read our Terms Of Use and Privacy Statement for more information.
Operated by CommunityHeaven, a BootstrapLabs company.