flat assembler
Message board for the users of flat assembler.

Index > Projects and Ideas > RANDOM

Goto page Previous  1, 2, 3, 4  Next
Author
Thread Post new topic Reply to topic
edfed



Joined: 20 Feb 2006
Posts: 4216
Location: 2018
edfed
10^8 PRN/s
it is really impossible on a basic pentium

10 000 000 PRN
assuming a µP @ 1GHz
at least a PRN needs ten cycles
8 to generate
2 to load
so you need at least 100 000 000 cycles
100 MHZ
1Ghz/10

so it will take at least the 10% of the µP time

a solution can be find in loading PRN by packet of 6 dwords in eax...edi
and generate these number by packet too in eax...edi

ROR/ROL instructions combined with a imul seems to be a good solution

Code:

program:
...
call randomdex
...
jmp program 

randomdex:
;this PRNG is from an idea of DEX Wink
    mov eax,[.seed]             ;Move our number into A X
    imul eax,[.k1]                  ;This mutiply seed has -number
    add eax,[.k2]               ;Adds k2 to ax
    ror al,1                  ;Rotate right 1
    rol ah,1                  ;Rotate left 1
    ror eax,16
    ror al,1                  ;Rotate right 1
    rol ah,1                  ;Rotate left 1
    mov [.seed],eax             ;Moves AX into seed
    ret
align 4
.seed dd 0
.k1 dd 9821
.k2 dd 1
    


this dex random is fast but cannot generate 10 000 000 prn/s

Code:
randomedfed:
        add eax,[.seed1]
        or eax,1  
        ror eax,10
        add [.seed1],eax
        ret
align 4
.seed1 dd 0
    


i've left the idea of my previous random because it's too slow
now dex and edfed randoms are close in term of speed

by mixing both into a meta random, we can obtain a better random

Code:
rand:
.ptr=0
.list=4
dd 0
dd rand1
dd rand2
rand1:
include 'randomdex.inc'
rand2:
include 'randomedfed.inc'
macro RND
{
        mov ebx,[rand+rand.ptr]
        and ebx,1
        mov ebx,[rand+rand.list+ebx*4]
        call ebx
        add [rand+rand.ptr],eax 
}          
    


Last edited by edfed on 24 Oct 2007, 11:47; edited 1 time in total
Post 22 Oct 2007, 14:19
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2796
Location: dank orb
bitRAKE
Yes, 100 000 000 is difficult!

With no special priority I'm getting 80 000 000+ in windows.
(updates every half second)

I've attached a little test program.

It is important to note how large a period is needed to not repeat pattern at this fast rate. 32-bit seed is not sufficient - hence the larger state array and automata.

(EDIT: Suppose it might be good to say something about the processor - since I did state my measurement. It's a 1.6Ghz Pentium M, Dothan. So, less than 10 cycles per DW, about 1.67 x 10^8 per second. The project I'm working on needs a random block of bits - up to say 1k to be cautious.)


Description: Random numbers per half second.
Download
Filename: PPTest.rar
Filesize: 5.25 KB
Downloaded: 272 Time(s)



Last edited by bitRAKE on 22 Oct 2007, 18:42; edited 1 time in total
Post 22 Oct 2007, 17:04
View user's profile Send private message Visit poster's website Reply with quote
edfed



Joined: 20 Feb 2006
Posts: 4216
Location: 2018
edfed
good job bitrake!! Smile

i cannot code for windows Sad
too much (c) for my brain

can you make a bmp with the random numbers
pleaseee!
Post 22 Oct 2007, 18:07
View user's profile Send private message Visit poster's website Reply with quote
vid
Verbosity in development


Joined: 05 Sep 2003
Posts: 7106
Location: Slovakia
vid
just wondering... what do you need so many random numbers per second for?
Post 22 Oct 2007, 18:19
View user's profile Send private message Visit poster's website AIM Address MSN Messenger ICQ Number Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2796
Location: dank orb
bitRAKE
edfed wrote:
i cannot code for windows Sad
too much (c) for my brain
Just put your algorithm in "process:" and update [t_data] and you can time your code easily. Without WinASM and great templates/addin of shoorick I'd be lost. (c) means nothing to me:
Thomas Jefferson wrote:
He who receives an idea from me, receives instruction himself without lessening mine; as he who lights his taper [(candle)] at mine, receives light without darkening me.

