Algo

multiplication, division, soustraction et modulo en base x

Recherche :

Mot : Pseudo : Filtrer
Page : 1 2 Page Suivante Page Précédente Bas de page
Auteur	Sujet : multiplication, division, soustraction et modulo en base x

blackgoddess

vive le troll !

Bonjour, je cherche des algos (les plus optimisés possibles) pour les multiplication, division, soustraction et modulo en base x.

je n'espere pas un truc tout fait, mais n'importe quelle piste serait la bienvenue.

merci

---------------
-( BlackGoddess )-

Publicité

Deaddy

drole d'idée ! tu veux pas plutot convertir tes nombres de base x en entier, faire tes calculs, puis revenir en base x ?

blackgoddess

vive le troll !

euh ... en fait je cherche a manipuler des gds nombres. j'ai donc pensé a mettre plusieurs nombres (de type unsigned long en c, donc codés sur 32bits et non signés) les 1 a la suite des autres. pour faire une opération, je dois donc calculer comme si c'etait en base 2^32 il me semble donc ?

---------------
-( BlackGoddess )-

Taz

bisounours-codeur

oui. moi aussi, j'ai déjà pensé à ce genre d'implémentation, mais j'ai préféré l'implémentation à base de string

y a pas de recette miracle. addition et soustraction, à la main

mutliplication indienne
et division avec soustraction successive, j'ai pas trouvé d'autres moyens

blackgoddess

vive le troll !

a base de strings ... chaque caractère représente un chiffre de 0 à 9 ou tu as utilisé un caractère comme un nombre de 0 à 255 ? (ou -128 à 127)

et sinon pourrais-tu m'expliquer la division par soustraction successive et la multiplication indienne stp ?

---------------
-( BlackGoddess )-

LeGreg

tu te souviens comment tu faisais tes multiplications et divisions en primaire?

ben tu fais pareil sauf qu'a les faire en base 10 tu les fais
en base x

LeGreg

Deaddy

c simple tu fais comme à la main (au cm2)

