(c)Svin.

Alex, I set the code formatting options so that the source is easier to read.

```
```

.586

.model flat,stdcall

option casemap:none

include C:\masm32\include\windows.inc

include C:\masm32\include\kernel32.inc

include C:\masm32\include\user32.inc

includelib kernel32.lib

includelib user32.lib

FermaAlgo proto :DWORD

.code

start:

invoke FermaAlgo,123456789

call ExitProcess

;Algoritm Fermat (optimized by the Svin) to find 2 close dividers

;In: Odd natural number.

;Out: Multipliers of number N or message that N is prime.

;Step1: Put x = [sqrt(n)], if x^2 = n, then x is divider of n

;and the algo stops. In other case increase X by 1

;and go to step 2

;Step2: If x = (n+1)/2, then n is prome, and algo stops ;

;in other case calculate y = sqrt(x^2 - n)

;???3: If y is natural (e.i. [y]^2 = x^2 - n), then n can be represented by

;(x+y)(x-y), and algo stops; in other case goto step 2

FermaAlgo proc num

LOCAL sqrt:DWORD

;Stage1: Check if input is correct.

;Check case 0,1 ?nd 2,3

cmp num,4

mov eax,num

jnc @F

jmp [eax*4][offset jmptbl] ;handling1,2,3,0

@@: test eax,1

je @even

;Stage 2 - init of var and check for a full sqare

;Step2 compares ? against the same value (n+1)/2

so we calculate it and give it a personal reg

;edi = (n+1)/2

;x always is changed by 1 and also can be used to calculate near sq

;so we'll give it a "personal" reg too.

;esi = x

;and X^2-n cause X^2 progressing uninterruped ?nd n is constant for speed we do

;ecx = X^2 - n

;difference between (X^2-n) and (X+1)^2 - n the same as X^2 and (X+1)^2 and equal

;2X +1 'cause (X+1)^2 = X^2+2X+1

;Get first value of X = sqrt(n)

.data?

cr dw ?

.code

fstcw cr

or cr,0000010000000000b ;round to -

fldcw cr

fild num

fsqrt

fistp sqrt

mov esi,sqrt ;init X

mov eax,sqrt ;X -> eax

mul eax ;eax ^ 2

cmp eax,num ;full sq?

je @fullsq

mov edi,num

lea ecx,[eax][esi*2][1] ;ecx = (X+1)^2

sub ecx,edi ;ecx = (X+1)^2 - n

inc edi

shr edi,1 ;edi = (n+1)/2

mov sqrt,esi

jmp init

@again:

mov sqrt,ecx

fild sqrt

fsqrt

fistp sqrt ;sqrt = sqrt(x^2-n)

mov eax,sqrt

lea edx,[ecx][eax] ;check for odd\even

test edx,1 ;if sum isn't even than sq isn;t natural for sure

jne @odd ;

mul eax ;and yet in ~ 50% not full sq "will pass" the test

cmp eax,ecx ;for this cases we'll do aditional test

je @found

@odd:

lea ecx,[ecx][esi*2][1]

init:

inc esi

cmp esi,edi

jne @again

Prime:

.data

jmptbl dd @case0,@case1,@Prime,@Prime

MsgPrime db 'It's prime number - ',13,10

db 'It can be divided only by itself and 1',0

.data

TtlMsgPrime db "Prime",0

.code

@Prime:

invoke MessageBox,0,offset MsgPrime,offset TtlMsgPrime,0

ret

@case0:

.data

MsgZero db 'Number = 0. It's senceless to divide it',0

.code

invoke MessageBox,0,offset MsgZero,0,0

ret

@case1:

.data

Msg1 db "Number = 1. It can be divided only by itself",0

.code

invoke MessageBox,0,offset Msg1,0,0

ret

@even:

.data

MsgEven db "Number is even",0

.code

invoke MessageBox,0,offset MsgEven,0,0

ret

@fullsq:

mov eax,esi

mov edx,esi

jmp @out

@found:

mov eax,esi ;eax = X

mov edx,sqrt ;edx = Y

sub eax,edx ;a = X-Y

lea edx,[esi][edx] ;b = X+Y

@out:

.data

tmpl db Multiplyers of %i',13,10

db '%i,%i',13,10

db 13,10,0

MsgFound db 'Multiplyers are found',0

.data?

buffer db 64 dup (?)

.code

invoke wsprintf,offset buffer,offset tmpl,num,eax,edx

invoke MessageBox,0,offset buffer,offset MsgFound,0

ret

FermaAlgo endp

ret

end start

Alex, I set the code formatting options so that the source is easier to read.

