Optimizing Loops 1

[0x4B47]

Hi forum,
I wrote a procedure in MASM 6.15 which takes a 32-bit unsigned int from the user and tells the user whether it is a prime number or not. Now the program loop works fine with small numbers (obviously) but with larger numbers the program takes anything up to 5-10 secs to calculate whether its prime or not!! Plz take some time to look at the code and advise me how I may possibly optimize the loop to run faster.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

CheckIfPrime proc uses eax ecx edx
cmp input, 0
je Finish                   ; Finish is global label inside main
mov ebx, input              ; input is global mem var, stores user 'input'
mov ecx, input
CheckPrime:
	mov eax, input         ;move input into eax
	dec ebx                ;decrement ebx
	cmp ebx, 1             ;is ebx = 1?
	je IsPrime             ;if so, number 2 is prime
	cmp ebx, 0             ;is ebx = 0?
	je NotPrime            ;if so, number 1 is not prime
	mov edx, 0             ;clear edx
	div ebx                ;divide eax by ebx
	cmp edx, 0             ;is the remainder of the division 0
	je NotPrime            ;if so, number is not prime
Loop CheckPrime
NotPrime:
                            ;Display msg indicating num NOT prime
IsPrime:
                            ;Display msg indicating num IS prime
ret
CheckIfPrime endp

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
Thank you
KG.

 

[lionelhill]

There are several minor changes you could make, but I feel you're going about this algoritmically in the wrong direction. (see point 3 below)

What you are doing is dividing your number by every number that is less than it, and if you reach the bottom without hitting a "no remainder", you rightly identify your number as prime.

However, you really only need to divide the number by prime numbers, because if the number won't divide by 2, then it won't divide by 4 either.

This suggests several advances you could do:

(1) very simply, divide your number by 2, then 3 and upwards jumping in twos. Because having checked 2, you know you don't need to divide by 4, 6, 8 etc....

(2) perhaps it would be worth implementing a mini-demosthenes-type sieve. This is going to be problematic for a full 32-bit number, and there are diminishing returns. So what I'd try is something like this:
Maintain a set of counters in pairs (1A, 1B, 2A, 2B, 3A, 3B) - perhaps 5 or so pairs. In each pair, counterA contains a (precalculated) prime above 2. Counter B just counts.
On each loop, add 2 to counters B. If a number overshoots its counter A, subtract the value in A from that in B. If you get through all 5 pairs like this without any landing exactly on A=B, then you have a potential prime by which you should divide the test-number.
In effect, what you are doing is discounting every 2nd, 3rd, 5th, 7th, 9th or 11th number, which means you have to do a lot fewer divisions.

For a single number-test, I wouldn't be surprised if you had little gain going beyond a handful of prime numbers, because each successive prime saves a division more rarely, and you are still having to step in (at best) 2's through all numbers. But as the primes mount up, the work in adding to counters mounts up, and it will quickly be as much work as a single division.

I'm guessing the extra memory references won't mess this up too badly. If they do, then I think you'd have enough registers to handle counting by 2's and 3's, which still cuts your divisions by a factor of 6

(3) The other obvious thing is that if your number n does not divide by 2, then it won't divide by anything above n/2, either.
Similarly if it doesn't divide by 3, you needn't check above n/3.
So each time you do the division, reduce your target to the result of the division!!!!
This will make a BIG improvement.

[PS I spent only 5 min thinking about this, so I'm sure there are much better solutions out there if someone actually knows or has a better head on the case than mine]