voici un exemple d'implémentation en base 2^32, sur du 128 bits, pour l'addition, soustraction, multiplication (je t'ai pas fais la division quand meme!)

Code :

#include <stdio.h>
#include <conio.h>
void zero(unsigned int *x)
{
__asm
{
mov edi,x
xor eax,eax
mov ecx,4
rep stosd
}
}
void mov(unsigned int *x,unsigned int *y)
{
__asm
{
mov esi,y
mov edi,x
mov ecx,4
rep movsd
}
}
void add(unsigned int *x,unsigned int *y)
{
__asm
{
mov esi,y
mov edi,x
mov eax,[esi]
add [edi],eax
mov eax,[esi+4]
adc [edi+4],eax
mov eax,[esi+8]
adc [edi+8],eax
mov eax,[esi+12]
adc [edi+12],eax
}
}
void sub(unsigned int *x,unsigned int *y)
{
__asm
{
mov esi,y
mov edi,x
mov eax,[esi]
sub [edi],eax
mov eax,[esi+4]
sbb [edi+4],eax
mov eax,[esi+8]
sbb [edi+8],eax
mov eax,[esi+12]
sbb [edi+12],eax
}
}
void main()
{
unsigned int a[4],b[4];
int i;
zero(a);
zero(b);
a[3]=0x01234567; a[2]=0x88889999; a[1]=0xaabbccdd; a[0]=0x87654321;
b[0]=0x00010000;
printf(" a = %08X %08X %08X %08X\n",a[3],a[2],a[1],a[0]);
printf(" b = %08X %08X %08X %08X\n",b[3],b[2],b[1],b[0]);
add(a,b);
printf(" a+b = %08X %08X %08X %08X\n",a[3],a[2],a[1],a[0]);
sub(a,b);
printf("a+b-b = %08X %08X %08X %08X\n",a[3],a[2],a[1],a[0]);
// multiplication
unsigned int l00[4],l01[4],l02[4],l03[4];
unsigned int l10[4],l11[4],l12[4],l13[4];
unsigned int l20[4],l21[4],l22[4],l23[4];
unsigned int l30[4],l31[4],l32[4],l33[4];
for (i=0;i<4;i++)
{
l00[i]=l01[i]=l02[i]=l03[i]=0;
l10[i]=l11[i]=l12[i]=l13[i]=0;
l20[i]=l21[i]=l22[i]=l23[i]=0;
l30[i]=l31[i]=l32[i]=l33[i]=0;
}
__asm
{
// ligne 0
mov ebx,b[0]
mov eax,a[0]
mul ebx
mov l00[4],edx
mov l00[0],eax
mov eax,a[4]
mul ebx
mov l01[8],edx
mov l01[4],eax
mov eax,a[8]
mul ebx
mov l02[12],edx
mov l02[8],eax
mov eax,a[12]
mul ebx
mov l03[12],eax
//ligne 1
mov ebx,b[4]
mov eax,a[0]
mul ebx
mov l10[8],edx
mov l10[4],eax
mov eax,a[4]
mul ebx
mov l11[12],edx
mov l11[8],eax
mov eax,a[8]
mul ebx
mov l12[12],eax
// ligne 2
mov ebx,b[8]
mov eax,a[0]
mul ebx
mov l20[12],edx
mov l20[8],eax
mov eax,a[4]
mul ebx
mov l21[12],eax
//ligne 3
mov ebx,b[12]
mov eax,a[0]
mul ebx
mov l30[12],eax
}
mov(a,l00);
add(a,l01);
add(a,l02);
add(a,l03);
add(a,l10);
add(a,l11);
add(a,l12);
add(a,l20);
add(a,l21);
add(a,l30);
printf(" a*b = %08X %08X %08X %08X\n",a[3],a[2],a[1],a[0]);
getch();
}

Message édité par Deaddy le 29-04-2003 à 10:19:09

Evadream -jbd-

Pour la multiplication à l'indienne, fais une recherche sur google avec Multiplication et Karatsuba.

Dans un premier temps, il faut que tu choisisses le mode de réprésentation de tes nombre : Big Endian ou Little Endian.

Le mode Little Endian est celui que nous utilisons tous les jours, par exemple mille deux cents cinquante deux sera érit comme ca : 1252.

En Big Endian, ca donne 2521. Avec une représenation à base de string, ou liste, c'est moins cher en temps pour gérer le propagation de retenue (de proche en proche) plutot que d'aller au fond de ta liste. Tu peux aussi faire une liste doublement chainée avec un pointeur sur la tete et un sur la queue, mais ca fait un peu lourd je trouve

Je pense qu'en faisant un peu de recherche tu trouveras ton bonheur. Il faut juste s'habituer à faire des opérations dans n'importe quelle base, ca ne change rien

Par exemple, A et B sont deux nombres en base X composés des chiffres a4a3a2a1 et b4b3b2b1, on va les additions. Soit r0 la retenue "entrante", nulle.

Si b1+a1+r0 = RES >= X, alors on garde le reste de la division entiere entre RES et X, sinon, on garde RES. La retenue suivante est alors le résultat est celui de la division entiere de RES et X. Et ainsi de suite...

Un petit exemple, avec 2 nombres en base 10.

15
+ 8
---

5 + 8 = 13 > 10, On garde RES mod X = 3 et on génére une retenue de 13/10 = 1.
1 + 1 = 2

=> 23 :)

Voilà le principe !

@+

Message édité par Evadream -jbd- le 29-04-2003 à 12:24:23

blackgoddess

vive le troll !

pour l'addition, j'y etais deja arriver avec du code (tres peu portable car que en BigEndian) : j'avais aussi un pricinpe de retenue : lorsque j'ajoute le nombre de gauche de chaque nombre, je stock le résultat dans une variable de 64bits, et les 32 bits 'bas' font le résultat, et les 32 'hauts' font la retenue.

legreg : je risque de faire un dépassement de capacité avec une multiplication comme en primaire : lorsque je multiplie 2 long, la valeur doit etre tenue ds un int64. le probleme est que si les 2 long ont déja la valeur max, l'int64 aussi. si il y a une retenue, bam ...

---------------
-( BlackGoddess )-

blackgoddess

vive le troll !

(je me plonge de suite dans le décryptage du code asm ... )

---------------
-( BlackGoddess )-

Publicité

blackgoddess

vive le troll !

en tout cas merci beaucoup pour vos réponses

---------------
-( BlackGoddess )-

