divide.c File Reference

#include <stdlib.h>
#include <stdio.h>
#include "linear_assert.h"
#include "arithmetique.h"

Include dependency graph for divide.c:

Go to the source code of this file.

Macros
#define	DIVIDE_MAX_A   7
#define	DIVIDE_MAX_B   8

Functions
Value	divide_fast (Value a, Value b)
	package arithmetique More...
Value	divide_slow (Value a, Value b)

Macro Definition Documentation

DIVIDE_MAX_A

#define DIVIDE_MAX_A   7

DIVIDE_MAX_B

#define DIVIDE_MAX_B   8

Function Documentation

divide_fast()

Value divide_fast	(	Value	a,
		Value	b
	)

package arithmetique

divide.c

INTLIBRARY int divide(int a, int b): calcul du divide de a par b; le reste (qui n'est pas retourne) est toujours positif; il est fourni par la fonction modulo()

Il y a quatre configuration de signe a traiter:

1. a>0 && b>0: a / b
2. a<0 && b>0: (a-b+1) / b
3. a>0 && b<0: cf. 1. apres changement de signe de b, puis changement de signe du resultat
4. a<0 && b<0: cf. 2. apres changement de signe de b, puis changement de signe du resultat
5. a==0: 0

definition d'une look-up table pour les valeurs de a appartenant a [-DIVIDE_MAX_A..DIVIDE_MAX_A] et pour les valeurs de b appartenant a 1..DIVIDE_MAX_B

Serait-il utile d'ajouter une test b==1 pour supprimer une colonne?

Serait-il utile de tester b > a pour renvoyer 0 ou -1 tout de suite?

b == 1 2 3 4 5 6 7 8

a == - 7

a == - 6

a == - 5

a == - 4

a == - 3

a == - 2

a == - 1

a == 0

a == 1

a == 2

a == 3

a == 4

a == 5

a == 6

a == 7

translation de a pour acces a la look-up table par indice positif: la == a + DIVIDE_MAX_A >= 0

valeur du quotient C

serait-il utile d'optimiser la division de a=0 par b? Ou bien cette routine n'est-elle jamais appelee avec a=0 par le package vecteur?

direct table look up

shift a for the table

this is just divide_slow

Definition at line 51 of file divide.c.

{
    /* definition d'une look-up table pour les valeurs de a appartenant
       a [-DIVIDE_MAX_A..DIVIDE_MAX_A] et pour les valeurs de b
       appartenant a [1..DIVIDE_MAX_B] (en fait [-DIVIDE_MAX_B..DIVIDE_MAX_B]
       a cause du changement de signe)
       
       Serait-il utile d'ajouter une test b==1 pour supprimer une colonne?
 
       Serait-il utile de tester b > a pour renvoyer 0 ou -1 tout de suite?
       */
 
#define DIVIDE_MAX_A 7
#define DIVIDE_MAX_B 8
 
    static Value
        divide_look_up[2*DIVIDE_MAX_A+1][DIVIDE_MAX_B]={
        /* b ==         1   2   3   4   5   6   7   8 */
        {/* a == - 7 */ -7, -4, -3, -2, -2, -2, -1, -1},
        {/* a == - 6 */ -6, -3, -2, -2, -2, -1, -1, -1},
        {/* a == - 5 */ -5, -3, -2, -2, -1, -1, -1, -1},
        {/* a == - 4 */ -4, -2, -2, -2, -1, -1, -1, -1},
        {/* a == - 3 */ -3, -2, -1, -1, -1, -1, -1, -1},
        {/* a == - 2 */ -2, -1, -1, -1, -1, -1, -1, -1},
        {/* a == - 1 */ -1, -1, -1, -1, -1, -1, -1, -1},
        {/* a ==   0 */  0,  0,  0,  0,  0,  0,  0,  0},
        {/* a ==   1 */  1,  0,  0,  0,  0,  0,  0,  0},
        {/* a ==   2 */  2,  1,  0,  0,  0,  0,  0,  0},
        {/* a ==   3 */  3,  1,  1,  0,  0,  0,  0,  0},
        {/* a ==   4 */  4,  2,  1,  1,  0,  0,  0,  0},
        {/* a ==   5 */  5,  2,  1,  1,  1,  0,  0,  0},
        {/* a ==   6 */  6,  3,  2,  1,  1,  1,  0,  0},
        {/* a ==   7 */  7,  3,  2,  1,  1,  1,  1,  0}
    };
    /* translation de a pour acces a la look-up table par indice positif:
       la == a + DIVIDE_MAX_A >= 0 */
 
    Value quotient;     /* valeur du quotient C */
 
    assert(value_notzero_p(b));
 
    /* serait-il utile d'optimiser la division de a=0 par b? Ou bien
       cette routine n'est-elle jamais appelee avec a=0 par le package vecteur?
       */
 
    if (value_le(a, int_to_value(DIVIDE_MAX_A)) && 
        value_ge(a, int_to_value(-DIVIDE_MAX_A)) &&
        value_le(b, int_to_value(DIVIDE_MAX_B)) &&
        value_ge(b, int_to_value(-DIVIDE_MAX_B)))
    {
        /* direct table look up */
        int bint = VALUE_TO_INT(b),
            la = VALUE_TO_INT(a)+DIVIDE_MAX_A; /* shift a for the table */
        quotient = (bint>0)?
            divide_look_up[la][bint-1]:
                value_uminus(divide_look_up[la][(-bint)-1]);
    }
    else 
        quotient = value_pdiv(a,b); /* this is just divide_slow */
 
    return quotient;
}

References assert, DIVIDE_MAX_A, DIVIDE_MAX_B, int_to_value, value_ge, value_le, value_notzero_p, value_pdiv, VALUE_TO_INT, and value_uminus.

divide_slow()

Value divide_slow	(	Value	a,
		Value	b
	)

Definition at line 114 of file divide.c.

{
    return value_pdiv(a, b);
}

References value_pdiv.