Path: Home => AVR-EN => Applications => Random ATtiny13 => Calculation   Diese Seite in Deutsch: Flag DE Logo
Random colors 250*250 AVR applications

Random number generation with ATtiny13
Calculation of random numbers in assembler

1 To calculate random numbers in assembler

To calculate random numbers we need some mathmatical operations that change as much as possible bits in binary numbers. Here, we combine the following methods:
  1. An Exclusive-Or: This is what any random generator uses. ExOr flips all bits that are ones in both binary numbers to zero and sets all bits that are zero in the first number and one in the second number. This is done in assembler with this code: EOR Register1,Register2. The result of the operation is stored in Register1.
  2. Swap: This operation exchanges the upper four bits of a number (upper nibble) with the lower four bits (lower nibble) and vice versa. In assembler this is done with the instruction: SWAP Register.
  3. Adding: This operation adds two binary numbers. All bits at the same position, that are one in both numbers, will be zero. All bits that are one in the second number and one in the first, will change to one. Only bits that are zero in both numbers will remain zero. But: as any bit can produce an overflow to the next bit if both bits are one, this overflow adds to the next position. In the consequence adding can change lots of bits in a number. Adding in AVR-Assembler goes with ADD Register1,Register2, the result is again in Register1.
With these three instructions the assembler random generator is nearly complete:

.def rN1 = R16 ; Register for the first random number
.def rN2 = R17 ; Register for the second one
  ldi rN1,cStart1 ; Start the random generator with the first seed
  ldi rN2,cStart2 ; and with the second seed
Loop:
  eor rN1,rN2 ; Exclusive-Or with the second seed
  swap rN1 ; Swap nibbles
  add rN2,rN1 ; Add result to the second seed
  rjmp Loop

Note that the generation of a random like this requires only three clock cycles, which, in an ATtiny13 and it's default clock, translates to 2.5 µs. Yes, assembler is faster than any other language, but requires some brain efforts ahead.

The only question left is: with which seed numbers (cStart1, cStart2) to start with? And after how many runs through the loop will the number row repeat?

The criterion for this selection should be that all numbers between 0 and 255 appear nearly with the same count, I call that homogeniosity. To find out how homogeneous the results are, I varied cStart1 and cStart2 between 0 and 255 and repeated the loop with each combination 100,000 times. Of course I skipped the combination (0|0) and did that in a PC with a Lazarus Pascal program. For each combination I counted the number occurences of 0 to 255, which ideally should be 100,000 / 256 = 390.625. I took the differences of each count from this man value, squared this (the larger the difference the higher the contribution to the sum) and added it to a difference sum. When done, I took the root of the sum. The larger the resulting sum gets, the less homogeneous is the combination.

Sums of inhomogeniosity These are those sums for the combinations between 0x88 and 0xBC for cStart1 and 0x02 for cStart2. As can be seen, most of the combinations have small sums around 200, but certain combinations have six or seven times larger sums. The optimal sum of the whole 65,535 combinations has the combination 0x02A8 (N1=168, N2=2), but many other combinations are not significantly less homogeneous.

Certain combinations are obviously less recommendable as starters. Simply avoid those with a high sum.

Inhomogenity and periodicity The second question is, after how many cycles the number rows repeat. It is sufficient for that to search the first four numbers in the complete data set for each combination. The astounding result can be seen in the graph, again for the combinations between 0x0288 to 0x02BC. All the succesful combinations with a small inhomgeneous sum (left, red) have the same period length of 53,961 (right, green), all unsuccesful combinations with a higher inhomogeneous sum (has been cut at 250) have periods of around 20.

In practice, a series of 53,961 different numbers is not seen as a repetition. When displayed once in each each second, the period repeats after 15 hours. Three randoms on an RGB LED repeat after 5 hours. Nothing that can be recognized by a trained human, and even the most strict criticizers won't complain that they were bored by the same color row every 5 hours.

Number counts in 100,000 loops, optimal seeds This shows the counts for 0 to 255 with the seed combination 0x02A8. If you do not think that this is rather homogeneous I'll call you a hyper-hyper-hyper-criticizer.

The first 256 random numbers If you'll try simulation of the above loop instructions, e. g. with avr_sim, here are the first 256 random numbers with the 168/2 combination in decimal and hexadecimal format.

The best 25 combinations in 100k runs The best 25 combinations in 1M runs For those who need more than only one seed combination, here are the 25 best ones. To the left, in 100,000 runs, to the right in 1 million runs. Results differ slightly, but all combinations are very homgeneous. Numbers were crunched with a Lazarus program, the source code can be downloaded here.

And: Yes, every type of AVR understands EOR, SWAP and ADD. So you do not need to invent it from scratch when you need it for an Arduino controller.

And: No, I will not answer any questions concerning how to insert the three assembler instructions as inline assembler for Arduino freaks, how to translate that algorithm into C or other high-level languages, or how to translate it to generate random floating point numbers in 32 or 64 bit, and how to stuff the floating point library into an ATtiny13's small flash memory.

Page top Main page Display Noise generation Analysis sine wave


Praise, error reports, scolding and spam please via the comment page to me.

©2020 by http://www.avr-asm-tutorial.net