arithmétique en 128 bits

Eric Belhomme <{rico}+no/spam@ricospirit.net> a écrit :

J'ai besoin d'effectuer de opérations sur des entiers de 128 bits. probleme
: je ne sais pas manipuler de tels nombres.

Quelles sont les solutions envisageables ? (environement MS Visual C++ 6)

Est-ce que le compilateur offre un support pour une telle chose ?
Que vaut std::limits<long long>.digits() ?

Si le compilateur offre un support pour de tels nombres,
c'est facile, on le prend.
Sinon, c'est plus difficile, surtout suivant le degrès de
portabilité souhaité.
L'idée de base, c'est de faire une classe qui surcharge
les opérateurs arithmétiques et décompose les opérations
(opération membre à membre, propagation de retenue, etc.)
Il doit surement déjà en exister des implémentations,
mais je ne sais pas où les trouver.

Marc Boyer
--
À vélo, prendre une rue à contre-sens est moins dangeureux
que prendre un boulevard dans le sens légal. À qui la faute ?

On 21/06/2005 13:46, Eric Belhomme wrote:

bonjour,

J'ai besoin d'effectuer de opérations sur des entiers de 128 bits. probleme
: je ne sais pas manipuler de tels nombres.

Quelles sont les solutions envisageables ? (environement MS Visual C++ 6)

La prière ;-)

Non, sans plaisanter, c'est râpé avec tous les compilateurs que je connais,
alors il faut aller voir du côté des librairies. Si tu veux vraiment te
limiter à 128 et pas au-delà, c'est peut-être bête d'aller chercher gmp,
miracl ou ntl, seulement je ne connais pas de librairie pour ce que tu veux.
Dernière remarque, si tu n'a besoin que d'additions et multiplications,
c'est facile à faire, seule la division est un peu plus difficile. Si tu n'a
pas besoin que ce soit très rapide, tu peux aussi coder la division, comme
on la fait à la main ou presque. Mais si tu te fiche vraiment de la vitesse,
une librairie "bigint" comme les trois que j'ai citées est toute indiquée.

Deuxième réponse: jette un oeil là:
http://cvs.gnucash.org/docs/HEAD/group__Math128.html
J'ignore complètement où ça mène, je n'ai pas réussi à trouver les sources
de ladite librairie.

Bonne chance

bonjour,

Bonjour,

J'ai besoin d'effectuer de opérations sur des entiers de 128 bits. prob leme
: je ne sais pas manipuler de tels nombres.

Question : tu as besoin d'entiers de 128 bits, mais est-ce que ça
exige une représentation (non signé, signé en code complément à 2,
etc...) ?

tu peux par exemple :

- utiliser (ou faire) une implémentation C (ou une bibliothèque
tierce) qui permet de manipuler des entiers de 128 bits.

- Si ce sont juste les bits qui t'intéressent sans représentation, si
CHAR_BIT vaut 8, manipuler des tableaux d'unsigned char de 16.

- ...

Quelles sont les solutions envisageables ? (environnement MS Visual C++ 6)

Pas de bol...
Une solution, faire ta propre implémentation en utilisant le type
(unsigned) _int64 de MS.


Regis

J'ai besoin d'effectuer de opérations sur des entiers de 128 bits. probleme

je ne sais pas manipuler de tels nombres.

Quelles sont les solutions envisageables ? (environement MS Visual C++ 6)

Est-ce que le compilateur offre un support pour une telle chose ?
Que vaut std::limits<long long>.digits() ?

Si le compilateur offre un support pour de tels nombres,
c'est facile, on le prend.
Sinon, c'est plus difficile, surtout suivant le degrès de
portabilité souhaité.
L'idée de base, c'est de faire une classe qui surcharge
les opérateurs arithmétiques et décompose les opérations
(opération membre à membre, propagation de retenue, etc.)
Il doit surement déjà en exister des implémentations,
mais je ne sais pas où les trouver.
Oui. J'en ai même une dans mes papiers (certainement au C++ très

criticable), mais je ne la trouve pas du tout. Pas protable et pour
cause, c'était une démo d'utilisation de l'assembleur dans une classe
C++.
En fait, on trouve plus facilement des classes "grands entiers" de
taille ouverte. On peut Googler:
big OR huge OR arbitrary integer class
C'est à mon sens un des cas, rares en vérité, où l'assembleur, si on
peut se l'autoriser, est efficace, mais également plus lisible et moins
générateur d'erreurs. Tout se passe au niveau de la détection des
retenues, reports sur le msb (nombre négatifs), etc. L'assembleur est
très efficace, et je n'ai pas trouvé de code C++ qui suggère au
compilateur de générer ce code. Pour une simple addition, on peut
utiliser:
c = a + b;
bool carry = (c < b); // ou (c < a)
(bool ou le unsigned qui va bien)

