[Help] - Find Next Prime

[yq8]

Hey,

Today I was playing around with prime numbers in C++, and to get better into asm
i try to code every math algorithm i come accross in asm aswell to get a better understanding ;]
I looked a bit into jumps, i think i understood them better now.

The C++ Algorithm :

Code Select Expand

static int NextPrime(int a)
{
while (true)
{
a++;
if (a < 2) continue;
if (a == 2) break;
if (a % 2 == 0) continue;
bool flag = false;
for (int i = 3; (i*i) <= a; i += 2)
{
if (a % i == 0)
{
flag = true;
break;
}
}
if (!flag)
break;
}
return a;
}
This is my C++ algorithm, - a bit more complex, yes.
Its trying to find the next larger prime number which is the closest to my input.

e.g.

Input is 12 -> output is 13
Input is 17 -> output is 19
Input is 19 -> output is 23
Input is 84 -> output is 89

etc etc

I know there are many way to find the next prime number,  but I really like to do it the same way the c++ code does it, because
it is very efficient and fast.
So I like to perform every check and every operation like my C++ algorithm does, but in asm.
Tho, I really had problems when so much stuff was at the same time.. :

Code Select Expand

for (int i = 3; (i*i) <= a; i += 2)
{
if (a % i == 0)
{
flag = true;
break;
}
}
No idea how to do this one.
Tho, I attempt to code as much as I know already in asm.
This is what I've come up with so far:

Code Select Expand

static int NextPrimeASM(int a)
{
__asm
{
// create while loop somehow arround everything?


// if (a < 2) continue, - mov a into eax;
mov eax, a
mov ecx, 0
cmp eax, ecx
jg JUMP1
mov eax, 0
jmp JUMP2
JUMP1 :
mov eax, a
JUMP2 :

// if (a == 2) continue, - mov a into eax;
cmp eax, 2
je JUMP3
jmp JUMP4
JUMP3:
mov eax, a
JUMP4:

// Calculate modulo
// if (a % 2 == 0) return 1;
// if (a % 2 != 0) return 0;
mov eax, a
xor edx, edx
mov ebx, 2
div ebx
cmp edx, 0
je JUMPISZERO
mov eax, 0
jmp JUMPISNOTZERO
JUMPISZERO :
mov eax, 1
JUMPISNOTZERO :

//JUMPEND: // end of while, return result?
}
}

So:
1) Are those code fragments like the modulo and the greater and smaller checks correct so far?
2) No idea how to do the while loop and handle  the Incrementing (Inc) at the same time.
3) And with the inner for loop it was just to much at the same time, unsure how to handle all that.

Would be cool if you guys can give me advices again, post constructive critism on my code so I can improve my skills :)
Also, would be nice if someone can help me a bit with the complex inner part of the algorithm.
Am I on the right track so far?

Have a nice day ;)

[dedndave]

not sure how to read the C code - lol
the ASM code looks like it could be improved upon
give me a chance to wake up (coffee) and we'll take a look   :t

[FORTRANS]

Hi,

   While your modulo code looks correct, for modulo two it can be
simplified.  Modulo two is just a test for odd or even, the low bit
being set or zero.

Code Select Expand


        TEST    EAX,1
        JNZ     BitSet
        JZ      BitZero

   A while loop could test a value for true (non-zero usually) or
false, and then have a conditional jump to exit.  Quick knock-off
below.  The value could be held in a variable in memory or a register.

Code Select Expand


DB      WhileL  0FFH
...
        TEST    [WhileL],0FFH
        JZ      ExitWhile
...
; Want to exit.
        MOV     [WhileL],0

Cheers,

Steve N.

[rrr314159]

it is very efficient and fast.

- no, it's not. Well, if "efficient" means "short program in C" it is that. But for larger numbers it's much slower than a good algo. Really large numbers that can be done in a second would take a year with this approach!

