Discussion :

[BorisTheBear]

Bonjour,

Je cherche actuellement une implémentation d'une classe arithmétique d'un entier 128 bits .

BigInteger ne m'intéresse pas , à cause de ses performances désastreuses tant en terme de CPU que de RAM (Cette classe est prévue pour être générique, moi, je veux du 128 "dur")

A défaut, j'ai commencé mon affaire en manipulant 2 longs, mais les opérations e multiplication/division me donnent du fil à retordre.

Quelqu'un connais une implémentation pour ça ?
Sinon, je vais coder un truc en C++ et le wrapper avec du JNI

[professeur shadoko]

créer une classe qui utilise un Bitset? (je n'ai aucune idée des perfs de Bitset )

[tchize_]

Bitset est lent, très lent si tu veux en faire un entier de 128nits. Il est prévu pour servir de tableau de booléens, pas pour faire de nombreuses opération de changement dessus.

Qu'est-ce qui te pose problème pour la division / multiplication?

Tu peux utiliser la division par soustraction (la plus simple) qui n'est pas très performante ou le complexe Newton–Raphson.

Mais pourquoi tu refuse de déléguer ce travail à BigInteger?

[BorisTheBear]

Il y a une chose que je veux dans java, c'est les templates.

Je me dis qu'un bigInteger( new byte[16]) doit être extremmement lent par rapport a un bigInteger<16>..

Peut être je devrais recoder cette classe ?

[tchize_]

Ce n'est pas beaucoup plus lent de manipuler 2 long que de manipuler 4 long. Le code reste le même, la seul différence, c'est que les opération auront 4 étapes au lieu de 2.

Si tu regarde le code de BigInteger, je ne vois pas ce que tu voudrais ajouter comme optimisation

Ce que tu appelle des template, ça s'appelle des Generic en java, et ça prend en paramètre un type, pas une valeur, comme les template c++

[thelvin]

Si tu regarde le code de BigInteger, je ne vois pas ce que tu voudrais ajouter comme optimisation

L'utilisation de paires de long (ou autres types de base) au lieu d'objets, et l'absence de généricité sur la taille des données, faisant du temps de calcul en moins. Ça donne déjà des bons résultats si on fait presque rien que des calculs.

Si on décide d'utiliser des objets, les rendre mutables permet de soulager un peu le pool d'objets.

... Mais je dois avouer que j'ai jamais su faire des multiplications ou divisions en binaire.

[tchize_]

ouais, ben si les performances sont critiques à ce point => JNI et tu fais faire le calcul par le GPU qui a lui un bus de 128 bits via opencl


Blague à part, si la multiplication / division donne du fil à retordre, je ne vois pas en quoi passer par JNI + C va résoudre le problème. Ton problème d'algorithme restera le même.

Au pire tu prend le code source de la class BigInteger (openjdk), tu remplace son tableau interne de ints par 4 ints et tu déroule manuellement toutes les boucles, et tu fait une nouvelle classe avec ça.