Deaddy

un peu d'explication sur mon post précedent
// addition
add dest,src : dest=dest+src
s'il y a dépassement CF=1 (carry flag), 0 sinon

adc dest,src : dest=dest+src+CF
s'il y a dépassement CF=1 (carry flag), 0 sinon

CF(2) CF(1) CF(0)

a[3] a[2] a[1] a[0]
b[3] b[2] b[1] b[0]
---------------------------------------------------------
a[3]+b[3]+CF a[2]+b[2]+CF a[1]+b[1]+CF a[0]+b[0]

CF(3) perdu (pourrait servir à detecter le depassement)

//soustraction
sub dest,src : dest=dest-src
s'il y a dépassement CF=1 (carry flag), 0 sinon

sbb dest,src : dest=dest-src-CF
s'il y a dépassement CF=1 (carry flag), 0 sinon

même principe que pour l'addition

// multiplication

mul dest : R = EDX:EAX = eax * dest
eax, edx, dest: 32 bits
R = EDX:EAX : 64 bits
EDX=HI(R) , EAX=LO(R)

A3 A2 A1 A0
x B3 B2 B1 B0
---------------------------------------------------------------
+ 0 0 HI(X00) LO(X00) = l00
+ 0 HI(X01) LO(X01) 0 = l01
+ HI(X02) LO(X02) 0 0 = l02
+ LO(X03) 0 0 0 = l03
---------------------------------------------------------------
+ 0 HI(X10) LO(X10) 0 = l10
+ HI(X11) LO(X11) 0 0 = l11
+ LO(X12) 0 0 0 = l12
---------------------------------------------------------------
+ HI(X20) LO(X20) 0 0 = l20
+ LO(X21) 0 0 0 = l21
---------------------------------------------------------------
+ LO(X30) 0 0 0 = l30
---------------------------------------------------------------

Xij = Aj * Bi (64bits)
lij : resultat (128bits) d'une multiplication élémentaire (cf ci-dessus)

le résultat de la multiplication est la somme de tous les lij.

Message édité par Deaddy le 29-04-2003 à 19:44:10

Deaddy

au secours le formattage !!
(j'ai essayé fixed cpp, et leurs combinaisons mais rien)

[edit] ouf j'ai réussi (après un quart d'heure de padding avec des espaces)

Message édité par Deaddy le 29-04-2003 à 19:34:03

LeGreg

BlackGoddess a écrit :

legreg : je risque de faire un dépassement de capacité avec une multiplication comme en primaire : lorsque je multiplie 2 long, la valeur doit etre tenue ds un int64. le probleme est que si les 2 long ont déja la valeur max, l'int64 aussi. si il y a une retenue, bam ...

eh oh ! je parle de multiplication en base x
pas de multiplication en base long !

LeGreg

blackgoddess

vive le troll !

merci Deaddy pour l'explication lol, j'avais du mal a comprendre le code

pour la multiplication avec l'algo Karatsuba, je suis tjs en train d'essayer de comprendre ... je vais bien finir par y arriver

---------------
-( BlackGoddess )-

Evadream -jbd-

