#!/usr/local/bin/python
# coding: iso-8859-1
# Copyright © 2008 by Amos Newcombe
# 
# This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.
# 
# This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more details.
# 
# You should have received a copy of the GNU General Public License along with this program.  If not, see <http://www.gnu.org/licenses/>.

'''Command-line program to calculate greatest common divisors.
'''

def gcd(nA, nB): # Euclid's algorithm
	while nB: nA, nB = nB, nA % nB
	return nA

def gcdEuclidRecursive(nA, nB):
	if nB == 0: return nA
	return gcdEuclidRecursive(nB, nA % nB)

def gcdLRA(nA, nB):
	while nB:
		nR = nA % nB
		if ( nR > (nB >> 1)): nR = nB - nR
		nA, nB = nB, nR
	return nA

def gcdLRA2(nA, nB):
	while nB:
		nR = nA % nB
		if ( nR > (nB // 2)): nR = nB - nR
		nA, nB = nB, nR
	return nA

def gcdRSB(nA, nB):
	# find even part
	nExp2 = 0
	while not ((nA | nB) & 1):
		nA >>= 1
		nB >>= 1
		nExp2 += 1
	# remove extra factors of 2
	while not (nA & 1): nA >>= 1
	while not (nB & 1): nB >>= 1
	# find odd part
	while nA != nB:
		if nA < nB: nA, nB = nB, nA
		nA -= nB
		while not (nA & 1): nA >>= 1
	return nA << nExp2

def gcdRSB2(nA, nB):
	# find even part
	n2 = 1
	while not ((nA | nB) % 2):
		nA //= 2
		nB //= 2
		n2 *= 2
	# remove extra factors of 2
	while not (nA & 1): nA //= 2
	while not (nB & 1): nB //= 2
	# find odd part
	while nA != nB:
		if nA < nB: nA, nB = nB, nA
		nA -= nB
		while not (nA & 1): nA //= 2
	return nA * n2

def gcdLSB(nA, nB):
	if nA < nB: nA, nB = nB, nA
	while nB > 0:
		nExp2, nBT, nBT1 = 0, nB, nB << 1 
		# invariant: nBT, nBT1 = nB * 2^nExp2, nB * 2^(nExp2+1)
		while nBT1 < nA:
			nExp2 += 1
			nBT    = nBT1
			nBT1 <<= 1
		# nBT <= nA < nBT1
		nA = min(nA - nBT, nBT1 - nA)
		if nA < nB: nA, nB = nB, nA
	return nA

def gcdLSB2(nA, nB):
	if nA < nB: nA, nB = nB, nA
	while nB > 0:
		nExp2, nBT, nBT1 = 0, nB, nB * 2
		# invariant: nBT, nBT1 = nB * 2^nExp2, nB * 2^(nExp2+1)
		while nBT1 < nA:
			nExp2 += 1
			nBT    = nBT1
			nBT1  *= 2
		# nBT <= nA < nBT1
		nA = min(nA - nBT, nBT1 - nA)
		if nA < nB: nA, nB = nB, nA
	return nA

dfGcd = {
	'E': gcd,
	'C': gcdEuclidRecursive,
	'N': gcdLRA,
	'R': gcdRSB,
	'L': gcdLSB,
	'n': gcdLRA2,
	'r': gcdRSB2,
	'l': gcdLSB2,
}

def gcdlist(fGcd, ln):
# 	print 'gcdlist(%s, %s)' % (`fGcd`, ln)
	if isinstance(fGcd, str) and fGcd: fGcd = dfGcd.get(fGcd[0], gcd)
	if not ln: return 0
	nResult, ln = ln[0], ln[1:]
	while ln:
		n, ln = ln[0], ln[1:]
		nResult = fGcd(n, nResult)
	return nResult

from commander.commander import commander
import sys

class CmdGcd(commander):
	
	# ¤ Creation
	
	def __init__(self, lsLine, sName):
		self.sUsage   = '''\
python %%prog <options> n1 n2 ...
Write the %s of the arguments to standard output.
"No bitshift" use multiplication, division and modulo by 2 instead of bit shift and test.\
''' % sName
		self.sVersion = '%prog 2008.08.05.0'
		commander.__init__(self, lsLine)
	
	def options(self): # called by commander.__init__()
		'populate the option parser (self.optParser) with options'
# 			print 'options()'
		nVerbDef = 0 # default verbose level
		self.sAlgDef = 'E'
		self.optParser.add_option('-v', '--verbose',
			action='store', dest='nVerbose', type='int', default=nVerbDef,
			metavar='N', help='set the verbosity to N (default %d)' % nVerbDef
		)
		self.optParser.add_option('-i',
			action='store_true', dest='isStdIn',
			help='get further input from stdin',
		)
		self.optParser.add_option('-E',
			action='store_const', dest='sAlg', const='E',
			help='use Euclid\'s algorithm (default)'
		)
		self.optParser.add_option('-C',
			action='store_const', dest='sAlg', const='C',
			help='use Euclid\'s recursive algorithm'
		)
		self.optParser.add_option('-N',
			action='store_const', dest='sAlg', const='N',
			help='use Euclid\'s algorithm, allowing negative remainders'
		)
		self.optParser.add_option('-n',
			action='store_const', dest='sAlg', const='n',
			help='use Euclid\'s algorithm, allowing negative remainders, no bitshift'
		)
		self.optParser.add_option('-R',
			action='store_const', dest='sAlg', const='R',
			help='use the Right shift binary algorithm'
		)
		self.optParser.add_option('-r',
			action='store_const', dest='sAlg', const='r',
			help='use the Right shift binary algorithm, no bitshift'
		)
		self.optParser.add_option('-L',
			action='store_const', dest='sAlg', const='L',
			help='use the Left shift binary algorithm'
		)
		self.optParser.add_option('-l',
			action='store_const', dest='sAlg', const='l',
			help='use the Left shift binary algorithm, no bitshift'
		)
	
	# ¤ Operation
	
	def main(self, df, sAbbr):
		f = df.get(self.opt.sAlg, df[self.sAlgDef])
		nResult = 0
		for s in self.CommanderArgs(self.lsArgs, self.opt.isStdIn):
			if 2 <= self.opt.nVerbose: 
				print '%s%s(%s, %d) =' % (sAbbr, self.opt.sAlg or self.sAlgDef, s, nResult),
			try: nResult = f(int(s), nResult)
			except ValueError: continue
			if 1 <= self.opt.nVerbose:
				print nResult
		print nResult
	
	class CommanderArgs:
		
		def __init__(self, ls, isStdIn):
			self.ls = ls
			self.isStdIn = isStdIn
			
		def __iter__(self): return self
		
		def next(self):
			if self.ls:
				s, self.ls = self.ls[0], self.ls[1:]
				return s
			elif self.isStdIn:
				self.ls = sys.stdin.next().split()
				return self.next()
			else:
				raise StopIteration

if __name__ == '__main__':

	CmdGcd(sys.argv, 'greatest common divisor').main(dfGcd, 'gcd')