Il y a une base mathématique "optimale" qui accélérerait le calcul factoriel?
arrière-plan: Juste pour le plaisir, je mettez en œuvre ma propre bibliothèque de Bignum. (-: Est-ce ma première erreur? :-). J'essaie d'expérimenter différentes bases utilisées dans la représentation interne et des tests de régression en imprimant des valeurs exactes (en décimale) pour N factorial (n!). P>
La façon dont ma bibliothèque Bignum représente les entiers et la multiplication, Le temps est proportionnel au nombre total de bits "1" dans la représentation interne n !. En utilisant une base 2, 4, 8, 16, 2 ^ 8, 2 ^ 30, ouc. dans ma représentation interne me donnez tous exactement le même nombre total de bits "1" pour tout numéro particulier. P>
Sauf si j'ai commis une erreur, tout factoriel (n!) Représenté à la base 18 a moins de bits «1» que la même valeur représentée dans la base 10 ou ou la base 16 ou la base 19. Et ainsi (en principe), l'utilisation de la base 18 rendrait ma bibliothèque Bignum plus rapidement que d'utiliser la base 10 ou une base binaire 2 ^ W ou une base 19. Je pense que cela a quelque chose à voir avec le fait que n! est plus court ou a plus de "zéros traînant" ou les deux lorsqu'il est imprimé dans la base 18 que dans la base 10 ou ou la base 16 ou la base 19. Y a-t-il une autre base qui fonctionnerait encore mieux que la base 18? Autrement dit, Y a-t-il une base qui représente n! avec encore moins de bits "1" que la base 18? p>
Ce n'est pas un dup de "Qu'est-ce qu'une base pratique pour un algorithme de bibliothèque et de primalité Bignum?" parce que je soupçonne "la base optimale pour travailler avec des entiers connus pour être de grandes factorielles, avec de nombreux facteurs de 2 et 3" est différent de "la base optimale pour travailler avec des entiers qui n'ont pas de petits facteurs et sont éventuellement premier". (-: accélère les calculs factoriels - peut-être à la charge d'autres types de calculs - ma deuxième erreur?: -) p>
EDIT: Par exemple: P>
(decimal) 16! == (decimal ) == 20,922,789,888,000 // uses decimal 14 "1" bits (dozenal ) == 2,41A,B88,000,000 // uses decimal 10 "1" bits (hexadecimal) == 130,777,758,000 // uses decimal 18 "1" bits (octadecimal) == 5F,8B5,024,000 // uses decimal 14 "1" bits
4 Réponses :
Je ne ferai pas de prétendre que je connais des mathématiques, alors ne prenez pas ma réponse en tant que saint "optimum" que vous recherchez probablement. Si je devrais faire la factorielle aussi rapide que possible, je voudrais essayer une approximation (quelque chose comme une approximation de la sourglage) ou de réduire le nombre de multiplications, car la multiplication est une opération coûteuse. Si vous représentez le nombre en k-Base, vous pouvez simuler la multiplication par K avec l'aide de décalage. Si vous choisissez le 2 base, la moitié des multiplications seront déplacées. Les autres multiplications sont des déplacements et un interrupteur à un bit. Si vous visez à minimiser le nombre de "1" dans votre représentation du nombre, cela dépend de quels nombres vous représentez. Lorsque vous augmentez la base, vous utiliserez moins de «1» S pour représenter un nombre donné, mais vous devrez avoir plus de bits pour chaque commande, ce qui signifie plus de potentiel »1». J'espère que cela aide au moins un peu, sinon, juste demander, je vais essayer de répondre.
Si vous essayez simplement d'optimiser la durée d'exécution pour calculer la factorielle et que la base de la base est le seul paramètre que vous modifiez, la base optimale contiendra probablement de petits facteurs. 60 pourrait être un choix raisonnable. Si vous voulez expérimenter, j'essaierais diverses bases de la forme (2 ^ a) (3 ^ b) (5 ^ c)
Améliorer la vitesse de la multiplication est probablement la meilleure solution. Quel algorithme utilisez-vous pour la multiplication? (Livre d'école, Karatsuba, Toom-Cook, FFT, ...)
Il existe également d'autres facteurs à considérer. Si vous convertissez fréquemment les chiffres en décimale, une base qui est une puissance de 10 rendra la conversion le plus rapidement possible.
Beaucoup (*) Il y a plusieurs années, j'ai écrit une bibliothèque de points flottante de base-6 spécifiquement pour résoudre un problème de multiplication / division répétée de 2 et / ou 3. Mais à moins que vous n'ayez essayé de résoudre un problème spécifique, je pense que vous sera mieux servi en optimisant vos algorithmes en général que d'essayer d'optimiser la factorielle.
casevh
(*) J'ai initialement dit "il y a plusieurs années" jusqu'à ce que je me souvienne que le programme a couru pendant plusieurs jours sur un 12 MHz 80286.
Oui, c'est exactement ce que je fais. Vous avez probablement raison que ces autres considérations avaient probablement un impact beaucoup plus important que le choix de la base, alors peut-être que je pense que cela dépasse cela. Pour autant que je sache, la multiplication de Karatsuba - la multiplication de l'écolier une fois que le facteur est suffisamment faible - est l'algorithme connu le plus rapide lorsque l'un ou l'autre du facteur est inférieur à (très grossièrement, en fonction des compilateurs et du matériel) 300 membres. On dirait que vous avez raison - des bases que j'ai essayées, les bases qui ont le moins de bits «1» lorsque représentent N! sont tous des nombres à 5 polyvalents 5. Merci!
Si par '"1" Bits "Vous voulez dire des chiffres, alors je suggère une base de 256 ou 65536. En d'autres termes, rendez chaque octet / mot un" chiffre "aux fins de votre calcul. L'ordinateur gère régulièrement ces chiffres et est optimisé pour le faire. Vos factoriels seront rapides et d'autres opérations seront également.
Ne pas mentionner l'ordinateur gère une grande partie des conversions d'une base similaire à celles-ci avec facilité. (Intention de rimes)
tandis que du point de vue purement mathématique, la base optimale est e (et après l'arrondi au plus proche entier - 3), d'un point de vue pratique pour une bibliothèque Bignum sur un ordinateur, choisissez une taille de mot de la machine à base pour votre système numérique (2 ^ 32 ou 2 ^ 64). Oui, c'est énorme, mais la couche d'abstraction supérieure de votre système Bignum est le point d'étranglement, les calculs sous-jacents sur les mots de la machine sont la partie rapide, alors déléguez autant de calcul aux instructions de bas niveau de la CPU tout en gardant votre propre travail au minimum.
Et non, ce n'est pas une erreur. C'est un très bon exercice d'apprentissage.
Comment représentez-vous des nombres dans la base e ?
@TrentCl: Pas si difficile mais complètement impraticable. 0, 1, 2 existent normalement. 3 ne pas; Ils représentent des multiples entier de pouvoirs de E qui composent un nombre donné. 1 = 1, 2 = 2, 3 [DEC] = 1e ^ 1 + 0e ^ 0 + 0e ^ (- 1) + 2e ^ (- 2) + 0e ^ (- 3) + 0e ^ (- 4) + 1e ^ - (5) + ... = 10.0201 [E]. 4 [DEC] = 1e ^ 1 + 1e ^ 0 + 1e ^ -1 + 0e ^ -2 + 1e ^ -3 + ... = 11.101 ... [E] - À propos de tous les nombres entiers sauf 0,1,2 serait une fraction. Pendant ce temps, E ^ 5 = 148.413 [DEC] = 100000 [E]
Alors, comment est-ce "optimal" pour calculer des factoriels? Ou qu'est-ce que vous vouliez dire par un "point de vue purement mathématique"?
@TrentCl: Je ne sais pas exactement quelle métrique était pour l'optimalité, mais je pense que c'était quelque chose dans le sens de la quantité de données stockées par rapport à la quantité de données requise pour résoudre le lieu de stockage; C'est un problème théorique de la science informatique de la taille d'un peu; Il y avait des ordinateurs ternaires qui - avec 3 étant plus proches de E de 2 - étaient théoriquement plus optimaux (bien sûr que l'optimalité était hors de la fenêtre avec l'immense croissance de la complexité électronique, c'est pourquoi binaire gagné après tout).
Base E est le "Sweet Spot" théorique qui est absolument purement théorique car pendant que les ratios peuvent parler en faveur de celui-ci. Être une base non entière, il est si horriblement lourd que personne ne prend l'idée de l'utiliser dans la pratique sérieusement. Donc, oui, c'est le "optimum mathématique" de la question titulaire de l'OP, mais loin de l'optimum pratique - qui, en cas de développement d'un système Bignum dans des logiciels, est invariablement le plus grand mot de machine avec support matériel disponible; Et en cas de développement d'une CPU à partir de zéro, aussi proche de e comme une complexité technique / machine permet (= 2.).
Je n'ai jamais vu personne d'utiliser des émoticônes comme des parenthèses comme ça avant :)
Qu'est-ce que vous parlez exactement comme des "bits" lorsque vous parlez de chiffres de base 18? Comment stockez-vous ces chiffres?