Multiplication rapide d'entiers à l'aide de tables

Je veux parler aux lecteurs d'une astuce de programmation que j'ai rencontrée dans une sorte de livre de traduction qui contient une sélection de ces astuces dans ces temps lointains où il n'était pas encore inventé non seulement l'octet, mais c'est effrayant de dire la pile, et le grand Dijkstra n'a pas encore maudit l'opérateur GOTO (sic, en majuscules).

J'aimais tellement l'astuce par sa simplicité et sa grâce que déjà en ce millénaire j'étais heureuse d'en parler aux étudiants sous la forme de la tâche suivante.

Imaginez que lors du retour de la Lune en 2030, vous avez soudainement découvert que votre ordinateur de bord n'effectue pas correctement les opérations de multiplication d'entiers, ce qui entraînera certainement un accident lors de l'atterrissage.

Dans cette histoire, il n'y a rien de particulièrement fantastique. Rappelons-nous, par exemple, quels problèmes se sont produits une fois avec les processeurs Pentium , et au moment où vous avez été envoyé sur la lune, vous n'aviez pas encore atteint la substitution complète des importations. En général, il est nécessaire de vérifier si les processeurs ont été spécialement percés.

Mais au fait. Vous devez de toute urgence implémenter la multiplication par programme afin qu'elle fonctionne rapidement en temps réel et s'intègre dans une ressource disponible.

Du cours d'arithmétique de l'école, nous rappelons que les nombres à valeurs multiples peuvent être multipliés par une colonne, et le résultat de la multiplication des nombres individuels peut être tiré de la table de multiplication.

Mais seulement si les nombres sont choisis courts (par exemple, 0 et 1), la table de multiplication sera courte et les colonnes longues, et leur calcul prendra beaucoup de temps.

Si, au contraire, nous prenons des nombres longs (par exemple, de 0 à 65535), alors pour l'arithmétique 16 bits
le résultat est extrait directement du tableau et les colonnes sont manquantes. Cependant, la taille de la table pythagoricienne classique se révèle être d'environ 17 Go (4 * 65536 * 65536), si l'on tient compte de la symétrie par rapport à la diagonale, la moitié est d'environ 8,5 Go.

C'est peut-être un peu trop.

Serrez et souvenez-vous de l'algèbre.

$$$(a + b) ^ 2 = a ^ 2 + b ^ 2 + 2ab$(1)

$$$(a - b) ^ 2 = a ^ 2 + b ^ 2 - 2ab$(2)

Soustraire (2) de (1)

$$$(a + b) ^ 2 - (a - b) ^ 2 = 4ab$

et plus loin

$$$a b = ((a + b) ^ 2 - (a - b) ^ 2) / 4$

Ainsi, ayant une table de carrés dans le tableau sqr, nous obtenons

a * b = (sqr [a + b] - sqr [a - b]) / 4 (*)

La taille de la table 8 * (65535 + 65535) est d'environ 8,4 Mo, ce qui peut déjà être acceptable.

La taille de l'élément de table de 8 octets est due au fait que pour le maximum a et b, le carré de leur somme de 4 octets ne convient pas - 2 bits ne suffisent pas.

Ensuite, je vais décrire une amélioration, qui n'était pas dans le livre. Je l'ai inventé moi-même alors que j'écrivais déjà cette note.

Notez que les deux bits les moins significatifs d'un carré pair sont toujours 00 et le carré impair est toujours 01. En revanche, pour toute paire de nombres, leur somme et leur différence ont la même parité.
Par conséquent, dans notre formule (*), le processus de soustraction entre parenthèses ne peut pas avoir de tirets,
associé aux deux bits les moins significatifs. Par conséquent, le contenu des éléments de la table des carrés
Vous pouvez avancer de deux bits vers la droite et ainsi économiser la moitié de la mémoire.

Enfin, nous avons

a * b = sqr4 [a + b] - sqr4 [a - b] (**)

où sqr4 est la table des carrés modifiée.

Dans notre exemple, sa taille est d'environ 4,2 Mo.

Ci-dessous pour illustrer cette approche, le texte du programme Lua est inclus.

function create_multiplier(N) -- N     local sqr4 = {} --   for i = 1, 2 * N - 1 do local temp = 0 for j = 1, i - 1 do --    temp = temp + i - 1 --    end -- ..  "" sqr4[i] = math.floor(temp / 4) --  2  end return --   () function (i, j) if i < j then i, j = j, i end return sqr4[1 + i + j] - sqr4[1 + i - j] end end N = 256 mpy = create_multiplier(N) for i = 0, N - 1 do for j = 0, N - 1 do if i * j ~= mpy(i,j) then print("", i, j, i * j, mpy(i,j)) end end end print(" .") 

Pour les processeurs modernes, il semble raisonnable d'avoir une taille de chiffres qui est un multiple de la taille des octets pour y accéder facilement. Avec des chiffres de 1 octet, la taille de la table n'est que de 1022 octets, ce qui peut permettre d'utiliser cette astuce dans les processeurs 8 bits qui n'ont pas de multiplication matérielle.

Je serai reconnaissant à tous les lecteurs de cette note pour les corrections et commentaires.