modulo en binaire
gerard barbera
Je ercherche un algoruthme rapide de calcul du modulo de deux nombres
exprimés en binaire.
Merci d'avance :)
Florian
Yves Gallot
>exprimés en binaire.
Sauf cas particuler (k.2^n+/-1 avec k "petit") pour le modulo, il faut faire
la division. Si tu repètes plusieurs calculs avec le même diviseur, une
optimisation est de calculer l'inverse une fois et d'ensuite multiplier par
celui-ci.
Yves
Barbera Florian
Merci pour la réponse, mais autre question :
Existe-t-il un système apparenté au binaire (DCB ou autre) pour lequel le
calcul du modulo se fait plus "rapidement" ?
Je recherche ces réponse car avec un ami nous voulons nous amuser à inclure en
C++ un type d'entier "super-long" (du genre 200 ou 300 chiffres).
Nous sommes à l'ENSEEIHT Informatique à Toulouse.
Merci ! :)
Florian
Yves Gallot
>calcul du modulo se fait plus "rapidement" ?
Si on peut exprimer N sous la forme k.b^n+/-a avec k et a "petits", on peut
faire la calcul rapidement si on emploie la base b. Mais on reste toujours
dans un cas particulier.
>Je recherche ces réponse car avec un ami nous voulons nous amuser à inclure
en
>C++ un type d'entier "super-long" (du genre 200 ou 300 chiffres).
200 ou 300 chiffres, c'est long pour des entiers (au sens int) mais court
pour des "BigNum". Pour cette taille, un algorithme performant est la
version modifiée de Lehmer de l'algorithme d'Euclide. (voir par exemple "A
Course in Computational Algebraic Number Theory" d'Henri Cohen chez
Springer-Verlag). Avec la division du Knuth, on obtient un algo très rapide.
(voir par exemple la lib gmp de GNU).
>Nous sommes à l'ENSEEIHT Informatique à Toulouse.
Bonjour voisins, il fait un temps à faire de l'informatique ce soir!
Yves
Cyrille de Brebisson
>Existe-t-il un système apparenté au binaire (DCB ou autre) pour lequel le
>calcul du modulo se fait plus "rapidement" ?
Mlheureusement non. je connais assez bien le problemme car je bosse en ASM
sur un pross qui ne sais faire que des additions, des divisions par deux,
des soustractions, des and, or et non. et je peut t'assurer que j'ai
parcourus le problemme en long large et travers.
>Je recherche ces réponse car avec un ami nous voulons nous amuser à inclure
en
>C++ un type d'entier "super-long" (du genre 200 ou 300 chiffres).
dans ce cas, il peut etre interresant de rechercher d'autres types de
calculs addaptes aux nombres long. par exemple une multiplication se ferra
par un truc genre FFT-1(FFT (A)+FFT(B)) (a verifier) qui est en o(n) au
lieux de o(n log(n)) pour une multiplication normale
A+ Cyrile
Yves Gallot
>
>dans ce cas, il peut etre interresant de rechercher d'autres types de
>calculs addaptes aux nombres long. par exemple une multiplication se ferra
>par un truc genre FFT-1(FFT (A)+FFT(B)) (a verifier) qui est en o(n) au
>lieux de o(n log(n)) pour une multiplication normale
La multiplication par FFT ne prend le dessus que pour des nombres de plus de
1000 chiffres et n'est "très" intéressante qu'au delà de 10000 chiffres
(cela dépend bien-sûr de CPU et FPU, mais c'est un bon ordre de grandeur).
La complexité de la multiplication par FFT est en n.log(n).log(log(n)) et la
multiplication classique est en n^2. Il existe des formes récursives
(Karatsuba) en n^(log(3)/(log2)) ~= n^1.58 qui sont un très bon compromis
pour quelques centaines de chiffres. (implémantation: voir toujours la gmp
de GNU).
Yves
http://www.utm.edu/research/primes/programs/gallot/proths.html
florian
Nous sommes des débutants en algorithmique alors, quelqu'un pourrait-il
nous détailler un algorithme de facon complete sachant que l'on veut
calculer le reste et le quotient de deux nombres de tres grandes
tailles (+ de 500 chiffres).
Yves Gallot
>nous détailler un algorithme de facon complete sachant que l'on veut
>calculer le reste et le quotient de deux nombres de tres grandes
>tailles (+ de 500 chiffres).
Dégote le Knuth (Donald E.) :"The Art of Computer Programming", Volume 2 /
Seminumerical Algorithms, Addison-Wesley. On a tous commencé avec lui, je
crois. Il est incontournable. (désolé mais je ne peux pas recopier les 4 ou
5 pages qui traitent de la division).
Yves
Nymbus
à a&(b-1).
Ca y est, je viens de vérifier, c'est ça. C'est vachement plus rapide que de
fair modulo normalement. Le pb, c'est qu'il y a une soustraction à faire, alors
faut voir ce que tu gagnes au bout du compte. Moi, j'ai toujours utilisé ce
truc, et ça a toujours bien marché,
Nymbus
Julien CASSAIGNE
> Je crois (ça fait longtemps...) que si tu veux faire mod(a/b) cela
>équivaut à a&(b-1).
Ça ne marche que si b est une puissance de 2 !
Julien.
--
Julien Cassaigne cass...@iml.univ-mrs.fr
Institut de Mathématiques de Luminy (CNRS), Marseille, France
http://www.eleves.ens.fr:8080/home/cassaign/