How to divide 2 numbers represented by a circular list in C?

0

Hello, I'm writing algorithms for large numbers. I implemented the addition, division and subtraction operations but for the divide I have no idea just an algorithm to use with binary basis. It is not an option to turn the number to binary, I want to use base 10.

The numbers I want to divide are represented as follows:

2346

| 2 | - | 3 | -> 4 | -> 6 |

It's a circular list.

How can I do this?

I will leave the algorithm in binary recursive for the division:

funcao divide(x,y)
entrada: dois numeros inteiros de n bits x e y, onde y >= 1
saida: o quociente e o resto de x dividido por y

se x = 0 : retorn (q,r) = (0,0)
(q,r) = divide(floor(x/2),y)
q = 2*q, r = 2*r
se x é impar: r = r + 1
se r>=y: r = r - y, q = q + 1
retorna (q,r)
    
asked by anonymous 28.05.2016 / 18:21

1 answer

0

I do not understand why a circular list, but go there. As you passed pseudocode in the question, I will respond with pseudocode as well; if you later have difficulty converting the pseudocode to C, put the structures so that I can try to match.

The algorithm is essentially the algorithm we all learned there in the fourth year with Aunt Loló:

função divide(x, y)
entrada: dois números inteiros e posiitivos, sendo y > 0
saída: o quociente e o resto de x dividido por y

01: se x = 0: retorne (0, 0)
02: seja ny = número de dígitos de y
03: seja x' = ny dígitos mais significativos de x
04: início do loop:
05:     seja dq = 0
06:     enquanto x' >= y, faça x' = x' - y e incremente dq
07:     concatene dq no final de q
08:     se ainda houver dígitos de x que não foram incluídos em x',
09:         concatene o próximo dígito mais significativo de x no final de x'
10:         senão saia do loop (vá para a linha 12)
11: fim do loop (vá para a linha 04)
12: retorne (q, x')

Note that the algorithm works equally well for non-circular lists of digits, or for vectors of BCD digits to four bits per decimal digit.

    
18.05.2017 / 05:05