View difference between Paste ID: HRs8YtLi and NXAYTLXV

 from itertools import* #reikalinga funkcijai starmap
 #SKAICIU TEORIJA
 def primes(n, sieve=[False,False,True]): #by-need calculation of primes; not includes n
     #TEST1
     #sieve:          [1,1,1,1,1,1,1,1,1,1]=[1]*10
     #possible primes [0,1,2,3,4,5,6,7,8,9]
     #given sieve     [0,0,1,1,0]
     #a=3
     #check from 0 to sqrt(len(sieve))
     #last five entries were checked dividing by primes 0 to a=3
     #sieve is given as list of bools to save memory
     #TEST2
     #primes(20) returns [2, 3, 5, 7, 11, 13, 17, 19], sieve is [False, False, True]
     #after that primes(30) returns [2, 3, 5, 7, 11, 13, 17, 19, 23, 29], taken sieve is list of bools with len=20
     #print sieve - get a primary sieve
     if len(sieve)<n:
         a=len(sieve)
         sieve+=[True]*(n-a)
         i=1
         while i<=int((n-1)**0.5):
             i+=1
             if sieve[i]:
                 for j in range(max(2*i, a+(i-a)%i),n,i): sieve[j]=False
     return [i for i in range(n) if sieve[i]]
 from time import*
 def factor(num):
     product=[]
     t=time()
     if num==0: return 0
     if num<0: return None
     for n in primes(int(num**0.5)+1):
         while num%n==0:
             if time()-t>2: break
             product.append(n)
             num/=n
         if num==1: break
     if num<>1: return product+[num]
     return product
 def divisors(num):
     if num<1: return None
     def multiply(array):
         k=1
         for n in array: k*=n
         return k
     M=tuple(factor(num))
     return list(map(lambda x: multiply(x), product(*[[n**i for i in range(M.count(n)+1)] for n in set(M)])))
 #POLINOMU OPERACIJOS, kur a+bx+cx^2+...=[a,b,c...]