--
Pour répondre directement: enlever une lettre sur deux
wwaannaaddoooo -> wanadoo

Pierre Maurette

"Pierre Maurette" <mmaauurreetttteeppiieerrrree@wwaannaaddoooo.ffrr> writes:

C'est à mon sens un des cas, rares en vérité, où l'assembleur, si on peut
se l'autoriser, est efficace, mais également plus lisible et moins
générateur d'erreurs.

Je suppose que tu parles des additions et des soustractions. Parce
que les multiplications et les divisions en assembleurs pour des
operandes de tailles variables, c'est pas si simple que ca. (Le seul
endroit ou j'ai vu un algo decrit en detail pour la division, c'est
chez Knuth).

A+

--
Jean-Marc
FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ
C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html
Site de usenet-fr: http://www.usenet-fr.news.eu.org

"Pierre Maurette" <mmaauurreetttteeppiieerrrree@wwaannaaddoooo.ffrr> writes:

C'est à mon sens un des cas, rares en vérité, où l'assembleur, si on peut
se l'autoriser, est efficace, mais également plus lisible et moins
générateur d'erreurs.

Je suppose que tu parles des additions et des soustractions. Parce
que les multiplications et les divisions en assembleurs pour des
operandes de tailles variables, c'est pas si simple que ca. (Le seul
endroit ou j'ai vu un algo decrit en detail pour la division, c'est
chez Knuth).
Effectivement, ce n'est pas simple. Ceci dit, et sans évoquer des jeux

d'instructions trop "spéciaux", on va trouver par exemple des
multiplications 32 * 32 -> 64 (64 * 64 -> 128 en x86-64) ou des
divisions 64 / 32 -> 32(quotient) + 32(reste), et même (64 * 64 -> 128
et 128 / 64 -> 64 + 64 en x86-64) qui positionnent les flags et vont
aider. De plus, les algo efficaces utilisent beaucoup d'additions et de
soustractions.
Je reviens sur un détail. Sans utiliser d'assembleur, on peut tenter
(je me place dans un cas idéal): imaginons une implémenation dans
laquelle la taille naturelle de l'entier est de 32 (ou 64) bits.
Imaginons que cette implémentation offre un entier de taille double (64
ou 128). Les opérations sur ces entiers long seront efficaces (on
l'espère). On pourra alors baser nos grands entiers sur des tableaux
d'entiers "naturels" et effectuer les opérations sur des entiers longs.
Ce sera plus facile. Quand à la vitesse, je n'en sais rien.

--
Pour répondre directement: enlever une lettre sur deux
wwaannaaddoooo -> wanadoo

Pierre Maurette

"Eric Belhomme" <{rico}+no/spam@ricospirit.net> a écrit dans le message de
news: Xns967C8BEDC1B2Aericbelhommefreefr@212.27.42.77...

bonjour,

J'ai besoin d'effectuer de opérations sur des entiers de 128 bits.
probleme
: je ne sais pas manipuler de tels nombres.

Quelles sont les solutions envisageables ? (environement MS Visual C++ 6)

Merci ;)

--
Rico

bonjour,

il y a cette classe mais je ne sais pas ce qu'elle vaut
https://sourceforge.net/projects/cpp-bigint/

Pascal

Eric Belhomme wrote on 21/06/05 :

bonjour,

J'ai besoin d'effectuer de opérations sur des entiers de 128 bits. probleme

je ne sais pas manipuler de tels nombres.

Quelles sont les solutions envisageables ? (environement MS Visual C++ 6)

Merci ;)

Il existe des bibliothèques 'grands entiers' (BigNum, par exemple).
Googole est ton ami...

--
Emmanuel
The C-FAQ: http://www.eskimo.com/~scs/C-faq/faq.html
The C-library: http://www.dinkumware.com/refxc.html

"There are 10 types of people in the world today;
those that understand binary, and those that dont."

"Pascal Pizeine" <pascal.pizeine@milesys.fr> wrote in
news:d99dul$rms$1@s1.news.oleane.net:

bonjour,

il y a cette classe mais je ne sais pas ce qu'elle vaut
https://sourceforge.net/projects/cpp-bigint/

Merci a tous pour vos réponses très intéressantes ;)

Cette classe convient parfaitement pour ce que je voulais faire (calculs de
modulo sur des chiffres concaténés)

J'avais tenté de coder moi meme la division en éclatant mon entier sur des
ulong, maids je me suis heurté à un autre problème, que je n'ai pas réussi
à surmonter en une après midi de recherches : comment convertir une chaine
de caractères représentant un nombre en sa représentation binaire
(factorisé sur 4 ulongs) ?

en d'autre terme, comment coder atoi128, et son pendant i128toa ?

--
Rico

Pierre Maurette wrote:

"Pierre Maurette"
<mmaauurreetttteeppiieerrrree@wwaannaaddoooo.ffrr> writes:

C'est à mon sens un des cas, rares en vérité, où
l'assembleur, si on peut se l'autoriser, est efficace, mais
également plus lisible et moins générateur d'erreurs.

Je suppose que tu parles des additions et des soustractions.
Parce que les multiplications et les divisions en
assembleurs pour des operandes de tailles variables, c'est
pas si simple que ca. (Le seul endroit ou j'ai vu un algo
decrit en detail pour la division, c'est chez Knuth).

Effectivement, ce n'est pas simple. Ceci dit, et sans évoquer
des jeux d'instructions trop "spéciaux", on va trouver par
exemple des multiplications 32 * 32 -> 64 (64 * 64 -> 128 en
x86-64) ou des divisions 64 / 32 -> 32(quotient) + 32(reste),
et même (64 * 64 -> 128 et 128 / 64 -> 64 + 64 en x86-64) qui
positionnent les flags et vont aider. De plus, les algo
efficaces utilisent beaucoup d'additions et de soustractions.

Parfaitement. L'existance d'un 32*32->64 est une aide
inestîmable, de même que la présence des bits de retenu.

Je reviens sur un détail. Sans utiliser d'assembleur, on peut
tenter (je me place dans un cas idéal): imaginons une
implémenation dans laquelle la taille naturelle de l'entier
est de 32 (ou 64) bits.

L'implémentation « classique », (prèsque) 100% portable, c'est
de maintenir des « digits » sur des unsigned char, et de faire
les calculs en int (ou unsigned int). Ça marche sur toutes les
machines où sizeof( int ) > 1.

Mais évidemment, on pourrait se servir de n'importe quel type
entier, du moment qu'il existe un autre type entier qui est au
moins deux fois plus grand, et qu'on fait les calculs
intermédiaire sur cet autre type. Et plus le type de base est
grand, moins on passe dans la boucle de base -- l'algorithme de
base est O(n) pour l'addition et la soustraction, et O(n^2) pour
la multiplication (et je crois aussi la division, mais avec une
constante beaucoup plus grande), où n, c'est le nombre
d'éléments de base. En revanche, ce n'est pas sûr qu'on gagne si
le type intermédiaire n'est pas supporter en hardware. Sur une
machine 32 bits classique d'aujourd'hui, je soupçonne que
unsigned short serait le type de base optimal, avec unsigned int
comme type intermédiare ; sur une machine 64 bits (Sparc,
PA-Risc, Alpha, Itanium...), unsigned int et unsigned long
pourrait s'imposer.

Imaginons que cette implémentation offre un entier de taille
double (64 ou 128). Les opérations sur ces entiers long seront
efficaces (on l'espère). On pourra alors baser nos grands
entiers sur des tableaux d'entiers "naturels" et effectuer les
opérations sur des entiers longs. Ce sera plus facile. Quand à
la vitesse, je n'en sais rien.

Quand à la vitesse, c'est simple : la multiplication est O(n^2),
où n est le nombre d'éléments. Du coup, la version en langage
évolué effectuera quatre fois plus d'opérations lors d'une
multiplication.

L'exception, évidemment, c'est quand les instructions machine
pour la multiplication ne donne pas un résultat plus grand que
les opérands. (C'est le cas sur un Sparc v9, par exemple, où
l'instruction de multiplication est 64*64->64. Or que les
versions plus anciennes avaient bien 32*32->64. Et les versions
encore plus anciennes n'avaient même pas de multiplication
cablée, mais seulement une instruction dite « multiply step »,
qui était en fait une espèce de shift/conditional add.)

--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34