n'importe quel document qui indique exactement à quelle plage de nombres les BigIntegers .NET sont-ils destinés?

12

Je joue avec le .NET BigInteger et, fondamentalement, je me demande quel nombre - une réponse estimée serait bien - est le point de déviation de la courbe de (le graphique de (augmentation du temps requis pour les opérations) vs (valeur de BigInteger))?

ou sont-ils conçus sans un tel écart de telle sorte que si nous traçons l'augmentation du temps requis pour les opérations par rapport à la valeur de BigInteger de 1 à l'infini, nous aurons une courbe lisse tout le long?

par exemple, en supposant que les tableaux sont conçus avec une capacité de gérer 50 éléments. cela signifie que si j'ai 1 article, les opérations sont f (1) fois. et quand j'ai 2 articles, les opérations sont temps f (2). si j'ai 50 articles, les opérations sont de temps f (50). mais comme il est conçu pour gérer seulement 50 éléments, les opérations effectuées lorsque nous avons 51 éléments seront g (51) où g (51)> f (51).

Si elle est correctement mise en œuvre, la complexité de l'arithmétique BigInteger doit être une courbe lisse. Par exemple, la complexité temporelle de la multiplication doit être O (NM) où N est le nombre de chiffres dans le premier multiplicande et M est le nombre de chiffres dans le second multiplicande. Bien sûr, il existe des limites pratiques en ce sens que vous pouvez choisir N ​​et M si grands que les nombres ne rentreraient pas dans votre machine.

Existe-t-il / quelqu'un connaît-il des documents affirmant qu'il est mis en œuvre en tant que tel?

Pacerier
la source
3
@Down électeurs, les votes vers le bas ne veulent rien dire si vous ne pouvez pas laisser un commentaire expliquant pourquoi la question n'est pas une bonne question. J'ai voté pour cela car je n'y vois aucun problème.
The Muffin Man
Je n'ai pas déçu, mais je ne sais pas quelle est la question ici. Voulez-vous connaître la complexité d'exécution / mémoire des opérations sur bigints (addition, multiplication, division, etc.)?
nikie
par exemple, en supposant que les tableaux sont conçus avec une capacité de gérer 50 éléments. cela signifie que si j'ai 1 élément et que les opérations sont f (1) fois. et quand j'ai 2 articles, les opérations sont temps f (2). si j'ai 50 articles, les opérations sont de temps f (50). mais comme il est conçu pour gérer seulement 50 articles, les opérations effectuées lorsque nous avons 51 articles seront g (51) où g (51)> f (51)
Pacerier
@Charles E. Grant oui! C'est ce dont je suis en train de parler. la question est la suivante: existe-t-il / quelqu'un connaît-il des documents affirmant qu'il est mis en œuvre en tant que tel?
Pacerier
@Paceier J'ai déplacé mon commentaire vers ma réponse et ajouté un lien vers un document traitant exactement de cela.
Charles E. Grant

Réponses:

7

Tout nombre pouvant éventuellement être supérieur à ULong.MaxValue ou inférieur à Long.MinValue doit être représenté à l'aide de BigInteger.

Si NON (Long.MinValue <= X <= ULong.MaxValue) Alors BigInteger

BigInteger est pour un nombre trop grand que les primitives normales peuvent gérer.

Par exemple, si votre entier est en dehors de la plage de Long, vous devez probablement utiliser BigInteger. Ces cas sont cependant très rares et l'utilisation de ces classes a des frais généraux significativement plus élevés que leurs homologues primitifs.

Par exemple, il a une longlargeur de 64 bits et peut contenir la plage: -9,223,372,036,854,775,808 à 9,223,372,036,854,775,80. ulong peut contenir de 0 à 18 446 744 073 709 551 615. Si vos nombres sont plus grands ou plus petits que cela, BigInteger est votre seule option

La seule fois où je les ai vus utilisés dans une application réelle était une application starchartting.

Voir aussi: Plages primitives dans .NET