That ideas should freely spread from one to another over the globe, for the moral and mutual instruction of man, and improvement of his condition, seems to have been peculiarly and benevolently designed by nature, when she made them, like fire, expansible over all space, without lessening their density in any point, and like the air in which we breathe, move, and have our physical being, incapable of confinement or exclusive appropriation. -- Thomas Jefferson, letter to Isaac McPherson, 13 August 1813
vid, genetic algorithms. I'll have some examples soon, maybe.
Post 22 Oct 2007, 18:52
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2796
Location: dank orb
bitRAKE
edfed wrote:
can you make a bmp with the random numbers
Sorry, I forgot to answer this before.

As you can imagine a BMP would not compress - it really is random. So I have attached a program that creates a colorful random display. If you'd like, press Alt+PrtScr keys to capture (to clipboard) a BMP and try to compress it - the EXE is smaller, lol.

I've also done some graphical distribution tests. At the 32-bit scale there doesn't appear to be any correlation between consecutive numbers.


Description: Graphical random pixel test.
Download
Filename: Random.zip
Filesize: 3.46 KB
Downloaded: 252 Time(s)

Post 23 Oct 2007, 02:02
View user's profile Send private message Visit poster's website Reply with quote
edfed



Joined: 20 Feb 2006
Posts: 4216
Location: 2018
edfed
is ramdom.exe made on the basis of PPalgorythm??
if it is, it shows that this algorythm is looping
the time to loop is 5 seconds on my PIII 800Mhz

WHAT IS DOING THIS CODE????
Code:
process:

.block: mov ebp, PPStateWidth/4
.one:   mov eax,DWORD [PPState+ebp*4-4]
        dec ebp
        jne .one
        call PPRenew
        add [t_data],PPStateWidth/4
        jmp .block
    

the .one loop seems to be really unsefull

ho i see
it's a task
and when we want a PRN, we just have to read the value of eax in tss
ok!!!!!
Post 23 Oct 2007, 22:20
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2796
Location: dank orb
bitRAKE
You are correct process: is just a thread. I like threads because there is no need to have a defined end - the parent process can just kill it, or slow it down - whatever is needed. Threads have there own stack (4k = local storage) and registers, so you can pretend the rest of the world does not exist when coding a thread.

We see here an example of this. The threads job is just to create random numbers and count how many it has created and moved into EAX. As you have noted, nothing is done with them beyond that. So, loading the value for use is also timed - which some people would concider not part of the algorithm.

Next we have a timer triggered every ~500ms. This timer just determines how the count has changed from last time and updates the dialog text.

The dialog gets everything going, displays numbers, and shuts everything down. I don't bother to suspend the thread opting just to kill it and create a new one - same with the timer. Some windows might not like this, but I think there is some recycling underneath - I hope!

Can you run the windows program? How many for 500ms?
I'm thinking less than 40 000 000, but not sure by how much.
Post 23 Oct 2007, 23:46
View user's profile Send private message Visit poster's website Reply with quote
edfed



Joined: 20 Feb 2006
Posts: 4216
Location: 2018
edfed
27 138 686 for a PIII 800MHz
and this is the same if blender runs or not

the way to read the PRN is a part of the algorythm

now i will think about the thread design

it seem's to be powerfull
and permit to place the different layers of the code in different threads

but the first problem is "what about the communication and the synchronisation between layers??

the 4K stack frame looks like the embeded ressources of a µC
it is funny to realise that a PENTIUM is in fact a multi µC system
each µC can easylly be a component of a system like real components on a PCB !!!!

assembling takes all its meaning with this
building a fasm code like an electronic board
YEAH this is the revelation of the year ( for me )

so now we need, not a library, but a manner to interconnect modules like on a printed circuit board
if anyone is agree, then lets go

we need the notion of ship, bus, gate, mux, dmux etc etc...
like in real electronics
Post 24 Oct 2007, 00:27
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2796
Location: dank orb
bitRAKE
edfed wrote:
but the first problem is "what about the communication and the synchronisation between layers?
The LOCK prefix or XOR instruction can be used to pass data between threads and a common memory address.

Ultrano has a good project here:
http://www.codeproject.com/useritems/FastReadWriteLock.asp

AFAIK, all the threads share the same address space. Since only one DWORD can be passed to the thread on the stack, maybe it should be an pointer to an array of all other threads at that level? Each thread could store it's stack pointer in the array, and other threads could access it's local data. (funny idea)

