multiplication, division, soustraction et modulo en base x - Algo - Programmation
Marsh Posté le 28-04-2003 à 16:15:24
drole d'idée ! tu veux pas plutot convertir tes nombres de base x en entier, faire tes calculs, puis revenir en base x ?
Marsh Posté le 28-04-2003 à 17:33:39
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 ?
Marsh Posté le 28-04-2003 à 17:46:11
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
Marsh Posté le 29-04-2003 à 09:18:11
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 ?
Marsh Posté le 29-04-2003 à 09:31:15
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
Marsh Posté le 29-04-2003 à 10:17:48
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 :
|
Marsh Posté le 29-04-2003 à 12:23:08
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.
|
Voilà le principe !
@+
Marsh Posté le 29-04-2003 à 14:14:26
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 ...
Marsh Posté le 29-04-2003 à 14:15:01
(je me plonge de suite dans le décryptage du code asm ... )
Marsh Posté le 29-04-2003 à 14:17:27
en tout cas merci beaucoup pour vos réponses
Marsh Posté le 29-04-2003 à 19:12:40
|
Marsh Posté le 29-04-2003 à 19:19:55
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)
Marsh Posté le 29-04-2003 à 19:28:50
BlackGoddess a écrit : |
eh oh ! je parle de multiplication en base x
pas de multiplication en base long !
LeGreg
Marsh Posté le 29-04-2003 à 22:07:26
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
Marsh Posté le 29-04-2003 à 22:14:05
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+
Marsh Posté le 29-04-2003 à 22:20:50
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
Marsh Posté le 29-04-2003 à 22:24:54
sur? ça fait beaucoup quand meme. moi je maintiens un cout logarithmique
Marsh Posté le 29-04-2003 à 22:34:43
En me basant sur cette page :
http://gersoo.free.fr/docs/karat/kar.html
Ce que j'ai dit semble correct !
Marsh Posté le 29-04-2003 à 22:43:07
Je n'avais pas compris. En fait depuis le début je pense que méthode indienne = Karatsuba
Marsh Posté le 29-04-2003 à 22:53:28
++Taz pourrais-tu décrire la méthode indienne alors stp ?
Marsh Posté le 29-04-2003 à 23:25:55
Code :
|
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
Marsh Posté le 30-04-2003 à 00:21:53
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 ?
Marsh Posté le 30-04-2003 à 02:57:57
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 :
|
modBin2, binMult2, binMinus1 et binDiv2 sont implémentées de la facon suivante :
Code :
|
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 !
@+
Marsh Posté le 30-04-2003 à 08:56:05
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
Marsh Posté le 30-04-2003 à 12:55:53
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 ...
Marsh Posté le 30-04-2003 à 13:19:15
++Taz a écrit : ben c'est un problème d'implémentation, par ce que ln(n)/ln(2) < n*ln(2) |
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
@+
Marsh Posté le 30-04-2003 à 16:14:24
BlackGoddess a écrit : je n'arrive pas à faire de division ni de modulo |
j'en parlais avec nraynaud l'autre jour: apparemment il n'existe pas d'algorithme vraiment bon pour la division
Marsh Posté le 30-04-2003 à 16:44:43
ah
est-il possible de trouver le reste d'une division sans la faire ?
Marsh Posté le 30-04-2003 à 17:26:13
je pense pas. cela dit si je relis ta question, ç ame parait evident que non
Marsh Posté le 30-04-2003 à 20:33:40
je demande juste lol, il me semblait aussi, mais des fois que qq1 connaisse un algo
Marsh Posté le 30-04-2003 à 20:58:38
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
Marsh Posté le 21-11-2003 à 21:32:22
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
++
Marsh Posté le 21-11-2003 à 21:34:49
maicaisupair, moi qui croyais que tu uppais pour me fêter mon anniversaire un peu en retard ...
Marsh Posté le 21-11-2003 à 22:04:13
euh... ton anniv en tant que Taz, en tant qu'ex modo, ou dans la vie civile???
dans tous les cas, bon anniv
Marsh Posté le 28-11-2003 à 22:24:28
pour une addition binaire:
vous en pensez quoi???
donc on fait res = A + B
Code :
|
Marsh Posté le 28-04-2003 à 00:27:32
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 )-