Malfist
la source
Je veux dire, bien sûr, je sais que nous devrions utiliser des primitives normales chaque fois que nous le pouvons. je veux dire que je sais qu'il peut supporter 100k fois plus grand que ULong.MaxValue mais est-il conçu avec cette gamme à l'esprit, ou est-il conçu avec cette gamme déclarée "exigence hors de l'ordinaire"?
Pacerier
5
Vous ne pouvez pas représenter un nombre même supérieur à ULong.MaxValue sans utiliser BigInteger, c'est donc pour cela. Tout nombre pouvant éventuellement devenir plus grand que ULong.MaxValue doit être un BigInteger.
Malfist
bien sûr, il existe des moyens de représenter des nombres supérieurs à ULong.MaxValue et sans utiliser BigInteger. je pourrais simplement écrire une structure personnalisée qui se compose d'un ULong et d'un booléen et d'un alto que je peux représenter jusqu'à deux fois d'ULong.MaxValue
Pacerier
Oui, mais c'est beaucoup moins compliqué d'utiliser BigInteger, et ce ne serait probablement pas beaucoup plus rapide, voire plus rapide, et ce ne serait pas aussi flexible que BigInteger. Vous pouvez également représenter de très grands nombres avec un tableau de booléens, mais c'est tout simplement trop compliqué.
Malfist
2
@Mavrik, il a changé cela en une question complètement différente de celle à laquelle j'ai répondu.
Malfist
4

Dans un certain sens, le point de BigInteger n'est pas tant la taille absolue que la précision illimitée. Les nombres à virgule flottante peuvent également être très importants, mais leur précision est limitée. BigInteger vous permet d'effectuer des calculs arithmétiques sans vous soucier des erreurs d'arrondi ou du débordement. Le prix à payer est qu'il est des centaines de fois plus lent que l'arithmétique avec des entiers ordinaires ou des nombres à virgule flottante.

Comme d'autres l'ont souligné, ulong peut contenir entre 0 et 18 446 744 073 709 551 615, et tant que vous restez dans cette plage, vous pouvez faire une arithmétique exacte. Si vous allez même 1 au-delà de cette plage, vous obtiendrez un débordement, donc la réponse à votre question est d'utiliser BigInteger si vous avez besoin d'une arithmétique exacte et il y a une possibilité que tout résultat intermédiaire dépasse 184446744 073709551515.

La plupart des problèmes en science, en ingénierie et en finance peuvent vivre avec les approximations forcées par les nombres à virgule flottante, et ne peuvent pas se permettre le coût en temps de l'arithmétique BigInteger. La plupart des calculs commerciaux ne peuvent pas vivre avec les approximations de l'arithmétique à virgule flottante, mais fonctionnent dans la plage de 0 à 18 446 744 073 709 551 615, afin qu'ils puissent utiliser l'arithmétique ordinaire. BigInteger est nécessaire lors de l'utilisation d'algorithmes de la théorie des nombres qui incluent des choses comme la cryptographie (pensez aux nombres premiers à 50 chiffres). Il est également parfois utilisé dans des applications commerciales lorsque des calculs exacts sont nécessaires, la vitesse n'est pas trop importante et la mise en place d'un système de virgule décimale correct est trop difficile.

Si elle est correctement mise en œuvre, la complexité de l'arithmétique BigInteger doit être une courbe lisse. Par exemple, la complexité temporelle de la multiplication doit être O (NM) où N est le nombre de chiffres dans le premier multiplicande et M est le nombre de chiffres dans le second multiplicande. Bien sûr, il existe des limites pratiques en ce sens que vous pouvez choisir N ​​et M si grands que les nombres ne rentreraient pas dans votre machine.

Si vous recherchez sur Google "Complexité de calcul de biginteger", vous obtiendrez plus de références que vous ne pourrez en serrer la baguette. Celui qui répond directement à votre question est le suivant: Comparaison de deux packages arithmétiques de précision arbitraire .

Charles E. Grant
la source
4

Limite de mémoire

BigInteger s'appuie sur la baie int pour le stockage. En supposant cela, la limite théorique du nombre maximal, que BigInteger est capable de représenter, peut être dérivée de la taille maximale du tableau disponible dans .net. Il y a un sujet SO sur les tableaux ici: Trouver la quantité de mémoire que je peux allouer pour un tableau en C # .

