Algorithmes basés sur des systèmes de base de nombres?

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:

  • Les tas binomiaux sont basés sur des nombres binarys, et les tas binomiaux de biais les plus complexes sont basés sur des nombres binarys asymésortingques.
  • Certains algorithmes pour générer des permutations ordonnées lexicographiquement sont basés sur le système de nombre factoradic.
  • Les essais peuvent être considérés comme des arbres qui regardent un chiffre de la chaîne à la fois, pour une base appropriée.
  • Les arbres de codage Huffman sont conçus pour que chaque arête de l’arborescence code un zéro ou un dans une représentation binary.
  • Le codage de Fibonacci est utilisé dans la recherche de Fibonacci et pour inverser certains types de logarithmes.

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:

  1. Systèmes de nombres positionnels
  2. Nombres binarys (listes binarys d’access aléatoire, représentations sans chiffres, représentations paresseuses, représentations segmentées)
  3. Chiffres binarys asymésortingques (listes aléatoires d’access aléatoire binarys, désordres binomiaux asymésortingques)
  4. Nombres Trinaires et Quaternaires

Quelques-unes des meilleures astuces, distillées:

  • Distinguer les représentations denses et éparses des nombres (vous voyez généralement cela dans les masortingces ou les graphiques, mais cela s’applique aussi aux nombres!)
  • Les systèmes de numéros redondants (systèmes comportant plusieurs représentations d’un numéro) sont utiles.
  • Si vous arrangez le premier chiffre pour qu’il ne soit pas nul ou pour utiliser une représentation sans zéro, l’extraction de la tête de la structure de données peut être efficace.
  • Evitez les emprunts en cascade (en reprenant la queue de la liste) et transportez (depuis la liste) en segmentant la structure de données

Voici également la liste de référence pour ce chapitre:

  • Guibas, McCreight, Plass et Roberts: Une nouvelle représentation des listes linéaires.
  • Myers: une stack applicative à access aléatoire
  • Carlsson, Munro, Poblete: Une queue binomiale implicite avec un temps d’insertion constant.
  • Kaplan, Tarjan: listes purement fonctionnelles avec caténation via un ralentissement récursif.

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