J’ai remarqué récemment qu’il existe de nombreux algorithmes basés en partie ou en totalité sur des utilisations intelligentes des nombres dans des bases créatives. Par exemple:
Ma question est la suivante: quels sont les autres algorithmes qui utilisent un système numérique intelligent comme étape clé de leur intuition ou de leur preuve? . Je pense à organiser une conférence sur le sujet, donc plus je devrai d’exemples, mieux ce sera.
Chris Okasaki a un très bon chapitre dans son livre Structures de données purement fonctionnelles qui traite des “représentations numériques”: essentiellement, prenez une représentation d’un nombre et convertissez-le en une structure de données. Pour donner une saveur, voici les sections de ce chapitre:
Quelques-unes des meilleures astuces, distillées:
Voici également la liste de référence pour ce chapitre:
“Les nombres ternaires peuvent être utilisés pour transmettre des structures similaires comme un sortingangle Sierpinski ou un ensemble Cantor convenablement.” la source
“Les nombres quaternaires sont utilisés dans la représentation des courbes de Hilbert 2D.” la source
“Le système de numération quater-imaginaire a été proposé pour la première fois par Donald Knuth en 1955 dans une soumission à une recherche scientifique de lycée. Il s’agit d’un système de numération positionnel non standard qui utilise le nombre imaginaire 2i comme pour représenter chaque nombre complexe en utilisant uniquement les chiffres 0, 1, 2 et 3. ” la source
“Les chiffres romains sont un système biquinaire.” la source
“Senary peut être considéré comme utile dans l’étude des nombres premiers puisque tous les nombres premiers, exprimés en base six, autres que 2 et 3, ont 1 ou 5 comme chiffre final.” la source
“Sexagesimal (base 60) est un système de numération avec soixante comme base. Il est né avec les anciens Sumériens au 3ème millénaire avant JC, il a été transmis aux anciens Babyloniens, et il est toujours utilisé – sous une forme modifiée – pour mesurer le temps, les angles et les coordonnées géographiques qui sont des angles. ” la source
etc…
Cette liste est un bon sharepoint départ.
J’ai lu votre question l’autre jour et j’ai rencontré aujourd’hui un problème: comment générer tous les partitions d’un ensemble? La solution qui m’est venue, et que j’ai utilisée (peut-être à cause de votre question) était la suivante:
Pour un ensemble avec (n) éléments, où j’ai besoin de (p) partitions, comptez parmi tous les nombres (n) de chiffres dans la base (p).
Chaque numéro correspond à un partitionnement. Chaque chiffre correspond à un élément de l’ensemble et la valeur du chiffre indique la partition dans laquelle l’élément doit être placé.
Ce n’est pas incroyable, mais c’est chouette. C’est complet, ne provoque aucune redondance et utilise des bases arbitraires. La base que vous utilisez dépend du problème de partitionnement spécifique.
Je suis récemment tombé sur un algorithme génial pour générer des sous-ensembles dans l’ordre lexicographique basé sur les représentations binarys des nombres entre 0 et 2 n – 1. Il utilise les bits des nombres pour déterminer quels éléments doivent être choisis pour les ensembles générés pour les mettre en ordre lexicographique. Si vous êtes curieux, j’ai un article posté ici .
De plus, de nombreux algorithmes sont basés sur la mise à l’échelle (comme une version faiblement polynomiale de l’algorithme Ford-Fulkerson max-flow), qui utilise la représentation binary des nombres dans le problème d’entrée pour affiner progressivement une approximation grossière en une solution complète.
Pas exactement un système de base intelligent mais une utilisation intelligente du système de base: les séquences de Van der Corput sont des séquences à faible divergence formées en inversant la représentation base-n des nombres. Ils sont utilisés pour construire les séquences 2-D Halton qui ressemblent à ceci .
Je me souviens vaguement de quelque chose à propos des systèmes à double base pour accélérer une multiplication masortingcielle.
Le système à double base est un système redondant qui utilise deux bases pour un numéro.
n = Sum(i=1 --> l){ c_i * 2^{a_i} * 3 ^ {b_i}, where c in {-1,1}
Redondant signifie qu’un nombre peut être spécifié de plusieurs manières.
Vous pouvez rechercher l’article “Algorithme hybride pour le calcul du polynôme masortingciel” par Vassil Dimitrov, Todor Cooklev.
Essayer de donner le meilleur aperçu possible, je peux.
Ils essayaient de calculer le polynôme de masortingce G(N,A) = I + A + ... + A^{N-1}
.
En remplaçant N est le composé G(N,A) = G(J,A) * G(K, A^J)
, si nous appliquons pour J = 2, nous obtenons:
/ (I + A) * G(K, A^2) , if N = 2K G(N,A) = | \ I + (A + A^2) * G(K, A^2) , if N = 2K + 1
aussi,
/ (I + A + A^2) * G(K, A^3) , if N = 3K G(N,A) = | I + (A + A^2 + A^3) * G(K, A^3) , if N = 3K + 1 \ I + A * (A + A^2 + A^3) * G(K, A^3) , if N = 3K + 2
Comme il est “évident” (en plaisantant) que certaines de ces équations sont rapides dans le premier système et certaines meilleures dans le second, il est donc judicieux de choisir le meilleur en fonction de N
Mais cela nécessiterait un fonctionnement modulo rapide pour 2 et 3. Voici pourquoi la double base entre en jeu: vous pouvez en gros faire rapidement l’opération modulo pour les deux en vous donnant un système combiné:
/ (I + A + A^2) * G(K, A^3) , if N = 0 or 3 mod 6 G(N,A) = | I + (A + A^2 + A^3) * G(K, A^3) , if N = 1 or 4 mod 6 | (I + A) * G(3K + 1, A^2) , if N = 2 mod 6 \ I + (A + A^2) * G(3K + 2, A^2) , if N = 5 mod 6
Regardez l’article pour une meilleure explication, car je ne suis pas un expert dans ce domaine.
RadixSort peut utiliser plusieurs bases numériques. http://en.wikipedia.org/wiki/Radix_sort Implémentation intéressante d’un bucketSort.
Voici un bon post sur l’utilisation de nombres ternaires pour résoudre le problème de la «contrefaçon de pièce» (où vous devez détecter une seule pièce contrefaite dans un sac de pièces ordinaires, en utilisant une balance le moins possible)
Les chaînes de hachage (par exemple dans l’algorithme Rabin-Karp ) évaluent souvent la chaîne sous la forme d’un nombre base-b composé de n chiffres (où n est la longueur de la chaîne et b une base assez large). Par exemple, la chaîne “ABCD” peut être hachée comme suit:
'A'*b^3+'B'*b^2+'C'*b^1+'D'*b^0
En substituant les valeurs ASCII pour les caractères et en prenant b pour être 256, cela devient,
65*256^3+66*256^2+67*256^1+68*256^0
Bien que, dans la plupart des applications pratiques, la valeur obtenue soit modulo par un nombre raisonnablement suffisant pour que le résultat soit suffisamment petit.
L’exposition par quadrature est basée sur la représentation binary de l’exposant.
Dans Hackers Delight
(un livre que tout programmeur doit connaître à mes yeux), il existe un chapitre complet sur les bases inhabituelles, comme -2 comme base (oui, bases négatives à droite) ou -1 + i (i comme unité imaginaire sqrt (-1)). ) comme base. Aussi, bon calcul, quelle est la meilleure base (en termes de conception matérielle, pour tous ceux qui ne veulent pas le lire: la solution de l’équation est e, donc vous pouvez aller avec 2 ou 3, 3 serait un peu mieux (facteur 1,056 fois mieux que 2) – mais est plus technique que pratique).
D’autres choses me viennent à l’esprit: le compteur gris (vous ne comptez que 1 bit dans le système pour réduire les problèmes de métastabilité) ou la généralisation du codage Huffmann déjà mentionné – le codage arithmétique.
La cryptographie fait largement appel aux anneaux entiers (arithmatique modulaire) et aux corps finis, dont les opérations reposent intuitivement sur le comportement des polynômes à coefficients entiers.
J’aime beaucoup celui-ci pour convertir des nombres binarys en codes gris: http://www.masortingxlab-examples.com/gray-code.html
Bonne question La liste est longue en effet. Dire l’heure est une simple instance de bases mixtes (jours | heures | minutes | secondes | am / pm)
J’ai créé un framework n-tuple d’énumération de méta-base si cela vous intéresse. C’est du sucre syntaxique très doux pour les systèmes de numérotation de base. Ce n’est pas encore sorti. Envoyez mon nom d’utilisateur par courrier électronique (à l’adresse gmail).
Un de mes favoris utilisant la base 2 est le codage arithmétique . C’est inhabituel parce que le cœur de l’algorithme utilise des représentations de nombres entre 0 et 1 en binary.
Peut-être que c’est le cas.