BigInt pour Standard ML/NJ

Question

Existe-t-il un équivalent Java BigInt pour Standard ML? Le type int normal renvoie une exception lorsqu'il déborde.

Answer 1

Oui, voir la structure IntInf.

Answer 2

L'équivalent BigInt s'appelle LargeInt. Voir these lecture notes pour voir quelques fonctions sur la façon de convertir entre int (aka Int) et LargeInt.

Answer 3

Eh bien, int met une limite désagréable sur des choses comme le calcul des permutations. SML a besoin d'un grand type de données numérique plus naturel à utiliser.

Answer 4

La norme officielle de SML'97 basis library introduit un zoo de structures comme Int, IntInf, Int32, Int64, Largeint etc.

les utiliser dans la pratique de faire fonctionner les choses comme prévu, et les faire travailler efficacement , vous devez regarder de près la mise en œuvre SML à portée de main.

• Une famille de mises en œuvre imite la mise en mémoire de C et Java, donc Int32 sera vraiment un mot machine 32 bits (mais avec vérification de débordement) et Int64 un mot machine 64 bits. SML/NJ en est un exemple notable, et son petit int arithmentic est rapide, mais son gros int arithmétique est lent.

• Une autre famille d'implémentations provient du contexte du calcul symbolique (LISP ou Computer Algebra), où Poly/ML est un exemple notable. Ici, vous avez Int = IntInf = LargeInt par défaut, et l'implémentation utilise d'abord (partie de) le mot machine native comme approximation, jusqu'à ce qu'il déborde, puis passe à des entiers vraiment gros qui sont alloués sur le tas (comme des valeurs encadrées). Poly/ML utilise la bibliothèque GNU MP pour cette grande partie.

Ainsi Int/IntInf est très efficace aussi longtemps que votre application est sur les entiers, non mots machine d'une taille spécifique: Int32 dans le modèle symbolique ne tient pas dans un seul mot sur le matériel 32 bits en raison de la bits de balise supplémentaires requis. Donc, certains algorithmes qui concernent réellement l'arithmétique des mots vont se dégrader, par exemple SHA1 sur le matériel 32 bits. D'autre part, la mise à niveau implicite d'un int int, de plus petit que than wordsize, vous donne quelque chose de mieux que BigInt en Java, car vous n'aurez pas besoin de la surcharge de l'objet pour les petites valeurs: être juste un peu de modèle dans un registre (avec bit de balise supplémentaire), mais pas une boîte lourde sur le tas.

Answer 5

Bien que ce ne soit pas exactement ce que vous demandiez, vous ne voulez pas d'équivalent à la classe Java BigInt. La classe BigInt de Java implémente O (n^2) temps pour la multiplication (multipliant essentiellement la façon dont elle est enseignée à l'école primaire), au lieu de O (n log n), ce qui est possible. Ceci est vraiment important, car beaucoup de programmation BigInt triviale ne fonctionne tout simplement pas avec la version n^2.