Discussion :

[Invité]

Bonjour,

Pour ma curiosité, je code une bibliothèque de nombre à virgule fixe (Q32 32). Je réalise à chaque fois des tests pour tester les résultats, overflow, etc. et concernant la fonction de multiplication tout se passait bien jusqu'à ce que je passe sur la fonction exp...

Pour cette fonction exp j'utilise la définition formelle ; il y a peut être mieux, mais qu'importe pour l'instant mon problème semble ailleurs.
De la définition formelle je dois calculer la puissance qui fait appel à une fonction de multiplication (Long multiplication). Pour éviter "des erreurs" j'ai crée des détections sur les overflows.

Bref, en appliquant un contrôle sur ma fonction, je me suis aperçu que mon contrôle de dépassement pour la multiplication est faux. En multipliant 10000000000 par 10 je dois obtenir un overflow (un message classique serait implicit conversion from
'long' to 'int32_t' (aka 'int') changes value from 10000000000 to 1410065408) ce dernier nombre est le résultat sorti par la multiplication.

Donc mon contrôle ne passe pas. Vous trouverez le code ci-dessous. Pouvez-vous m'indiquez où

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
 
 
#include <stdint.h>
#include <stdbool.h>
 
typedef int64_t Q32_32;
 
/* CONSTANTS */
#define Q32_32_BIT 64
#define Q32_32_HALF_BIT 32
#define Q32_32_HALF_MAX ((1UL << Q32_32_HALF_BIT) - 1UL)
#define Q32_32_MAX   0x7fffffffffffffff
#define Q32_32_MIN   (-0x7fffffffffffffffLL-1)
#define Q32_32_MASK  0x8000000000000000
#define Q32_32_E     0x00000002B7E15163
 
 
static uint32_t Q32_32_hi(Q32_32 v) {
    return (uint64_t)(v) >> (Q32_32_BIT/2);
}
 
static uint32_t Q32_32_lo(Q32_32 v) {
    return (uint64_t)(v) & Q32_32_HALF_MAX;
}
 
Q32_32 Q32_32_from_int(int32_t v) {
    return (Q32_32)(v) << Q32_32_BIT/2;
}
 
int32_t Q32_32_to_int(Q32_32 v) {
    return (int32_t)(v >> Q32_32_BIT/2);
}
 
Q32_32 Q32_32_mul_noof(Q32_32 a, Q32_32 b, bool *overflow) {
    /* Using Long multiplication */
    /* Split to both 32bits half-words */
    /* lo(a)|hi(a) -> TY */
    /* lo(b)|hi(b) -> GH */
 
    /* h*y */
    /* h*t + g*y*/
    /* g*t */
    /* hi = gt + hi(ht_gy) */
    /* lo = hy + lo(ht_gy) */
    /* prod = hi|lo */
    int64_t a_sign = (int64_t)((uint64_t)a & Q32_32_MASK);
    int64_t b_sign = (int64_t)((uint64_t)b & Q32_32_MASK);
    bool is_neg = (a_sign ^ b_sign) != 0;
    a = a_sign < 0 ? -a : a;
    b = b_sign < 0 ? -b : b;
    uint64_t t = Q32_32_lo(a), y = Q32_32_hi(a);
    uint64_t g = Q32_32_lo(b), h = Q32_32_hi(b);
    uint64_t ht = h*t;
    uint64_t gy = g*y;
    uint64_t hy = h*y;
    uint64_t gt = g*t;
 
    uint64_t ht_gy = ht + gy;
 
    uint64_t hi = gt + Q32_32_hi((int32_t)ht_gy), lo = hy + Q32_32_lo((int32_t)ht_gy);
 
    Q32_32 prod = Q32_32_from_int((int32_t)(hi|lo));
 
    *overflow = prod < (a > b ? a : b);
 
    return is_neg ? -prod : prod;
}

Je pense que j'ai oublié une vérification dans ma détection de dépassement - calcul intermédiaire ? - , mais je n'arrive pas à obtenir un résultat satisfaisant.
Vous est-il possible de m'orienter vers la solution ?

En vous remerciant.

[dalfab]

Bonjour,

avec K = 1.0 (en 32.32) soit 0x100000000LL (en int64)
Le produit (H1.K+L1)*(H2.K+L2) vaut H1.H2.K.K + (H1.L2+H2+L1).K + L1.L2.

H1.H2 doit être inférieur ou égal à 0x7FFFFFFF sinon on dépasse
ensuite on effectue la première addition qui peut aussi dépasser H1.H2.K+(H1.L2+H2+L1) <= 0x7fffffffffffffffLL.
on ajoute ensuite le 3ième terme pour lequel un test overflowed est nécessaire (H1.H2.K+(H1.L2+H2+L1))K + L1.L2.
Tu as oublié au moins un transfert de retenue et il faut au moins 3 tests de dépassement.

[Invité]

Bonjour,

Merci à toi pour les explications. J'ai corrigé avec les tests d'erreurs (ci-dessous le code corrigé). En revanche, je n'ai pas compris (et pas eu le temps hier) la retenu, j'ai tout de même indiqué là où je pense que cela intervient.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
 
Q32_32 Q32_32_mul_noof(Q32_32 a, Q32_32 b, bool *overflow) {
    /* Using Long multiplication */
    /* Split to both 32bits half-words */
    /* lo(a)|hi(a) -> TY */
    /* lo(b)|hi(b) -> GH */
 
    /* h*y */
    /* h*t + g*y*/
    /* g*t */
    /* hi = gt + hi(ht_gy) */
    /* lo = hy + lo(ht_gy) */
    /* prod = hi|lo */
    int64_t a_sign = (int64_t)((uint64_t)a & Q32_32_MASK);
    int64_t b_sign = (int64_t)((uint64_t)b & Q32_32_MASK);
    bool is_neg = (a_sign ^ b_sign) != 0;
    a = a_sign < 0 ? -a : a;
    b = b_sign < 0 ? -b : b;
    uint64_t t = Q32_32_lo(a), y = Q32_32_hi(a);
    uint64_t g = Q32_32_lo(b), h = Q32_32_hi(b);
    uint64_t gt = g*t; /* lowbits */
    uint64_t hy = h*y; /* highbits */
    *overflow = hy > Q32_32_HALF_MAX;
    uint64_t ht = h*t;
    uint64_t gy = g*y;
 
    uint64_t ht_gy = ht + gy;
 
    *overflow = *overflow || ht_gy > Q32_32_MAX;
    uint64_t hi = gt + Q32_32_hi((int32_t)ht_gy), lo = hy + Q32_32_lo((int32_t)ht_gy);
 
    /* RETENU ? */
    if(lo < hy)
        hi++;
 
    Q32_32 prod = Q32_32_from_int((int32_t)(hi|lo));
    *overflow = *overflow || prod < (a > b ? a : b);
    return is_neg ? -prod : prod;
}

[dalfab]

En faisant :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
    uint64_t hi = gt + Q32_32_hi((int32_t)ht_gy), lo = hy + Q32_32_lo((int32_t)ht_gy);
 
    /* RETENU ? */
    if(lo < hy)
        hi++;
 
    Q32_32 prod = Q32_32_from_int((int32_t)(hi|lo));

Quand on calcule, les hi peuvent déborder et il y aura overflow que l'on doit vérifier.
Si les lo débordent, un report de retenu des lo vers hi est perdu. Pour éviter cela il suffit d'ajouter tout dans des int64 et surtout ne jamais faire des | entre 2 morceaux qui auraient été pré-ajoutés.