我们从Python开源项目中，提取了以下50个代码示例，用于说明如何使用fractions.gcd()。
def __init__(self, jobs): """ Create a new Scheduler. >>> s = Scheduler([Job(1, max, 100, 200)]) >>> for jobs in s: ... time.sleep(s.tick_duration) :param jobs: Sequence of jobs to schedule """ periodicities = {job.periodicity for job in jobs} self.tick_duration = reduce(lambda x, y: fractions.gcd(x, y), periodicities) self._ticks = self.find_minimum_ticks_required(self.tick_duration, periodicities) self._jobs = jobs self._current_tick = 0 logger.debug('Scheduler has {} ticks, each one is {} seconds'. format(self._ticks, self.tick_duration))
def __new__(cls, name, bases, attrs): # A list of all functions which is marked as 'is_cronjob=True' cron_jobs = [] # The min_tick is the greatest common divisor(GCD) of the interval of cronjobs # this value would be queried by scheduler when the project initial loaded. # Scheudler may only send _on_cronjob task every min_tick seconds. It can reduce # the number of tasks sent from scheduler. min_tick = 0 for each in attrs.values(): if inspect.isfunction(each) and getattr(each, 'is_cronjob', False): cron_jobs.append(each) min_tick = fractions.gcd(min_tick, each.tick) newcls = type.__new__(cls, name, bases, attrs) newcls._cron_jobs = cron_jobs newcls._min_tick = min_tick return newcls
def __init__(self, lattice, m, n): self.lattice = lattice self.m = m self.n = n # Chiral vector self.c = lattice.pos(m,n) self.magC = mag(self.c) # Translation vector d = gcd(2*n+m,2*m+n) self.t = lattice.pos((2*n+m)/d, -(2*m+n)/d); self.magT = mag(self.t) # Chiral rotation matrix (rotate a1 along x-axis) self.theta = acos(norm(self.c)[0]*copysign(1, self.c[1])) self.rotM = np.array([ [cos(self.theta), sin(self.theta)], [-sin(self.theta), cos(self.theta)]]).T # Calculate atoms and bonds in unit cell self._boundsErr = mag(lattice.pos(0,0,0) - lattice.pos(0,0,1)) self.indices = self._calcIndices(m, n) self.atoms = self._calcAtoms(self.indices) self.bonds = self._calcBonds(self.indices)
def lissajous(a, b, d): # request a,b integers, so we have closed, periodic curves n = gcd(a,b) N = (a/n) * (b/n) # number of periods before looping # error test input if N > 1e4: # non-integer (a,b) or otherwise too irregular raise Exception('Non-periodic', 'a,b must be integers (of moderate size)') # compute a set of interpolation points numb_pts = max(3*N, 100) # using 3N interpolation points is decent enough t = np.linspace(0,2*pi/n, numb_pts) x = np.array([np.sin(a*t + d), np.sin(b*t)]) # do a cubic curve interpolation with periodic boundary conditions return curves.cubic_curve(x.T, curves.Boundary.PERIODIC) ### main program ### # create the curve # crv = lissajous(60, 44, pi/2);
def brent(N): # brent returns a divisor not guaranteed to be prime, returns n if n prime if N%2==0: return 2 y,c,m = randint(1, N-1),randint(1, N-1),randint(1, N-1) g,r,q = 1,1,1 while g==1: x = y for i in range(r): y = ((y*y)%N+c)%N k = 0 while (k<r and g==1): ys = y for i in range(min(m,r-k)): y = ((y*y)%N+c)%N q = q*(abs(x-y))%N g = gcd(q,N) k = k + m r = r*2 if g==N: while True: ys = ((ys*ys)%N+c)%N g = gcd(abs(x-ys),N) if g>1: break return g
def smallPrimes(self,n="n",upperlimit=1000000): if(n=="n"): n = self.modulus from sympy import sieve for i in sieve.primerange(1,upperlimit): if(n % i == 0): self.p = i self.q = n // i return #-----------------END SMALL PRIME SECTION-----------------# #----------------BEGIN POLLARDS P-1 SECTION---------------# #Pollard P minus 1 factoring, using the algorithm as described by # https://math.berkeley.edu/~sagrawal/su14_math55/notes_pollard.pdf # Then I further modified it by using the standard "B" as the limit, and only # taking a to the power of a prime. Then from looking at wikipedia and such, # I took the gcd out of the loop, and put it at the end. # TODO Update this to official wikipedia definition, once I find an explanation of # Wikipedia definition. (I.e. Why it works)
def __init__( s, GcdUnit, src_msgs, sink_msgs, src_delay, sink_delay, dump_vcd=False, test_verilog=False ): # Instantiate models s.src = TestSource ( GcdUnitReqMsg(), src_msgs, src_delay ) s.gcd = GcdUnit () s.sink = TestSink ( Bits(16), sink_msgs, sink_delay ) # Dump VCD if dump_vcd: s.gcd.vcd_file = dump_vcd # Translation if test_verilog: s.gcd = TranslationTool( s.gcd ) # Connect s.connect( s.src.out, s.gcd.req ) s.connect( s.gcd.resp, s.sink.in_ )
def __init__( s ): # Interface s.req = InValRdyBundle ( GcdUnitReqMsg() ) s.resp = OutValRdyBundle ( Bits(16) ) # Adapters s.req_q = InValRdyQueueAdapter ( s.req ) s.resp_q = OutValRdyQueueAdapter ( s.resp ) # Concurrent block @s.tick_fl def block(): req_msg = s.req_q.popleft() result = gcd( req_msg.a, req_msg.b ) s.resp_q.append( result ) # Line tracing
def break_gcd_cipher(): from crypto.designs.integers.gcd import encrypt, decrypt from os import urandom for _m in range(1, 256): m = 0 while not m: m = ord(urandom(1)) k = ord(urandom(1)) def point_generator(m, k, point_count=32): for count in range(point_count): yield encrypt(m, k)[0] recovered_m = find_basis(point_generator(m, k)) assert recovered_m == m, (recovered_m, m) print("Recovered m: {}".format(recovered_m)) # conclusion: The error in pq + e should be random/should not be kept fixed
def canMeasureWater(self, x, y, z): """ :type x: int :type y: int :type z: int :rtype: bool """ import fractions if z > y + x: return False gcd = fractions.gcd(x, y) if gcd == 0: if x == z or y == z: return True else: return False elif z % gcd == 0: return True else: return False
def calculate_alloc_stats(self): """Calculates the minimum_size and alignment_gcd to determine "virtual allocs" when read lengths of data It's particularly important to cast all numbers to ints, since they're used a lot and object take effort to reread. """ available_allocs = list(self.get_available_allocs()) self.minimum_size = int(min([size for _, size in available_allocs])) accumulator = self.minimum_size for start, _ in available_allocs: if accumulator is None and start > 1: accumulator = start if accumulator and start > 0: accumulator = fractions.gcd(accumulator, start) self.alignment_gcd = int(accumulator) # Pick an arbitrary cut-off that'll lead to too many reads if self.alignment_gcd < 0x4: debug.warning("Alignment of " + self.__class__.__name__ + " is too small, plugins will be extremely slow")
def lcm(*args): """Compute the least common multiple of some non-negative integers""" def lcm2(a, b): 'compute the least common multiple of a, and b' if a == b: return a if 0 in (a,b) or 1 in (a,b):return a*b m,n = min(a,b), max(a,b) while n % m > 0 : m, n = divmod(n, m)[1], m gcd = m return (a*b//gcd) if 0 in args: return 0 args = sorted(args, reverse=True) # print(args) res = args[0] for i in args: if res % i >0: res = lcm2(res, i) else: pass # print(res) return res
def exgcd(a,b): """ Bézout coefficients (u,v) of (a,b) as: a*u + b*v = gcd(a,b) Result is the tuple: (u, v, gcd(a,b)). Examples: >>> exgcd(7*3, 15*3) (-2, 1, 3) >>> exgcd(24157817, 39088169) #sequential Fibonacci numbers (-14930352, 9227465, 1) Algorithm source: Pierre L. Douillet http://www.douillet.info/~douillet/working_papers/bezout/node2.html """ u, v, s, t = 1, 0, 0, 1 while b !=0: q, r = divmod(a,b) a, b = b, r u, s = s, u - q*s v, t = t, v - q*t return (u, v, a)
def lenstra(n, limit): g = n while g == n: # Randomized x and y q = randint(0, n - 1), randint(0, n - 1), 1 # Randomized curve coefficient a, computed b a = randint(0, n - 1) b = (q[1] * q[1] - q[0] * q[0] * q[0] - a * q[0]) % n g = gcd(4 * a * a * a + 27 * b * b, n) # singularity check # If we got lucky, return lucky factor if g > 1: return g # increase k step by step until lcm(1, ..., limit) for p in primes(limit): pp = p while pp < limit: q = elliptic_mul(p, q, a, b, n) # Elliptic arithmetic breaks if q[2] > 1: return gcd(q[2], n) pp = p * pp return False # Command line tool
def distinctdegree(self): d = 0 Result = [] g = [self] x = self.factory.monomial(1) h = [x] while d <= ((g[d].degree() / 2) - 1): d = d + 1 h.append((h[d-1]^(self.factory.q)) % g[d-1]) aux = g[d-1].gcd(h[d] - x) if not aux.is_one(): Result.append((aux,d)) g.append(g[d-1]/aux) if not g[d].is_one(): Result.append((g[d],g[d].degree())) return Result
def line_lattice_points(vertices): """ Return number of points on boundary line not including vertices """ assert len(vertices)==2, "not a line: %s" % vertices xspan = abs(vertices[0][0] - vertices[1][0]) yspan = abs(vertices[0][1] - vertices[1][1]) ret = 0 if xspan == 0 and yspan == 0: ret = 0 elif xspan == 0: ret = yspan - 1 elif yspan == 0: ret = xspan - 1 elif xspan == yspan: ret = xspan - 1 elif yspan > xspan: ret = gcd(yspan, xspan) - 1 elif xspan > yspan: ret = gcd(xspan, yspan) - 1 print "line_lattice_points %s=%d" % (vertices, ret) return ret
def __init__(self, N=2, D=None): if D is None: D = 1 if N < 0: N *= -1 D *= -1 if N < 2: raise ValueError('fraction numerator is less than 2') D %= N if D == 0: raise ValueError('fraction denominator is a multiple ' 'of the numerator') self.parts = fractions.gcd(N, D) self.N = N // self.parts self.D = D // self.parts
def spiro(num_teeth_fixed, num_teeth_move, height, num_segs, outfile): N = abs(num_teeth_fixed) D = abs(num_teeth_move) side_sign = num_teeth_move/D height = height*D/N num_segs = num_segs turns = D/fractions.gcd(N, D) print('OFF\n{} 1 0'.format(num_segs), file=outfile) for i in range(num_segs): ang_fixed = 2*math.pi*turns*i/num_segs ang_move = side_sign * ang_fixed * N/D move_cent = [math.cos(ang_fixed)*(N + side_sign*D)/N, math.sin(ang_fixed)*(N + side_sign*D)/N, 0] move_offset = [height*math.cos(ang_fixed+ang_move), height*math.sin(ang_fixed+ang_move), 0] P = [move_cent[i] + move_offset[i] for i in range(3)] print(P[0], P[1], P[2], file=outfile) print(num_segs, *[i for i in range(num_segs)], file=outfile)
def period_to_factors(base, modulus, period): half_period = period // 2 x = pow(base, half_period, modulus) if x**2 % modulus != 1 or x == 1 or x == -1 % modulus: return None # (x + 1) * (x - 1) = x^2 - 1^2 = 1 - 1 = 0 # therefore (x+1)*(x-1) * k = k * modulus # but (x+1) and (x-1) can't be multiples of modulus # therefore they contain factors factors_1 = fractions.gcd(x + 1, modulus) factors_2 = fractions.gcd(x - 1, modulus) assert factors_1 * factors_2 == modulus return sorted([factors_1, factors_2])
def least_common_multiple(a, b): """ Return the value of the least common multiple. """ return (a * b) / gcd(a, b) # -------------------------------------------------------- # LAYOUT
def lcm(self, a: int, b: int): """Return the lowest common multiple of 2 numbers""" return a * b // gcd(a, b)
def hcf(self, a: int, b: int): """Return the highest common factor of 2 numbers""" return gcd(a,b)
def modinv(a, b): """Returns the modular inverse of a mod b. Pre: a < b and gcd(a, b) = 1 Adapted from https://en.wikibooks.org/wiki/Algorithm_Implementation/ Mathematics/Extended_Euclidean_algorithm#Python """ saved = b x, y, u, v = 0, 1, 1, 0 while a: q, r = b // a, b % a m, n = x - u*q, y - v*q b, a, x, y, u, v = a, r, u, v, m, n return x % saved
def coprime(a, b): """Returns True iff `gcd(a, b) == 1`, i.e. iff `a` and `b` are coprime""" return _fractions.gcd(a, b) == 1
def rsa_recover_prime_factors(n, e, d): """ Compute factors p and q from the private exponent d. We assume that n has no more than two factors. This function is adapted from code in PyCrypto. """ # See 8.2.2(i) in Handbook of Applied Cryptography. ktot = d * e - 1 # The quantity d*e-1 is a multiple of phi(n), even, # and can be represented as t*2^s. t = ktot while t % 2 == 0: t = t // 2 # Cycle through all multiplicative inverses in Zn. # The algorithm is non-deterministic, but there is a 50% chance # any candidate a leads to successful factoring. # See "Digitalized Signatures and Public Key Functions as Intractable # as Factorization", M. Rabin, 1979 spotted = False a = 2 while not spotted and a < _MAX_RECOVERY_ATTEMPTS: k = t # Cycle through all values a^{t*2^i}=a^k while k < ktot: cand = pow(a, k, n) # Check if a^k is a non-trivial root of unity (mod n) if cand != 1 and cand != (n - 1) and pow(cand, 2, n) == 1: # We have found a number such that (cand-1)(cand+1)=0 (mod n). # Either of the terms divides n. p = gcd(cand + 1, n) spotted = True break k *= 2 # This value was not any good... let's try another! a += 2 if not spotted: raise ValueError("Unable to compute factors p and q from exponent d.") # Found ! q, r = divmod(n, p) assert r == 0 return (p, q)
def _lcm(a, b): """ Least Common Multiple between 2 integers. """ if a == 0 or b == 0: return 0 else: return abs(a * b) // fractions.gcd(a, b)
def _check_gear_pair(g1, g2): assert g1.module == g2.module # Load sharing between teeth assert fractions.gcd(g1.n, g2.n) == 1
def rsa_recover_prime_factors(n, e, d): """ Compute factors p and q from the private exponent d. We assume that n has no more than two factors. This function is adapted from code in PyCrypto. """ # See 8.2.2(i) in Handbook of Applied Cryptography. ktot = d * e - 1 # The quantity d*e-1 is a multiple of phi(n), even, # and can be represented as t*2^s. t = ktot while t % 2 == 0: t = t // 2 # Cycle through all multiplicative inverses in Zn. # The algorithm is non-deterministic, but there is a 50% chance # any candidate a leads to successful factoring. # See "Digitalized Signatures and Public Key Functions as Intractable # as Factorization", M. Rabin, 1979 spotted = False a = 2 while not spotted and a < _MAX_RECOVERY_ATTEMPTS: k = t # Cycle through all values a^{t*2^i}=a^k while k < ktot: cand = pow(a, k, n) # Check if a^k is a non-trivial root of unity (mod n) if cand != 1 and cand != (n - 1) and pow(cand, 2, n) == 1: # We have found a number such that (cand-1)(cand+1)=0 (mod n). # Either of the terms divides n. p = gcd(cand + 1, n) spotted = True break k *= 2 # This value was not any good... let's try another! a += 2 if not spotted: raise ValueError("Unable to compute factors p and q from exponent d.") # Found ! q, r = divmod(n, p) assert r == 0 p, q = sorted((p, q), reverse=True) return (p, q)
def _lcm(a, b): """ Least Common Multiple between 2 integers. """ if a == 0 or b == 0: return 0 else: return abs(a * b) // gcd(a, b)
def test_gcd(self): self.assertEqual(fractions.gcd(30,50),GCD.greatest_common_divisor(30,50)) self.assertEqual(fractions.gcd(55555,123450),GCD.greatest_common_divisor(55555,123450)) self.assertEqual(fractions.gcd(-30,-50),GCD.greatest_common_divisor(-30,-50)) self.assertEqual(fractions.gcd(-1234,1234),GCD.greatest_common_divisor(-1234,1234))
def getStepWidth(self, f): limits = f.getLimits() return 1 if limits == [] else reduce(gcd, limits) # returns the highest amount of tests that have been evaluated by one single user
def lcm(numbers): '''kleinstes gemeinsames vielfaches''' return reduce(lambda x, y: (x*y)/gcd(x, y), numbers, 1)
def leastCommonDenominator(denominators): return reduce(lambda x,y: (x*y)//gcd(x,y), denominators)
def compute(): ans = 1 for i in range(1, 21): ans *= i // fractions.gcd(i, ans) return str(ans)
def lattice(p1, p2): pair = (p1, p2) if pair in memo: return memo[pair] t1, t2 = fabs(p2[0] - p1[0]), fabs(p2[1] - p1[1]) g = gcd(t1, t2) + 1 memo[pair] = g return g
def canMeasureWater(self, x, y, z): """ :type x: int :type y: int :type z: int :rtype: bool """ gcd=fractions.gcd(x,y) return True if x+y>=z and (z==0 or (gcd and z%gcd==0)) else False
def egypt_greedy(x, y): if x == 1: return [y] else: a = (-y) % (x) b = y*(y//x + 1) c = gcd(a, b) if c > 1: num, denom = a//c, b//c else: num, denom = a, b return [y//x + 1] + egypt_greedy(num, denom)
def __init__(self, num, den): g = gcd(num, den) self.num = num // g self.den = den // g
def testMisc(self): self.assertEqual(0, gcd(0, 0)) self.assertEqual(1, gcd(1, 0)) self.assertEqual(-1, gcd(-1, 0)) self.assertEqual(1, gcd(0, 1)) self.assertEqual(-1, gcd(0, -1)) self.assertEqual(1, gcd(7, 1)) self.assertEqual(-1, gcd(7, -1)) self.assertEqual(1, gcd(-23, 15)) self.assertEqual(12, gcd(120, 84)) self.assertEqual(-12, gcd(84, -120))