En supposant que nous connaissons la taille maximale du tableau, nous pouvons estimer le nombre maximal que BigInteger peut représenter: (2 ^ 32) ^ max_array_size, où:

  • 2 ^ 32 - nombre maximum dans la cellule du tableau (int)
  • max_array_size - taille maximale autorisée du tableau int qui est limitée par la taille de l'objet de 2 Go

Cela donne un nombre avec 600 millions de chiffres décimaux.

Limite de performance

Quant aux performances, BigInteger utilise l' algorithme de Karatsuba pour la multiplication et l'algorithme linéaire pour l'ajout. La complexité de la multiplication est 3 * n ^ 1,585, cela signifie qu'elle évoluera assez bien même pour les grands nombres ( graphique de complexité ), mais vous pouvez toujours réduire les performances en fonction de la taille de la RAM et du cache du processeur.

Pour autant, comme la taille maximale des nombres est limitée à 2 Go, sur la machine de descente, vous ne verrez pas d'écart de performance inattendu, mais fonctionner sur 600 millions de chiffres sera très lent.

Valera Kolupaev
la source
c'est une information merveilleuse, mais où est votre source que BigInteger s'appuie sur des tableaux int?
Pacerier
Je viens de creuser dans les sources .net en utilisant dotPeek. Il semble que le nombre lui-même soit stocké dans uint [] _data de la structure BigInteger.
Valera Kolupaev
* Mis à jour avec une réponse plus détaillée, cependant, je ne trouve aucun code source .net, auquel je peux faire référence, à l'exception des extraits de code décompilés.
Valera Kolupaev
Il me semble qu'il existe un algorithme de multiplication standard dans .NET tel qu'il peut être déterminé à partir d'ILSpy: Multiplication BigInteger .NET
Ivan Kochurkin
1

La limite est la taille de votre mémoire (et le temps dont vous disposez). Donc, vous pouvez avoir de très gros chiffres. Comme l'a dit Kevin, en cryptographie, il faut multiplier ou exposer des nombres avec quelques milliers de chiffres (binaires), et cela est possible sans aucun problème.

Bien sûr, souvent les algorithmes ralentissent à mesure que les nombres augmentent, mais pas beaucoup plus lentement.

Lorsque vous utilisez des nombres dans la plage des méga-chiffres, vous voudrez peut-être penser à d'autres solutions, car le calcul avec eux devient également lent.

Paŭlo Ebermann
la source
0

Il y a quelques utilisations au sein de la communauté scientifique (ie la distance entre les galaxies, le nombre d'atomes dans un champ d'herbe, etc.)

Dave Wise
la source
euh pour ne pas être impoli .. mais comment cette réponse se rapporte-t-elle à la question?
Pacerier
2
La question, telle qu'elle est écrite, sonne comme s'il cherchait un exemple concret expliquant pourquoi un tel type de données devrait être créé.
Dave Wise
une meilleure reformulation serait "BigInteger est-il vraiment adapté pour des nombres aussi grands que 10 ^ 30"?
Pacerier
Pour cela, je ferais mieux d'utiliser doubleou float- vous n'avez pas la précision nécessaire de toute façon.
Paŭlo Ebermann
une meilleure reformulation serait "BigInteger est-il vraiment adapté pour des nombres aussi grands que 10 ^ 30 lorsque nous avons besoin de la précision"?
Pacerier
0

Comme le suggère la réponse de Kevin Cline, les BigNumbers ont été ajoutés aux bibliothèques .NET principalement parce qu'ils étaient nécessaires comme blocs de construction pour de nombreux algorithmes cryptographiques modernes (signatures numériques, cryptage de clé publique / privée, etc.). De nombreux algorithmes cryptographiques modernes impliquent des calculs sur des valeurs entières avec des tailles allant jusqu'à plusieurs milliers de bits. Étant donné que la classe BigNumber décrit une classe bien définie et utile, ils ont décidé de la rendre publique (plutôt que de la conserver en tant que détail interne des API cryptographiques).

Stephen C. Steel
la source
btw vient de savoir où est votre source que BigNumbers a été ajouté aux bibliothèques .NET principalement parce qu'ils étaient nécessaires comme bloc de construction pour de nombreux algorithmes cryptographiques modernes (et devraient donc être capables de prendre en charge des valeurs allant jusqu'à plusieurs milliers de bits)?
Pacerier