if you are interested, i' ll release an asm bignum library soon. it will be a bit slow, but well =)

hiiii

wow very very nice algorithm but i think i didnt understand the step2

x = (n+1)/2 ? if this equal why n is prime ?

and a stupid question this is the same fermat who invented the problem X^n+Y^n=Z^n (n>2), right ?

wow very very nice algorithm but i think i didnt understand the step2

x = (n+1)/2 ? if this equal why n is prime ?

and a stupid question this is the same fermat who invented the problem X^n+Y^n=Z^n (n>2), right ?

What we try is to represent an odd number as difference of two sq

X^2-Y^2.

We can represent to multipliers of n as n=a*b and a > b

and we can represent difference of two sq as (X+Y)*(X-Y)

so we can assume that a = (X+Y) and b = (X-Y)

Now what is Fermat algo about.

It tries to find closest multipliers. So through whole algo it increasing a and decrising b

Now what is the least possible value of b? It's 1.

And this means that if we get down to this value that the only possible multiplyers is N*1

Now what does it mean b = 1 in context of (X+Y)(X-Y) that means that X-Y=1

and that means X^2-Y^2 = 2X-1 or 2Y+1 'cause (X+1)^2=X^2+2X+1 and X^2+2X+1-X2=2X+1

in our case 'case X-Y=1 X will serve as (X+1) and Y as X for the above.

if b = 1 than a = n that means if (X-Y)=1 then n = 2X-1; 2X=n+1 ;X=(N+1)/2

I can try to write more detail proof for the algo.

The only problem is my English - I'm trapped each time I get to math terms in English.

Yes, it is the same Fermat. But a little bit + me :)

X^2-Y^2.

We can represent to multipliers of n as n=a*b and a > b

and we can represent difference of two sq as (X+Y)*(X-Y)

so we can assume that a = (X+Y) and b = (X-Y)

Now what is Fermat algo about.

It tries to find closest multipliers. So through whole algo it increasing a and decrising b

Now what is the least possible value of b? It's 1.

And this means that if we get down to this value that the only possible multiplyers is N*1

Now what does it mean b = 1 in context of (X+Y)(X-Y) that means that X-Y=1

and that means X^2-Y^2 = 2X-1 or 2Y+1 'cause (X+1)^2=X^2+2X+1 and X^2+2X+1-X2=2X+1

in our case 'case X-Y=1 X will serve as (X+1) and Y as X for the above.

if b = 1 than a = n that means if (X-Y)=1 then n = 2X-1; 2X=n+1 ;X=(N+1)/2

I can try to write more detail proof for the algo.

The only problem is my English - I'm trapped each time I get to math terms in English.

Yes, it is the same Fermat. But a little bit + me :)

nice i liked IT keep bring us your wisdom

:alright:

bye

eko

:alright:

bye

eko

hi think there is abug . its not exacly a bug but

try to put in the aglo 10!+1 =3628801

you will get 223047,211831 = 4291338495 this happend becuase the unsign,the algo think that the number 375F01h is actully FFC8A0FF

bye

eko

try to put in the aglo 10!+1 =3628801

you will get 223047,211831 = 4291338495 this happend becuase the unsign,the algo think that the number 375F01h is actully FFC8A0FF

bye

eko

I see... Thanks.

I think in this version it can be easily solved with changing the

num to qword, in the case it we not be treated as signed long

32 bit by fpu. The rest of the algo will work just with low dword of

the qword but loading to fpu as qword (with zero in the high dword).

I think in this version it can be easily solved with changing the

num to qword, in the case it we not be treated as signed long

32 bit by fpu. The rest of the algo will work just with low dword of

the qword but loading to fpu as qword (with zero in the high dword).

I am a native english speaker from the US, and I know people HERE that don't speak their OWN language as well as you do Svin. A friend in Hollend, also makes apoligies in her E-mails for her english, She speaks German, Dutch, and probubly a few others. I understand her E-mails JUST fine, but I speak and write ONLY English, not being gifted at languages, I seem to be the one being apoligized to for MY lack! So Svin, when you think it is YOU who has a problem getting your point across, perhaps what is really the point, is I lack the versatility to Learn your language, AND you make an effort to learn mine. Who, in the sceme of things has gained. I in an effort to understand, learn your gift for Math, and Garner a little bit of phraseology of your language, who knows, perhaps in time, I will LEARN your language.

Anunitu

Anunitu

Thanks, Anunitu.

I should stress that main problem is math terms.

Since in math terms explicity is the main base of notations.

I should stress that main problem is math terms.

Since in math terms explicity is the main base of notations.