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))
python类gcd()的实例源码
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);
Prime factors of an integer by Brent algorithm.py 文件源码
项目:Leetcode
作者: staticor
项目源码
文件源码
阅读 44
收藏 0
点赞 0
评论 0
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")
Prime factors of an integer by Brent algorithm.py 文件源码
项目:codewars_python
作者: staticor
项目源码
文件源码
阅读 34
收藏 0
点赞 0
评论 0
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 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 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 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