(c)Svin.




.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.
Posted on 2001-12-24 08:35:47 by The Svin
if you are interested, i' ll release an asm bignum library soon. it will be a bit slow, but well =)
Posted on 2001-12-24 10:24:40 by roy
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 ?
Posted on 2001-12-24 12:05:42 by eko
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 :)
Posted on 2001-12-24 12:53:33 by The Svin
nice i liked IT keep bring us your wisdom

:alright:
bye
eko
Posted on 2001-12-24 13:16:53 by 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
Posted on 2001-12-25 08:14:46 by 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).
Posted on 2001-12-26 23:22:58 by The Svin
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
Posted on 2001-12-28 10:51:29 by Anunitu
Thanks, Anunitu.
I should stress that main problem is math terms.
Since in math terms explicity is the main base of notations.
Posted on 2002-01-13 23:08:22 by The Svin