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

Question

Hi, I’m writing algorithms for large numbers. I implemented the operations of sum, division and subtraction but for divide I have no idea just an algorithm to use with binary base. 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?

I’ll leave the recursive binary algorithm to 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)

Answer 1

I don’t understand why a list should be circulated, but come on. As you passed pseudocode in the question, I will answer with pseudocode too; if later have difficulty in converting pseudocode into C, put the structures so I can try to make the matches.

The algorithm is essentially the algorithm that we all learned there in the 4th 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 four-bit BCD digits per decimal digit.