Primes

[Thomas_1110]

Hello
1. I wrote a program, that calculate primes. Looking in my code. Is there a way to makes its faster?
2. To calculate 100000 primes and display it in a "Edit" takes lesser than a second. When I cut the lines 114 and 115 then it takes over 30 seconds.

Forgive my bad English
best regards, Thomas

[dedndave]

underneath the message reply area is an "additional options" hyperlink
click that - then add the file(s) - only zips are allowed
let me look at the primes generator - there are hundreds of these on the web, i am sure - lol
certainly - the dword 2 string routine could be made faster
there are many routines in the forum for that (as well as the masm32 library)
fast binary 2 string conversions is one of our favourite passtimes - lol

[UtillMasm]

 :U

[Thomas_1110]

Hello
@dedndave:
First I used the str$() with szappend to write the DWord values as a string in Memory. It was really slow (over 30 seconds for 100 000 values). 
@UtillMasm: Thanks

[dedndave]

well - i could give you faster code - Drizz has a pretty fast one
thing is -
most of these routines are designed to right-justify the output string in a buffer field and return the pointer to the beginning
you'd have to modify your code a little bit to use them
as for the GetPrime function, i looked briefly in other threads using the forum search engine
there seems to be some good fast alternatives
just search "prime numbers" or "generate primes"
these guys are pretty advanced coders and have played with several options, including using sse/sse2 instructions

[raymond]

There are definitely MUCH faster ways to buid the list of primes. No division needed if you use a sieve.

Usually, you need such a list of primes to perform some other operation where you need those primes in binary form. Converting that list to ASCII is of little use, unless you are doing it as a programming exercise.

[Thomas_1110]

Hello
Has anyone an explaination why the program runs faster much more time with lines 111, 112 (I first wrote 114, 115, forgive me).
I comment the lines with "without this line" here in the code. This lines do only append a Space in Mem2.

Code Select Expand


WndProc proc hWnd:HWND, uMsg:UINT, wParam:WPARAM, lParam:LPARAM
local rect :RECT, x1 :DWORD, y1 :DWORD, x2 :DWORD, y2 :DWORD
local time1 :SYSTEMTIME, time2 :SYSTEMTIME, Zeit3 :SYSTEMTIME
.if uMsg == WM_CREATE
invoke GetClientRect, hWnd, ADDR rect
mov x1, 0
mov y1, 100
mov eax, rect.right
mov x2, eax
mov eax, rect.bottom
sub eax, 100
mov y2, eax
invoke CreateWindowEx, WS_EX_CLIENTEDGE, chr$("EDIT"), NULL,\
    WS_CHILD or WS_VISIBLE or WS_BORDER or WS_VSCROLL or ES_READONLY or ES_MULTILINE ,\
x1, y1, x2, y2, hWnd, EditID1, hInstance, NULL
mov  hEdit1, eax
invoke CreateWindowEx, WS_EX_CLIENTEDGE, chr$("BUTTON"), chr$("Test"),\
    WS_CHILD or WS_VISIBLE or BS_TEXT, 20, 20, 150, 40, hWnd, ButtonID1, hInstance, NULL
    mov hButton1, eax
;-----------------------------------------------------------------------------
.elseif uMsg == WM_CLOSE
invoke DestroyWindow, hWnd
;-----------------------------------------------------------------------------
.elseif uMsg == WM_DESTROY
invoke PostQuitMessage, NULL
;-----------------------------------------------------------------------------
.elseif uMsg==WM_COMMAND
.if wParam == ButtonID1
mov Mem1, alloc(memsz)
  mov Mem2, alloc(writesz)
  invoke GetLocalTime, addr time1
  invoke GetPrime, Mem1
  mov esi, Mem1
  mov edi, Mem2
  xor ecx, ecx

@@:
invoke DWordToString, [esi+ecx], edi
add edi, eax                   ; without this line
add edi, 1                      ; without this line
mov byte ptr [edi], 32
add edi, 1
  add ecx, 4
  cmp ecx, memsz
  jb @B
  sub edi, 1
  mov byte ptr [edi], 0
