En el artículo anterior, ya hemos discutido el algoritmo de división sin restauración . En este artículo, discutiremos la implementación de este algoritmo.
El algoritmo de división sin restauración se utiliza para dividir dos enteros sin signo. La otra forma de este algoritmo es Restoring Division . Este algoritmo es diferente del otro algoritmo porque aquí no existe el concepto de restauración y este algoritmo es menos complejo que el algoritmo de división de restauración. Sea el dividendo Q = 0110 y el divisor M = 0100. La siguiente tabla demuestra la solución paso a paso para los valores dados:
| Acumulador-A(0) | Dividendo-Q(6) | Estado | |
|---|---|---|---|
Initial Values |
0000 | 0111 | 0101(M) |
Step1:Left-Shift |
0000 | 111_ | |
| Operación: A – M | 1011 | 1110 | Error (-ve) A+M en el siguiente paso |
Step2:Left-Shift |
0111 | 110_ | |
| Operación: A + M | 1100 | 1100 | Error (-ve) A+M en el siguiente paso |
Step3:Left-Shift |
1001 | 100_ | |
| Operación: A + M | 1110 | 1000 | Error (-ve) A+M en el siguiente paso |
Step4:Left-Shift |
1101 | 000_ | |
| Operación: A + M | 0010 | 0001 | Exitoso (+ ve) |
| Resto(2) | cociente(1) |
Enfoque: A partir de la solución anterior, la idea es observar que la cantidad de pasos necesarios para calcular el cociente y el resto necesarios es igual a la cantidad de bits en el dividendo. Inicialmente, sea Q el dividendo y M el divisor y el acumulador A = 0. Por lo tanto:
- En cada paso, desplaza el dividendo a la izquierda en 1 posición.
- Resta el divisor de A (A – M).
- Si el resultado es positivo, se dice que el paso es «exitoso». En este caso, el bit de cociente será «1» y NO se requiere la restauración. Entonces, el siguiente paso también será la resta.
- Si el resultado es negativo, se dice que el paso es «fallido». En este caso, el bit cociente será “0”. Aquí, la restauración NO se realiza como el algoritmo de división de restauración. En cambio, el siguiente paso será SUMAR en lugar de restar.
- Repita los pasos 1 a 4 para todos los bits del Dividendo.
A continuación se muestra la implementación del enfoque anterior:
# Python program to divide two
# unsigned integers using
# Non-Restoring Division Algorithm
# Function to add two binary numbers
def add(A, M):
carry = 0
Sum = ''
# Iterating through the number
# A. Here, it is assumed that
# the length of both the numbers
# is same
for i in range (len(A)-1, -1, -1):
# Adding the values at both
# the indices along with the
# carry
temp = int(A[i]) + int(M[i]) + carry
# If the binary number exceeds 1
if (temp>1):
Sum += str(temp % 2)
carry = 1
else:
Sum += str(temp)
carry = 0
# Returning the sum from
# MSB to LSB
return Sum[::-1]
# Function to find the compliment
# of the given binary number
def compliment(m):
M = ''
# Iterating through the number
for i in range (0, len(m)):
# Computing the compliment
M += str((int(m[i]) + 1) % 2)
# Adding 1 to the computed
# value
M = add(M, '0001')
return M
# Function to find the quotient
# and remainder using the
# Non-Restoring Division Algorithm
def nonRestoringDivision(Q, M, A):
# Computing the length of the
# number
count = len(M)
comp_M = compliment(M)
# Variable to determine whether
# addition or subtraction has
# to be computed for the next step
flag = 'successful'
# Printing the initial values
# of the accumulator, dividend
# and divisor
print ('Initial Values: A:', A,
' Q:', Q, ' M:', M)
# The number of steps is equal to the
# length of the binary number
while (count):
# Printing the values at every step
print ("\nstep:", len(M)-count + 1,
end = '')
# Step1: Left Shift, assigning LSB of Q
# to MSB of A.
print (' Left Shift and ', end = '')
A = A[1:] + Q[0]
# Choosing the addition
# or subtraction based on the
# result of the previous step
if (flag == 'successful'):
A = add(A, comp_M)
print ('subtract: ')
else:
A = add(A, M)
print ('Addition: ')
print('A:', A, ' Q:',
Q[1:]+'_', end ='')
if (A[0] == '1'):
# Step is unsuccessful and the
# quotient bit will be '0'
Q = Q[1:] + '0'
print (' -Unsuccessful')
flag = 'unsuccessful'
print ('A:', A, ' Q:', Q,
' -Addition in next Step')
else:
# Step is successful and the quotient
# bit will be '1'
Q = Q[1:] + '1'
print (' Successful')
flag = 'successful'
print ('A:', A, ' Q:', Q,
' -Subtraction in next step')
count -= 1
print ('\nQuotient(Q):', Q,
' Remainder(A):', A)
# Driver code
if __name__ == "__main__":
dividend = '0111'
divisor = '0101'
accumulator = '0' * len(dividend)
nonRestoringDivision(dividend,
divisor,
accumulator)
Initial Values: A: 0000 Q: 0111 M: 0101 step: 1 Left Shift and subtract: A: 1011 Q: 111_ -Unsuccessful A: 1011 Q: 1110 -Addition in next Step step: 2 Left Shift and Addition: A: 1100 Q: 110_ -Unsuccessful A: 1100 Q: 1100 -Addition in next Step step: 3 Left Shift and Addition: A: 1110 Q: 100_ -Unsuccessful A: 1110 Q: 1000 -Addition in next Step step: 4 Left Shift and Addition: A: 0010 Q: 000_ Successful A: 0010 Q: 0001 -Subtraction in next step Quotient(Q): 0001 Remainder(A): 0010
Publicación traducida automáticamente
Artículo escrito por amit_mangal_ y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA