home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / basic / compiler / ubasic / malm / sformf.ub < prev    next >
Encoding:
Text File  |  1990-08-22  |  1.4 KB  |  33 lines
  1.    10   *Sformf(N,&F)
  2.    20   ' Shanks square form factorization of N.  F is a factor.
  3.    30   ' Version which uses the 2nd cntnd fraction & rejects small denom.
  4.    40   ' 7 May 1990.
  5.    50   dim Squf(80) ' Holds small denominators.
  6.    60   local P,Q,Pp=0,Qq=1,Qqq=N,Te,A,R=0,K,I=0,J=0,Ub,Jj,Ii=0,Ta,Iii,Flag
  7.    70   local Npp,Nqq,Na,Nr,Nqqq,Np,Nq
  8.    80   K=isqrt(N):if not res then F=K:return endif:A=K:Ub=2*sqrt(2*sqrt(N))
  9.    90   Squf(0)=1
  10.   100   ' Loop starts here.
  11.   110   inc Ii:if Ii>7000 then F=0:return endif
  12.   120   P=K-R:Q=Qqq+A*(Pp-P)
  13.   130   if Q<Ub then Iii=-1:Flag=1
  14.   140   :while and{Flag,(Iii<J)} inc Iii
  15.   150   :if Q=Squf(Iii) then Flag=0 endif wend
  16.   160   :if Flag then inc J:Squf(J)=Q endif endif
  17.   170   A=(P+K)\Q:R=res:inc I
  18.   180   Pp=P:Qqq=Qq:Qq=Q
  19.   190   Te=isqrt(Q):Ta=res
  20.   200   if or{odd(I),Ta<>0} then 110
  21.   210   if even(Te) then Te=Te\2 endif
  22.   220   Jj=0
  23.   230   while (Jj<=J):if Te=Squf(Jj) then 110 else inc Jj endif wend
  24.   240   ' Initialize for the second continued fraction
  25.   250   Npp=K-R:Nqq=isqrt(Q):Na=(Npp+K)\Nqq:Nr=res:Nqqq=(N-Npp*Npp)\Nqq
  26.   260   ' Loop begins
  27.   270   Np=K-Nr
  28.   280   if Np=Npp then 300 else Nq=Nqqq+Na*(Npp-Np):Na=(Np+K)\Nq:Nr=res
  29.   290   :Npp=Np:Nqqq=Nqq:Nqq=Nq:goto 270 endif
  30.   300   if even(Nqq) then F=Nqq\2 else F=Nqq endif
  31.   310   if or{F=1,F=N} then 110
  32.   320   return ' End of subroutine Sformf.
  33.