I like the µC analogy.

Hm...blender not doing anything? It was slower than I expected.
Post 24 Oct 2007, 01:51
View user's profile Send private message Visit poster's website Reply with quote
edfed



Joined: 20 Feb 2006
Posts: 4216
Location: 2018
edfed
blender was rendering a scene
and the PRN number is closely the same with or without a big process

it means that the PRN reader thread is a idle task no??

the prng needs more optimisation, thats all folks!!!



_____________________________________
GLA GLA the winter is still there, ho shit
so it's time to code now!
Post 24 Oct 2007, 11:04
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2796
Location: dank orb
bitRAKE
Some more random bliss....
(file updated in later post)


Last edited by bitRAKE on 31 Oct 2007, 00:38; edited 2 times in total
Post 27 Oct 2007, 06:54
View user's profile Send private message Visit poster's website Reply with quote
edfed



Joined: 20 Feb 2006
Posts: 4216
Location: 2018
edfed
mybug.zip is really unusefull Wink

give us at least the source code
and then it will be usefull Wink Wink
Post 29 Oct 2007, 15:14
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2796
Location: dank orb
bitRAKE
Here are the sources, but it might still be useless. As of now I am unable to determine why the main process thread will not terminate. All the other threads terminate without a problem, but WM_QUIT is never seen in main message loop.

From what OllyDbg is indicating only the process thread is active and pointing to some place in the kernel - CPU usage is 0%. If I kill the thread through OllyDbg then the process terminates.

The number of auxillary threads created doesn't effect it. I'm using the default window PROCs to close and post the quit message - doing it manually didn't change anything either.

Most the other problems have been solved. Can't set dialog as child in resource because it looses focus. There are compatiblity problems with Win9x, but I'm targeting Win2k+. Using Pelle C linker because MS link doesn't like all the changing object file flags FASM generates.


Description:
Download
Filename: MyBug.2007.10.30.rar
Filesize: 11.73 KB
Downloaded: 245 Time(s)

Post 31 Oct 2007, 00:35
View user's profile Send private message Visit poster's website Reply with quote
LocoDelAssembly
Your code has a bug


Joined: 06 May 2005
Posts: 4633
Location: Argentina
LocoDelAssembly
Post 31 Oct 2007, 00:50
View user's profile Send private message Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2796
Location: dank orb
bitRAKE
Thank you, that worked.

For some reason I thought the default handler did that.

(Actually, it wouldn't make much sense if it did. Embarassed )
Post 31 Oct 2007, 01:04
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2796
Location: dank orb
bitRAKE
I've always liked using the Chaos Game to look at random number generators. At these speeds it is quite entertaining, imho. Very Happy


Description: Multi-threaded Chaos Game
Download
Filename: ChaosTest.zip
Filesize: 2.88 KB
Downloaded: 243 Time(s)

Post 31 Oct 2007, 17:42
View user's profile Send private message Visit poster's website Reply with quote
edfed



Joined: 20 Feb 2006
Posts: 4216
Location: 2018
edfed
i'va found a good random generator in a 256b demo from ³ Luks <-> luks@host.sk
Code:
random:
mov ax,123
imul ax,123
rol ax,5
mov [cs:random+1],ax
ret
    
Post 16 Nov 2007, 04:16
View user's profile Send private message Visit poster's website Reply with quote
vid
Verbosity in development


Joined: 05 Sep 2003
Posts: 7106
Location: Slovakia
vid
Quote:
i'va found a good random generator in a 256b demo from

erm, good in which qualities, besides code size?
Post 16 Nov 2007, 07:58
View user's profile Send private message Visit poster's website AIM Address MSN Messenger ICQ Number Reply with quote
LocoDelAssembly
Your code has a bug


Joined: 06 May 2005
Posts: 4633
Location: Argentina
LocoDelAssembly
haha, funny way to store the seed. Anyway, this is one of the less random function ever, it always start with a 123 seed (or there is a randomize somewhere?), and the multiplicator (123), is not a prime number (people says that prime numbers are better but I never understood why an odd number is not just enough).

However surely it is good for the purposes of that demoscene Smile
Post 16 Nov 2007, 12:46
View user's profile Send private message Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  
Goto page Previous  1, 2, 3, 4  Next

< Last Thread | Next Thread >
Forum Rules:
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 vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Copyright © 1999-2019, Tomasz Grysztar.

Powered by rwasa.