Le truc qu'il faut comprendre pour Karatsuba, c'est la gain d'une multiplication par rapport au raisonnement naif, ce n'est pas juste le fait de faire ca par dichotomie qui te permet de gagner en complexité. ( Théoriquement, on passe d'un complexité quadratique une complexité en n^1.57 si mes souvenirs sont bons)

A+

Taz

bisounours-codeur

ché aps j'ai pas la calculette mais je dirai log2(n)

Evadream -jbd-

n^(log en base de 2 de 3), j'ai retrouvé le résultat !

Edit : il doit surement y avoir plusieurs implémentations de Karatsuba, le résultat que j'ai donné correspond à la seule que j'ai vu, ptetre la version pédagogique

Message édité par Evadream -jbd- le 29-04-2003 à 22:23:33

Taz

bisounours-codeur

sur? ça fait beaucoup quand meme. moi je maintiens un cout logarithmique

Evadream -jbd-

En me basant sur cette page :

http://gersoo.free.fr/docs/karat/kar.html

Ce que j'ai dit semble correct !

Taz

bisounours-codeur

ah je croyais que tu parlais de ma méthode indienne

Evadream -jbd-

[:alphat] Je n'avais pas compris. En fait depuis le début je pense que méthode indienne = Karatsuba

blackgoddess

vive le troll !

++Taz pourrais-tu décrire la méthode indienne alors stp ?

---------------
-( BlackGoddess )-

Taz

bisounours-codeur

Code :

def multIndienne(a, b):
def multR(x, y):
print x, y
if x==1:
return y
if x%2==0:
return multR(x/2, y*2)
else:
return y + multR((x-1)/2, y*2)
if a<b:
return multR(a, b)
else:
return multR(b, a)

c'est comme ça que c'est fait en hardware, par ce que %2, *2 et /2 sont trivial, le reste c'est une additiob

et la il me semble bien que c'est log2(n), avec n la plus petite des 2 operandes

blackgoddess

vive le troll !

d'accord, merci

---------------
-( BlackGoddess )-

blackgoddess

vive le troll !

pour le modulo, j'ai pensé faire la division (vu que c'est des entiers, mon algo arrondi a l'entier inférieur), puis refaire la multiplication et voir la difference.

par exemple :

a mod b
-> c = a/b
d = c*b
resultat = a-d

existe-t-il une manière plus optimisée ?

---------------
-( BlackGoddess )-

Evadream -jbd-

BlackGoddess > j'ai du mal à saisir l'intérêt de ta manip en fait

++Taz > J'ai tenté d'implémenter sur des listes de caractères la multiplication indienne, mais ca me donne des trucs comme ca :

En rouge Karatsuba et en vert la méthode Indienne. En abscisse, la taille des entiers, et en ordonnée le temps en secondes.

Voici pour des grands entiers avec moins de 1000 digits, on sent que l'indienne faiblie :

Voici pour des grands entiers avec moins de 5000 digits :

Je me suis basé sur ton algo et j'ai implémenté ca à la suite d'un projet sur Karatsuba fait en OCaml, voic un bout de code, qui se calque sur ce que tu as donner :

Code :

let multI a b =
let rec multR(x, y) =
match x with
| Zero -> Zero
| Num(1,Zero) -> y
| _ ->
begin
if ( (modBin2 x) = 0) then multR( (binDiv2 x), (binMult2 y) )
else let newres = multR( binDiv2(binMinus1 x), binMult2 y)
in add_with_carry(y, newres, 0, 2)
end
in
let res = compareNumber a b in
if res = -1 then
multR(a, b)
else
multR(b, a);;

modBin2, binMult2, binMinus1 et binDiv2 sont implémentées de la facon suivante :

Code :

let modBin2 a =
match a with
| Zero -> 0
| Num(a,_) -> if a = 0 then 0 else 1
let binMult2 a =
zero(a,1) (*ajout des zeros en tete (Big Endian) *)
let binDiv2 a =
match a with
| Zero -> Zero
| Num(a, Num(r,s) ) -> Num(r,s) (* decal à droite, donc à gauche en BigEndian *)
| Num(a,Zero) -> Zero
let binMinus1 a = (* pour faire le -1 *)
match a with
| Zero -> failwith "never append"
| Num(a,r) -> Num(0,r)

MMmmmm... en tapant je réfléchis à compareBigInteger qui coute cher, mais elle n'est executé qu'une seule fois... (elle part au fond de la liste et la remonte jusque trouvé deux digits différents)...

Je vois pas trop comment améliorer cà, ca semble moins performant que Karatsuba.

Si tu as le temps, vois tu ou ca pourrais coincé ?

Merci à toi !

@+

Message édité par Evadream -jbd- le 30-04-2003 à 02:59:42

Taz

bisounours-codeur

ben c'est un problème d'implémentation, par ce que ln(n)/ln(2) < n*ln(2)

le truc c que si tu fournit pas de décalage rapide, la méthode n'a plus d'interet. cependant, tu vois que ça a quand meme un bonne efficité: c'est un bon cas pour faire un strategy pattern avec une factory

edit: le mieux ça serait que tu utilises un profiler pour voir ou ça coince.

le truc sera sans doute de reduire tes appels à Num. J'ai du mal à te lire, mais si ta division est entiere, tu peux allègrement te passer soustraction. c'est déjà àa de gagner

Message édité par Taz le 30-04-2003 à 09:26:23

blackgoddess

vive le troll !

je n'arrive pas à faire de division ni de modulo

j'ai entendu parler de l'algorithme de newton
http://www.haypocalc.com/grandnbr/division.php
mais je n'ai pas compris

sinon, par soustractions successives, imaginons un tres grand nombre à diviser par 2, si on fait une boucle qui enleve 2 a chaque fois au dividende et rajoute 1 au quotien, jusqu'à ce que le diviseur (2) soit supérieur au dividende, ca prend un temps enorme ... je suppose qu'il doit etre possible de faire justement des divisions triviales par 2 pour n'importe quel diviseur, mais je n'arrive pas a trouver d'algo ...

---------------
-( BlackGoddess )-

Evadream -jbd-

++Taz a écrit :

Merci pour tes remarques.
Num n'est pas une fonction, mais juste un descripteur du type récursif Num.

Pour les décalagages rapides, je ne pense pas pouvoir aller plus rapidement, ces opérations ayant un cout en 0(1).

(Re)Edit : Bin2Mult est maintenant aussi en O(1).

Je vais voir ca avec un profiler, ca va me permettre d'en utiliser un pour la première fois en caml

@+

Message édité par Evadream -jbd- le 30-04-2003 à 13:33:43

Taz

bisounours-codeur

BlackGoddess a écrit :

j'en parlais avec nraynaud l'autre jour: apparemment il n'existe pas d'algorithme vraiment bon pour la division

blackgoddess

vive le troll !

ah

est-il possible de trouver le reste d'une division sans la faire ?

---------------
-( BlackGoddess )-

Taz

bisounours-codeur

je pense pas. cela dit si je relis ta question, ç ame parait evident que non

blackgoddess

vive le troll !

je demande juste lol, il me semblait aussi, mais des fois que qq1 connaisse un algo

---------------
-( BlackGoddess )-

LeGreg

Oui si c'est une division par une puissance de x
si x est la base dans laquelle le nombre est exprimé..

Ceci dit si tu reflechis bien ca veut dire que
la division a deja ete faite (une division par puissance de x pour obtenir le chiffre correspondant).

Sinon en base x tu peux aussi obtenir le reste
de la division par (x-1) en faisant la somme des chiffres de ce nombre dans cette base.

LeGreg

Riot

Buy me a riot

pour la division (avec des soustractions successives):
petit exemple:
14/3:
_ 14-3=11 (1 soustr)
_ 11-3=8 (2soustr)
_ 8-3=5 (3soustr)
_ 5-3=2 (4soustr, reste 2)
--> donc 14/3=4 (car on a effectué 4soustr) , reste 2

de plus on a 14%3 (modulo) ==2

++

Taz

bisounours-codeur

maicaisupair, moi qui croyais que tu uppais pour me fêter mon anniversaire un peu en retard ...

Riot

Buy me a riot

euh... ton anniv en tant que Taz, en tant qu'ex modo, ou dans la vie civile???
dans tous les cas, bon anniv

Riot

Buy me a riot

pour une addition binaire:
vous en pensez quoi???

donc on fait res = A + B

Code :

somme <- 0
retenue <- 0
pour i<-0 à n+1 faire
somme <- A[i] ^ B[i]; // ^ c un xor
res[i] <- somme ^ retenue;
retenue <- (A[i] & B[i]) ^ retenue; // & c un et
fin pour

:hello:

Message édité par Riot le 28-11-2003 à 22:25:25

Riot

Buy me a riot

c si nul que ça??? :?

Publicité

Page : 1 2

Page Suivante

Page Précédente

Haut de page

FORUM HardWare.fr

Programmation

Algo

multiplication, division, soustraction et modulo en base x

Sujets relatifs
Création d'une appli avec base de données de film avi	[PHP/MYSQL] Creer une base de donnés MYSQL en php , sans php my admin?
Recherche base de données	Se connecter à une base ACCESS ?
erreur d'ouverture de base access	besoins de conseil sur base de donnée
adressage indexé et basé...	lire dans la base de registre !
Base PARADOX	Créer une base de données
Plus de sujets relatifs à : multiplication, division, soustraction et modulo en base x

Page générée en 0.134 secondes