Division de deux entiers 32 bits - Page 1

yop,

Je cherche à écrire la division entière de deux entiers de 32 bits. Je ne sais pas si les entiers sont signés ou non. On va dire que non, au pif. Et je n'ai pas besoin du reste.
Le truc, c'est que je n'ai aucune idée de par où commencer. Autant pour la multiplication, j'ai réussi à me débrouiller simplement avec les multiplications 16 bits du 68k, autant pour la division, je ne sais pas comment décomposer mes entiers pour chercher le résultat. Donc si vous aviez une simple idée, pour que je puisse commencer à réfléchir, ça m'aiderait beaucoup.

J'ai regardé du côté de genlib, il y a une macro de division d'un 32 bits par un 16 bits. Mais c'est pas commenté, je vois donc pas la logique de l'algo. J'ai pas trouvé quelque chose d'équivalent dans TIGCC, bien que ça existe sûrement, je suis quasiment certain d'avoir vu ça.

Merci d'avance pour vos pistes.

-

C'est un binaire ton truc

Merci beaucoup Orion, mais j'aurais préféré une idée, pour creuser et implémenter moi-même. Je tiens absolument à comprendre complètement. Ah, aussi, la lenteur ou la longueur du code produit ne me dérange pas.

void div(unsigned int a, unsigned int b, unsigned int *q, unsigned int *r)
{
 *q = 0;
 *r = a;

 while (b >= *r) {
   assert( *q * b + *r == a);
   *r -=b;
   *q += 1;
 }
}

? Sinon y'a le code de PedroM.

Haaaaan PpHd, je suis sur le cul tellement c'est simplet et con comme solution, moi qui était parti sur un vieux truc arithmétique chelou
Merci bien. J'avais oublié que PedroM implémentait une division de ce genre, je vais voir merci bien.

RHJPP (./6) :

PpHd (./5) :
while (b >= *r) {

Oui, bon, ok, j'ai inversé

Moi je faisais ça comme ça, il me semble que ça va nettement plus vite que ce qu'a proposé Pphd parce que ça tire partie des opérations bit à bit. Je crois me rappeler que la fonction demandait typiquement aux alentours des 150 cycles, et un peu moins pour les nombres "simples" avec peu de bits à 1 :

unsigned int division(s32 i, u32 x, u32 y) {
	// x%y
	u32 j, z = 0;
	while ((y << i) == 0)
		i -= 2;
	for (; i >= 0; i -= 2) {
		j = y << i;
		while (x >= j) {
			x -= j;
			z += 1 << i;
		}
	}

	return z;
}

Et après ça s'appelle comme ça :

#define div32(x, y) division(30, x, y)
#define div16(x, y) division(14, x, y)

Après quand t'as vraiment besoin d'une division rapide tu peux aussi dérouler la boucle en ASM. (Tain j'ai dû écrire ça y a 10 ans...)

C'est clair que la solution que j'ai proposé et tout sauf rapide. Mais c'est la plus simple et c'était dans le cahier des charges de ./1

Tout à fait. Je veux d'abord un truc qui marche. Pour la vitesse, on verra après.
Merci Brunni cependant, ça donnera matière à optimiser ça au poil de cul

Bon, j'ai fini par élaborer ce code, ultra-concis :

\OperatorDivide:
	movem.l	d1-d2/a0-a1,-(sp)
	move.l	d3,d1
	ROMT	_du32u32
	move.l	d1,d0
	movem.l	(sp)+,d1-d2/a0-a1
	rts

(j'ai quand même lu le code de PedroM par principe, non mais ho )

Tout ça pour ça...

J'avais complètement zappé que ça existait en fait