ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Sashka Yackubtchick                  2:5054/29.54   01 Dec 2001  04:49:04
 To : All
 Subject : Алгоритм Ферма нахождения делителей
 -------------------------------------------------------------------------------- 
 

 
 Черновой вариант сабжа.
 Мысли, код, мнения как всегда мною приветсвуются
 и внимательно изучаются.
 
 === Cut ===
 .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,127*139
  call ExitProcess
 ;Алгоритм Ферма по нахождению близко расположеных делителей числа:
 ;Ввод: Hечётное натуральное число.
 ;Вывод: Множетели числа N или сообщение о том, что N простое.
 ;Шаг1: Положить x = [sqrt(n)], если x^2 = n, то x является делителем числа n
 ;и работа алгоритма останавливается. В противном случае увеличить X на 1
 ;и перейти к шагу 2
 ;Шаг2: Если x = (n+1)/2, то число n простое, и работа алгоритма
 ;останавливается;
 ;в противном случае вычислить y = sqrt(x^2 - n)
 ;Шаг3: Если число y целое (т.е. [y]^2 = x^2 - n), то n раскладывается в
 ;произведение
 ;(x+y)(x-y), и работа алгоритма останавливается; в противном случае перейти к
 ;шагу 2
 FermaAlgo proc num
 LOCAL sqrt:DWORD
 ;Стадия 1: Проверка корректности ввода.
 ;Проверим сразу случаи 0,1 а "заодно" и 2,3
  cmp num,4
  mov eax,num
  jnc @F
  jmp [eax*4][offset jmptbl] ;на обработку случаев 1,2,3,0
 @@: test eax,1
  je @even
 ;Стадия 2 - инициализация переменных и проверка на полный квадрат
 ;Шаг2 сравнивает число Х с одной и той же величиной (n+1)/2
 ;расчитать её нужно перед началом цикла и положить в неизменяемый регистр
 ;edi = (n+1)/2
 ;x всегда изменяется на 1 и так же может применятся при вычислении "соседнего"
 квадрата
 ;дадим ему также "персональный" регистр
 ;esi = x
 ;и X^2-n поскольку X^2 увеличивается равномерно а n постоянна то для скорости
 ;ecx = X^2 - n
 ;разница между (X^2-n) и (X+1)^2 - n составляет разницу между X^2 и (X+1)^2 а
 эта разница
 ;равна 2X +1 поскольку (X+1)^2 = X^2+2X+1
 ;Вычислим начальное значение X = sqrt(n)
 .data?
 cr dw ?
 .code
  fstcw cr
  or cr,0000010000000000b ;Округляем в меньшую сторону.
  fldcw cr
  fild num
  fsqrt
  fistp sqrt
  mov esi,sqrt ;инициализируем X
  mov eax,sqrt ;X -> eax
  mul eax       ;eax ^ 2
  cmp eax,num ;полный квадрат?
  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]   ;проверка на расхождение чётности\нечётности
  test edx,1 ;числа и корня если сумма нечётная то корень явно не целый
  jne @odd ;
  mul eax  ;тем не менее ~ 50% нецелых корней "пройдёт" этот тест
  cmp eax,ecx ;для этих случаев дополнительная проверка.
  je @found
 @odd:
  lea ecx,[ecx][esi*2][1]
 
 init:
  inc esi
  cmp esi,edi
 
  jne @again
 .data
 jmptbl dd @case0,@case1,@Prime,@Prime
 MsgPrime db 'Это простое число - ',13,10
  db 'Оно делится только на единицу и на себя',0
 TtlMsgPrime db "Простое число",0
 .code
 @Prime:
  invoke MessageBox,0,offset MsgPrime,offset TtlMsgPrime,0
  ret
 @case0:
 .data
 MsgZero  db 'Число = 0. Делить его бесмыслено',0
 .code
  invoke MessageBox,0,offset MsgZero,0,0
  ret
 @case1:
 .data
 Msg1 db "Число = 1. Единица делится только сама на себя",0
 .code
  invoke MessageBox,0,offset Msg1,0,0
  ret
 @even:
 .data
 MsgEven db "Число чётное",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 'Множители числа %i',13,10
  db '%i,%i',13,10
  db 13,10,0
 MsgFound  db 'Число разложено на множетели',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
 === Cut ===
 
 Пока!
              Sashka, The Svin.
 
 --- GoldED/W32 3.00.Beta1+
  * Origin: Svin, Perm, Russia  (2:5054/29.54)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор