Discussion :

[CSharpN]

Bonjour,

J'aurai aimé savoir si quelqu'un connaitrait une méthode plus rapide que l'opérateur / pour faire une division entre deux BigInteger.

Je dois faire 15000 divisions de ce type et ca me prend plus de 20sec et comme je vais devoir en faire plus je me demandais s'il existait une autre méthode.

Cordialement

[spottt]

Salut,

As-tu essayé en faisant une multiplication par l'inverse de ton diviseur ?
Je ne sais pas si c'est plus rapide qu'une division, mais ça vaut le coup d'essayer...

[CSharpN]

L'inverse de mon diviseur ne sera pas un entier donc je dois assigner á une autre variable á chaque boucle (car ce n'est pas toujours le meme diviseur) donc ca prend plus de temps et comme mon diviseur est un BigInteger lorsaue je prend l'inverse mon calcul devient "arrondi" et je n'ai plus le bon résultat.

Merci quand meme

[Bluedeep]

Salut,

As-tu essayé en faisant une multiplication par l'inverse de ton diviseur ?

Il a dit qu'il utilisait des BigInteger.

[Bluedeep]

Bonjour,

Je dois faire 15000 divisions de ce type et ca me prend plus de 20sec et comme je vais devoir en faire plus je me demandais s'il existait une autre méthode.

Non; c'est le problème avec les BigInteger, il n'existe pas d'instructions de manipulation native de ces structures dans le système (alors que le processeur a des instructions spécifiques pour les nombres à virgules flottante, par exemple), et la bibliothèque doit faire des opérations décomposées avec des "long" combinés en opérant les retenues dans le code => c'est long.

[spottt]

Il a dit qu'il utilisait des BigInteger.

Yes, l'expression a été plus vite que la réflexion, désolé.

[Bluedeep]

Yes, l'expression a été plus vite que la réflexion, désolé.

Pas grave, ça arrive

[DonQuiche]

Bonjour.

Soit tes entiers sont vraiment énormes (>1E1000000), soit le problème vient d'ailleurs. Parce que si je veux bien croire que la division de BigInteger soit plus lente qu'une division normale, là on serait à plus de 1ms par division ?! Cela voudrait dire qu'il faut plus d'un million d'opérations par division, c'est ridicule.

Je doute donc fortement que cette pauvre division soit la responsable.

[sisqo60]

Bonjour,

Tout à fait d'accord, envoie nous ton code et on pourra voir et même voire tester

[CSharpN]

Bonjour,

Je me suis trompé, c'est 150000 divisions pas 15000 et je suis sure que le probleme vient de la division puisque j'ai mis le reste de mon programme en commentaire pour faire les mesures de temps.

Mes nombres sont grands donc je suppose que je peux pas faire mieux que / .

Je ne peux pas poster mon code car je ne l'ai pas sur cet ordinateur, si vous pensez qu'il est vraiment nécessaire je peux essayer d'aller le récupérer.

Cordialement

[DonQuiche]

Même en multipliant par dix, c'est beaucoup trop lent. Pourrais-tu nous donner un ordre de grandeur pour tes nombres et le contexte (que représentent ces nombres) ? Et, oui, personnellement j'aimerais voir le code, il doit y avoir un truc.

[CSharpN]

Pardon c'est ma faute je ne donne pas les bonnes informations.

En comptant toutes mes boucles correctement je fais un peu plus de 19 200 000 cette division (qui change á chaque fois bien sur).

les 153 600 premieres fois j'ai P/Q avec P : 4 octets et Q : 2 octets
Puis j'ajoute 2 octets á P et 1 á Q toutes les 153 600

(Je fini avec P vers 128 et Q vers 64 je crois)

[DonQuiche]

Ok, ça change pas mal de choses.
Donc nous sommes à une microseconde par division, soit 1000 instructions environ. C'est malheureusement très raisonnable. On pourrait envisager de réécrire un BigInteger spécialisé pour ton cas et on pourrait peut-être ainsi diviser par 2 à 8 le temps de calcul (surtout en louchant du côté du code unsafe et de Mono.Simd pour une implémentation encore plus efficace). C'est fastidieux toutefois et les résultats ne sont pas garantis. Un peu plus simple et sans doute au moins aussi efficace, la GNU MP : développer des wrappers pour celle-ci ou carrément porter la partie calcul du code en C/C++ non-managé en s'appuyant sur elle.

Une autre approche plus rudimentaire serait, si ton problème est parallélisable, d'utiliser tous les coeurs du processeur. Le gain théorique serait de 2 à 8 selon les machines. Voire, à supposer que le problème s'y prête, avoir recours au GPU. Évidemment cette dernière solution serait de loin la plus complexe à mettre en oeuvre, même en s'appuyant sur des biblios avancées (comme la dernière-née des biblios de MS pour dotnet et dont le nom m'échappe), mais le gain potentiel est énorme (disons 20x à 100x).

Enfin, tout simplement, n'y a t-il pas un algorithme plus efficace pour résoudre ce problème ? C'est généralement la première chose à considérer.

[CSharpN]

Bonjour,

Malheureusement mon probleme n'est pas parallélisable puisque j'ai besoin du résultat précédent pour passer á l'instance suivante de ma boucle, je suppose donc que les solutions proposées dans le deuxieme paragraphe ne sont pas envisageable (dommage car x20 aurait été parfait).

Ceci dit j'ai commencé le c# il y a seulement 1 mois donc je connais pas encore comment passer en c/c++ (j'ai lu quelques choses dessus) donc je vais essayer de voir si je peux passer par lá.

Pour ce qui est de changer l'algorithme, malheureusement non, j'ai déjá fait pas mal de recherche dessus et il semblerai que ca soit la seule maniere de faire.

Merci d'avoir pris le temps de me répondre malgré mes explications un peu bancale parfois.

Cordialement

[youtpout978]

Bonjour,

si on voyait déjà ton code on pourrait peut être t'aider pour l'optimiser.