-def interpolation(ordered_pairs):
+def divide(P1,P2):
-    n=len(ordered_pairs)
+    residue=[]
-    return solve_system([[m[0]**i for i in range(n)]+[m[1]] for m in ordered_pairs])
+    Pol=[n for n in P1]
     if len(P2)<2: return
     from time import*
     t=time()
     while len(P2)<=len(Pol):
         if time()-t>2:
             break
             print 'Serious error in polynomial division'
         coef=Pol[0]/float(P2[0])
         residue.append(coef)
         del(Pol[0])
         for i in range(len(P2)-1):
             Pol[i]-=coef*P2[i+1]
     if Pol==[0]: return residue
 def roots(P):
     #mains bugs: finds just integral roots - need quotients (use substitution of polynomial variable to count this)
     #need general algorhytm for quadratic and cubic polynomials
     #possible liar result if roots not integral - abs(P[0]/P[-1]) is not always exact number
     if len(P)<2: return []
     guess=divisors(abs(P[0]/P[-1]))
     guess+=[-n for n in guess]
     p=True
     for test in guess:
         M=divide(P,[-test,1])
         if M<>None:
             p=False
             return [test]+roots(M)
     if p==True: return []
 #MATRICU OPERACIJOS
 def div(a,b): #norim, kad nebutu stufo, tokio kaip 0.0, o butu vietoj to sveikieji
         if float(a)/b==a/b: return a/b
         return float(a)/b
 def gcd(*args): #rasime skaiciu DBD
         def gcd_of_two(a,b):
             a,b=abs(a),abs(b)
             while a>0:
                 if b>a: a,b=b,a
                 if a==1: return 1
                 a-=(a/b)*b
             return b
         return reduce(lambda x,y: gcd_of_two(x,y), args)
 def T(matrix): return zip(*matrix) #transponuota matrica
 def mul(*args):
     def simple_mul(matrix_a, matrix_b):#matricu daugyba
         if len(matrix_a[0])==len(matrix_b): return map(lambda x: tuple(sum(starmap(lambda j,k: k*j, zip(x,n))) for n in zip(*matrix_b)),matrix_a)
     return reduce(lambda x,y: simple_mul(x,y), args)
 def add(matrix_a, matrix_b, m1=1, m2=1):
     #sudetis m1*matrix_a+m2*matrix_b
     return [tuple(m1*matrix_a[i][j]+m2*matrix_b[i][j] for j in range(len(matrix_a[0]))) for i in range(len(matrix_a))]
 def scalmul(matrix,const): return [tuple(matrix[i][j]*const for j in range(len(matrix[0]))) for i in range(len(matrix))] #matrica dauginta is skaliaro
 def unit(length, diagonal=[]):
     if diagonal==[]: diagonal=[1]*length
     return [tuple(int(i==j)*diagonal[i] for i in range(length)) for j in range(length)] #vienetine matrica
 def inverse(matrix): #atvirkstines matricos algoritmas
     #EXAMPLE: [[a1,a2,x1,x2],[b1,b2,y1,y2]] ->[[a3,a4,a5,a6],[x3,x4,x5,x6]], nes tai ekvivalentu zingsniui
     # /a1 a2\|/1 0 x1 x2\  _______\     /1 0\|/a3 a4 a5 a6\
     # \b1 b2/|\0 1 y1 y2/         /     \0 1/|\x3 x4 x5 x6/
     #rows can be longer than len of matrix; that case last terms means solutions to several systems of equations
     M=[[m for m in n] for n in matrix] #SIDE EFFECTS ARE ELIMINATED IN THIS ROW
     U=unit(len(M))
     order=[(i,j) for i in range(len(M)-1) for j in range(i+1,len(M))]+[(i,j) for i in range(len(M)-1,0,-1) for j in range(i-1,-1,-1)]
     #eiluciu keitimo tvarka, kai reikia suvesti i trikampi, po to i diagolini pavidala
     for i in range(len(M)):
         U[i]=U[i]+tuple(M[i][len(matrix):len(M[0])])
     #eiluciu sudejimo eiliskumas
     try:
         for n in order:
             i,j=n[0],n[1]
             if M[i][i]==0: # jei pasitaike nulinis elementas ant istrizaines, keiciame matricos eilutes. Jei neradome, ka sukeisti - nera atvirkstines matricos
                 p=0
                 for k in range(i+1,len(M)):
                     if M[k][i]<>0:
                         M[i],M[k]=M[k],M[i]
                         U[i],U[k]=U[k],U[i]
                         p=1
                         break
                 if p==0: return [M[i] for i in range(len(M)) if M[i][i]<>0] #bug we'll use later
             if M[j][i]<>0: #suvedimo i trikampi pavidala vienas zingsnis, kai uznulinama kazkuri eilute
                 c=M[i][i]*M[j][i]/gcd(M[i][i], M[j][i])
                 c1,c2=c/M[i][i],c/M[j][i]
                 M[j]=tuple(map(lambda x: x[1]*c1-x[0]*c2, zip(M[j],M[i])))
                 U[j]=tuple(map(lambda x: x[1]*c1-x[0]*c2, zip(U[j],U[i])))
         return map(lambda i: tuple(map(lambda x: div(x, M[i][i]),U[i])), range(len(U)))
     except IndexError: print 'Nesiskaiciuoja inverse, per daug eiluciu matricoje'
     #pradine matrica pasikeite i matrica su skaiciais ant istrizaines; jos istrizaine normalizavus, graziname U reiksme
 def rank(M): #gudras metodas, kur klaidos atveju inverse funkcijoje grazinamas tiesiskai nepriklausomu eiluciu matrica
     if len(M)>len(M[0]): return len(inverse(T(M))) #transponuojam, nes inverse taikosi tik siuo atveju
     else: return len(inverse(M))
 def det(matrix): #determinanto algoritmas - padaryta pagal inverse funkcija
     D=[]
     M=[[m for m in n] for n in matrix]
     order=[(i,j) for i in range(len(M)-1) for j in range(i+1,len(M))]
     for n in order:
         i,j=n[0],n[1]
         if M[i][i]==0: # jei pasitaike nulinis elememtas ant istrizaines, keiciame matricos eilutes. Jei neradome, ka sukeisti - det=0
             p=0
             for k in range(i+1,len(M)):
                 if M[k][i]<>0:
                     M[i],M[k]=M[k],M[i]
                     p=1
                     break
             if p==0: return 0
         if M[j][i]<>0: #suvedimo i trikampi pavidala vienas zingsnis, kai uznulinama kazkuri eilute
             c=M[i][i]*M[j][i]/gcd(M[i][i], M[j][i])
             c1,c2=c/M[i][i],c/M[j][i]
             D.append(-c2)
             M[j]=tuple(map(lambda x: x[1]*c1-x[0]*c2, zip(M[j],M[i])))
     if D<>[]: D=reduce(lambda x,y:x*y,D)
     else: D=1
     return reduce(lambda x,y: x*y, map(lambda i: M[i][i], range(len(M))))/D
 def solve_system(matrix): return [list(n) for n in zip(*inverse(matrix))[len(matrix):]]
 def orthoappend(*args):
     #kas zingsni sprendziama sistema, kur like nezinomieji(kuriu kiekis yra defect) prilyginti 1
     M=[list(n) for n in list(args)]
     defect=len(args[0])-len(M)
     while defect>0:
         N=[M[i][:-defect]+[-sum(M[i][-defect:])] for i in range(len(M))]
         M+=[list(solve_system(N)[0])+[1]*defect]
         defect-=1
     return M
 def chr_pol(M): #charakteristinis daugianaris, rastas aprepianciuju minoru pagalba
     def minors(M,k):
         L=len(M)
         #first row is elements of matrix with connection of order=[(M[n],M[n]) for n in second_row]
         #second_row says cyclic permutations with len=k of the sequence with len=L
         return [[[M[i][j] for j in n] for i in n] for n in [[x%L for x in range(i,i+k)] for i in range(L)]]
     return [sum([det(n) for n in minors(M,k)])*(-1)**k for k in range(len(M),0,-1)]+[1]
 def eigenvalues(M): return roots(chr_pol(M))