If lucky I can find assembler code that does this task better, from 35 years ago. If not I can google a ref on how to do it (you should try that too, but it might not be so easy since you don't know the right buzzwords). But I'm not sure if you're interested, since it is a longer algo. Let me know.

[dedndave]

you probably need to do some reading, in regards to register usage and instruction operands
if you can keep most of the working variables in register, the code will be faster
so - learning efficient register usage is key to good code

and - understanding operand forms is also critical
for example...

Code Select Expand

mov eax, a
mov ecx, 0
cmp eax, ecx
can be performed as...

Code Select Expand

    mov     eax,a
    cmp     eax,0
we often use different instructions to set flags, when the immediate operand is 0

Code Select Expand

    or      eax,eax
or

Code Select Expand

    test    eax,eax
these will set the flags, according to the value in EAX
OR and TEST always clear the carry flag, so the normal JL / JG branches don't really work
but, you can branch on the sign or zero flags (JS / JNS or JZ / JNZ)

not sure how the C compiler handles high-level language constructs for ASM code
in MASM, we can use .if/.else/.elseif/.endif constructs

but, basic branching should be simplified, when practical

Code Select Expand

    compare/test instruction - the instruction that sets the flags
    conditional branch instruction - jump if "case is true" to some label
    code for "case not true" goes here

[dedndave]

something you may find helpful....

you can do a lot of reading about the different instructions
but, until you see them being used, it may not mean much

something you can do to speed up your learning curve is to examine code written by more experienced ASM programmers
look at their code - if you come across something that doesn't make sense, THEN you read about the instruction   :t

[yq8]

First, thanks for all replies.
I will try to improve from what I've learned now, and then post my progress here :)

it is very efficient and fast.

- no, it's not. Well, if "efficient" means "short program in C" it is that. But for larger numbers it's much slower than a good algo. Really large numbers that can be done in a second would take a year with this approach!

If lucky I can find assembler code that does this task better, from 35 years ago. If not I can google a ref on how to do it (you should try that too, but it might not be so easy since you don't know the right buzzwords). But I'm not sure if you're interested, since it is a longer algo. Let me know.

For me that algorithm was pretty fast for numbers ~8 digits long.
If the alto you talk about is called "PGsimple4", then my algo is faster.
Tho if you have a code which does this task, finding the next prime in asm, and really is a lot faster as you stated, it would be very interesting to see that :)

[rrr314159]

Turns out it's not as easy as I thought ... Now, I'm talking about large numbers, 30 digits and more. So first task is to show your approach will take a year (or, long time anyway) for sufficiently large worst-case. That takes some work. But the real problem, I can't find the appropriate fast algo on the web, or in my ancient notes. You can compute very high "next primes" very efficiently - somebody out there must be doing it. In fact I thought I'd find a reference which would discuss and compare your simple approach, show how slow it is at 30 digits or so. As the days go by I should be able to come up with a reference (got to be out there somewhere), when I find time to look into it ... Sorry for such a lackluster response. Keep at it, yq8, and congrats on having confidence in your algo

[jj2007]

http://primesieve.org/

primesieve is the fastest open source prime number generator! It generates primes at least 50 times faster (single-threaded) than an ordinary C/C++ sieve of Eratosthenes implementation and more than 10,000 times faster than trial‑division. Ben Buhrow's yafu contains another highly optimized sieve of Eratosthenes implementation but primesieve runs a little faster on most CPUs

Search the web for prime Eratosthenes Atkins.

There are also quite a number of threads here and in the old forum. Search for prime sieve to get them.

[rrr314159]

Hello jj2007,

It occurred to me you might respond to my plaintive post, you've come up with refs I missed b4, for instance that chebyshev ref. But in this case I'm still out of luck. A while ago I did get primesieve and it impressed me, 10 (or was it 100?) times faster than my best shot at the time. I could do better now, though. And, sieve of Atkins was not so impressive, mathematically yes, but implementation-wise enough extra work to be done that (AFAIK) not faster.

I didn't look on this (masm32) site, I'll give it a try, have you ever noticed that the search facility on masm site is lousy? I do much better with google, which easily reports anything relevant on masm32, than searching directly here.

Anyway - I was looking for algo to generate "next-primes" - starting at a given number. If you've never seen that, you'll be amazed (well, I was, anyway) how well it can do at very high numbers. Much faster than simply generating all the primes up to there - and, much faster than yq8's brute-force approach - altho I don't really have the right to say that while I can't prove it!

I don't think Chris Atkins' prog does that mode? Maybe I'm missing something obvious, like, many of these fast-algos do that trick but don't mention it on the first page, have to download it to find out.

If you see anything let me know! Thanks for helpful response, c u later!

[jj2007]

I'm not a mathematician (and will never be one), so I just have to believe what the Internet says. For example:

Different algorithms get used based on how large the number is. It goes something like this:
Small Numbers : Use simple sieve algorithms to create list of primes and do plain factorization. Works blazingly fast for small numbers.
Big Numbers : Use Pollard's rho algorithm
Less Than 10^{25} : Use Lenstra elliptic curve factorization
Less Than 10^{100} : Use Quadratic sieve
More Than 10^{100} : Use General number field sieve
Currently, in the very large integer factorization arena, GNFS is the leader.

[rrr314159]

That's factorization, related but different. Factorizing has, of course, attracted a lot of attention since RSA algorithm (which one of those old guys - Euler? Gauss? foresaw). Fermat's Quadratic sieve was still the best until a few decades ago, now GNFS improves on it for very large numbers. You know, if Gauss had actually been confronted with the need to consider hundreds-of-digits numbers, he would have come up with GNFS in a day or two. Fermat - probably not; Euler - would have come up with something totally different and unexpected, maybe faster, maybe not; but it would have given wrong answers now and then. Then he would have written a few more papers, and taken a break for lunch.

Anyway, it's a different problem. We (xq8, and now me) want an algo to generate the next prime after a given number. The algo I remember generates a whole block of primes; the way it works, it can do that as easily as generating only the next one. The fact that it's not on the net makes me wonder if I'm misremembering ...

BTW jj2007, I bet you'd love math if you gave yourself the chance