




def 		lowerCAmelCase_   (	lowerCamelCase	,     lowerCamelCase = False   ):
				if n == 2:
								return True
				if not n % 2 or n < 2:
								return False
				if n > 5 and n % 10 not in (1, 3, 7, 9):  # can quickly check last digit
								return False
				if n > 3317044064679887385961981 and not allow_probable:
								raise ValueError(
								    """Warning: upper bound of deterministic test is exceeded. """
								    """Pass allow_probable=True to allow probabilistic test. """
								    """A return value of True indicates a probable prime."""   )
				# array bounds provided by analysis
				__magic_name__	:	Optional[Any]								=[
				    2047,
				    1373653,
				    25326001,
				    3215031751,
				    2152302898747,
				    3474749660383,
				    341550071728321,
				    1,
				    3825123056546413051,
				    1,
				    1,
				    318665857834031151167461,
				    3317044064679887385961981,
				]

				__magic_name__	:	Tuple								=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]
				for idx, _p in enumerate(lowerCamelCase	,     1   ):
								if n < _p:
												# then we have our last prime to check
												__magic_name__	:	str								=primes[:idx]
												break
				__magic_name__				, __magic_name__	:	Union[str, Any]								=n - 1, 0
				# break up n -1 into a power of 2 (s) and
				# remaining odd component
				# essentially, solve for d * 2 ** s == n - 1
				while d % 2 == 0:
								d //= 2
								s += 1
				for prime in plist:
								__magic_name__	:	Any								=False
								for r in range(lowerCamelCase   ):
												__magic_name__	:	str								=pow(lowerCamelCase	,     d * 2**r	,     lowerCamelCase   )
												# see article for analysis explanation for m
												if (r == 0 and m == 1) or ((m + 1) % n == 0):
																__magic_name__	:	Optional[int]								=True
																# this loop will not determine compositeness
																break
								if pr:
												continue
								# if pr is False, then the above loop never evaluated to true,
								# and the n MUST be composite
								return False
				return True




def 		lowerCAmelCase_   (	):
				assert not miller_rabin(561   )
				assert miller_rabin(563   )
				# 2047

				assert not miller_rabin(838201   )
				assert miller_rabin(838207   )
				# 1_373_653

				assert not miller_rabin(17316001   )
				assert miller_rabin(17316017   )
				# 25_326_001

				assert not miller_rabin(3078386641   )
				assert miller_rabin(3078386653   )
				# 3_215_031_751

				assert not miller_rabin(1713045574801   )
				assert miller_rabin(1713045574819   )
				# 2_152_302_898_747

				assert not miller_rabin(2779799728307   )
				assert miller_rabin(2779799728327   )
				# 3_474_749_660_383

				assert not miller_rabin(113850023909441   )
				assert miller_rabin(113850023909527   )
				# 341_550_071_728_321

				assert not miller_rabin(1275041018848804351   )
				assert miller_rabin(1275041018848804391   )
				# 3_825_123_056_546_413_051

				assert not miller_rabin(79666464458507787791867   )
				assert miller_rabin(79666464458507787791951   )
				# 318_665_857_834_031_151_167_461

				assert not miller_rabin(552840677446647897660333   )
				assert miller_rabin(552840677446647897660359   )
				# 3_317_044_064_679_887_385_961_981
				# upper limit for probabilistic test


if __name__ == "__main__":
							test_miller_rabin()










import numpy as np




def 		lowerCAmelCase_   (	lowerCamelCase	,     lowerCamelCase	,     lowerCamelCase = 1E-12	,     lowerCamelCase = 100	,     ):
				assert np.shape(lowerCamelCase   )[0] == np.shape(lowerCamelCase   )[1]
				# Ensure proper dimensionality.
				assert np.shape(lowerCamelCase   )[0] == np.shape(lowerCamelCase   )[0]
				# Ensure inputs are either both complex or both real
				assert np.iscomplexobj(lowerCamelCase   ) == np.iscomplexobj(lowerCamelCase   )
				__magic_name__	:	List[Any]								=np.iscomplexobj(lowerCamelCase   )
				if is_complex:
								# Ensure complex input_matrix is Hermitian
								assert np.array_equal(lowerCamelCase	,     input_matrix.conj().T   )

				# Set convergence to False. Will define convergence when we exceed max_iterations
				# or when we have small changes from one iteration to next.

				__magic_name__	:	List[Any]								=False
				__magic_name__	:	List[Any]								=0
				__magic_name__	:	List[str]								=0
				__magic_name__	:	str								=1E12

				while not convergence:
								# Multiple matrix by the vector.
								__magic_name__	:	Dict								=np.dot(lowerCamelCase	,     lowerCamelCase   )
								# Normalize the resulting output vector.
								__magic_name__	:	List[str]								=w / np.linalg.norm(lowerCamelCase   )
								# Find rayleigh quotient
								# (faster than usual b/c we know vector is normalized already)
								__magic_name__	:	Any								=vector.conj().T if is_complex else vector.T
								__magic_name__	:	List[str]								=np.dot(lowerCamelCase	,     np.dot(lowerCamelCase	,     lowerCamelCase   )   )

								# Check convergence.
								__magic_name__	:	List[str]								=np.abs(lambda_ - lambda_previous   ) / lambda_
								iterations += 1

								if error <= error_tol or iterations >= max_iterations:
												__magic_name__	:	int								=True

								__magic_name__	:	Optional[Any]								=lambda_

				if is_complex:
								__magic_name__	:	Union[str, Any]								=np.real(lambda_   )

				return lambda_, vector




def 		lowerCAmelCase_   (	):
				__magic_name__	:	Optional[int]								=np.array([[41, 4, 20], [4, 26, 30], [20, 30, 50]]   )
				__magic_name__	:	Any								=np.array([41, 4, 20]   )
				__magic_name__	:	Optional[Any]								=real_input_matrix.astype(np.complexaaa   )
				__magic_name__	:	str								=np.triu(1J * complex_input_matrix	,     1   )
				complex_input_matrix += imag_matrix
				complex_input_matrix += -1 * imag_matrix.T
				__magic_name__	:	List[Any]								=np.array([41, 4, 20]   ).astype(np.complexaaa   )

				for problem_type in ["real", "complex"]:
								if problem_type == "real":
												__magic_name__	:	Union[str, Any]								=real_input_matrix
												__magic_name__	:	List[Any]								=real_vector
								elif problem_type == "complex":
												__magic_name__	:	Optional[Any]								=complex_input_matrix
												__magic_name__	:	Tuple								=complex_vector

								# Our implementation.
								__magic_name__				, __magic_name__	:	Any								=power_iteration(lowerCamelCase	,     lowerCamelCase   )

								# Numpy implementation.

								# Get eigenvalues and eigenvectors using built-in numpy
								# eigh (eigh used for symmetric or hermetian matrices).
								__magic_name__				, __magic_name__	:	int								=np.linalg.eigh(lowerCamelCase   )
								# Last eigenvalue is the maximum one.
								__magic_name__	:	List[str]								=eigen_values[-1]
								# Last column in this matrix is eigenvector corresponding to largest eigenvalue.
								__magic_name__	:	Dict								=eigen_vectors[:, -1]

								# Check our implementation and numpy gives close answers.
								assert np.abs(eigen_value - eigen_value_max   ) <= 1E-6
								# Take absolute values element wise of each eigenvector.
								# as they are only unique to a minus sign.
								assert np.linalg.norm(np.abs(lowerCamelCase   ) - np.abs(lowerCamelCase   )   ) <= 1E-6


if __name__ == "__main__":
							import doctest

							doctest.testmod()
							test_power_iteration()




