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

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?

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

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 .

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 , 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.

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.

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.)

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).