invoke GlobalFree, Mem1
invoke SetWindowText, hEdit1, Mem2
invoke GlobalFree, Mem2
invoke GetLocalTime, addr time2
invoke GetTimeDifference, addr time1, addr time2, addr Zeit3
invoke TimeToString, Zeit3, addr TimeString
invoke MessageBox,NULL , addr TimeString, chr$("Zeitmessung"), NULL
mov byte ptr TimeString, 0
.endif
.else
invoke DefWindowProc, hWnd, uMsg, wParam, lParam
ret
.endif
xor eax,eax
ret
WndProc endp


@raymond:
Thanks for the tip. I will work on it in the next time. And yes, it's for exercise. I'm new in assembly, learning by doing! :bg
btw: you mean the "Sieve of Eratosthenes" ?

[dedndave]

i don't see anything obvious
except that esi and edi should be preserved (along with ebx, ebp, and DF)
maybe you are using registers you should not be using and the system takes a while to recover from it ?

push esi
push edi

    mov esi, Mem1
  mov edi, Mem2
  xor ecx, ecx

@@:
invoke DWordToString, [esi+ecx], edi
add edi, eax                   ; without this line
add edi, 1                      ; without this line
mov byte ptr [edi], 32
add edi, 1
  add ecx, 4
  cmp ecx, memsz
  jb @B
  sub edi, 1
  mov byte ptr [edi], 0

pop edi
pop esi

[Thomas_1110]

Sorry, I wasted your time with a false information. I edited the code for public here and I did it wrong.
So here i attach the two version as .exe and .asm. See the time difference.
Change between the two versions: line 111, 112

Code Select Expand


add edi, 1
mov byte ptr [edi], 32


Best regards, Thomas

[dedndave]

the version with the two lines runs fine

the version with the two lines commented out takes a while and all the numbers are run together
you have the symptoms reversed ?

i would still push and pop esi/edi

[Thomas_1110]

The " " is only a seperator. First I had a ", " as seperator. Then I tried to make my code faster.  With comma and without the space it was slower.
I hoped the profi programer have an answer for me. ::)
Ok, i will try to separate the symptom and write here my experience.
Big Thanks and best regards, Thomas

[raymond]

you mean the "Sieve of Eratosthenes" ?

Yes. In case you may not yet be familiar with that, you can find an example at:
http://mathworld.wolfram.com/SieveofEratosthenes.html

However, even that example can be improved speedwise quite significantly by:
- starting the "cross-out" only at the square of the prime (all multiples of the prime with lower primes have already been crossed-out;
- cross-out only odd multiples of the prime.

The "half-sieve" is even faster since you don't have to cross-out every second number. That sieve would be for odd numbers only.

[dedndave]

i like that site, Ray   :U

[raymond]

There's a tremendous amount of math knowledge on that site. There's an answer to almost any question.

[Eddy]

JFYI. The sieve of Eratosthenes is simple and fast for generating small primes.
For generating larger primes (hundreds or thousands of digits), Eratosthenes requires too much memory space and becomes too slow.
In that case, one usually uses probabilistic tests.
You generate a (random) odd number and then test whether it is prime or not. If not, you generate a new prime candidate and test again.
Now, probabilistic is the key word here. This means that, if the prime test function returns false ('not prime'), you can be sure that the number is not a prime. If the prime test function returns true, it is very well possible, but not 100% sure that the tested number is a prime. The more tests you perform (using different parameters for the prime test function) the higher the reliability that the result is correct if the function returns true.

The most well known prime test functions are: "Fermats little theorem" and the "Rabin-Miller prime test".

Interesting to know: There are a class of large integer numbers called Carmichael numbers. These numbers are not prime, but Fermat's test can not determine that they are not prime. Rabin-Miller can..

If you would like to play a bit with (very) large prime numbers, you can download my HIME library (www.devotechs.com) and run the HIMEWorkbench.exe demo program.
That has Fermat, Rabin-Miller and a few other prime number tests.

Kind regards