Devoirs arithmétiques

Lyoshenka, Lyoshenka, faites-moi une faveur!
Apprenez, Alyoshenka, la table de multiplication!
Agnia Barto


Première tâche pour une première niveleuse. Un nombre positif est donné. Vous devez multiplier par lui un autre nombre, inconnu à l'avance. La question est, comment les nobles Dons conseilleront-ils de le faire ??? Un développeur expérimenté dira sûrement, disent-ils l'homme, mettre le multiplicateur et ne vous inquiétez pas mon cerveau. Et peut-être que ce sera fondamentalement faux! En plus des monstres d'Alterra et de Xilinx, il y a aussi une famille aussi merveilleuse que l' iCE-40 de Lattice . Ultra micro consommant. Très bon marché. Oui, le problème est qu'ils sont douloureusement petits et, hélas, il n'y a pas de multiplicateurs là-bas. Je l'ai rencontré il y a environ 4 ans lorsque j'ai porté un certain codec ADPCM de l'assembleur adsp-2185 vers un tel cristal.

Non, sans multiplicateur à usage général (pour deux variables), cela n'aurait certainement pas pu être fait. J'ai dû le faire avec des stylos et il a pris la moitié du cristal. Le problème est qu'il a battu à chaque pas, c'est-à-dire pas de fenêtres du tout. Et en plus de la multiplication des variables dans l'algorithme, il y avait des coefficients fixes, qui devaient également être multipliés. Et il n'y avait aucun moyen d'utiliser le multiplicateur pour cela, il n'y avait tout simplement plus de fenêtre. Et puisque la lutte dans le projet a traversé chaque cellule, bien sûr, j'étais très intéressé par la façon d'esquiver, et en utilisant les propriétés de ces coefficients, faites le schéma optimal de multiplication par eux (pas un multiplicateur à usage général, mais un dispositif pour multiplier par un nombre donné!). Eh bien, comme un rêve complet devenu réalité - de sorte que les schémas de multiplication par différents coefficients tirent le meilleur parti de certaines ressources cristallines communes.

Ainsi, de la tâche de la première année, nous sommes passés doucement à la tâche de l'ingénieur et du mathématicien. Comment construire un schéma de multiplication optimal pour un nombre spécifique donné?

Rappelons un peu comment on multiplie généralement le nombre A par B.

1. Pour commencer, mettez le résultat à zéro.
2. Passons en revue les bits A.
3. Si en décharge 0, on ne fait rien.
4. Si dans le bit 1, nous décalons B du nombre de bits correspondant et ajoutons au résultat.

Au total, moins il y a d'unités A dans les chiffres, plus il est facile de le multiplier. La multiplication par 2, 4 ou 8 est facile. Seul un changement est nécessaire. Un peu plus difficile à multiplier par 3, 5 ou 10. Il faudra un ajout. Encore plus difficile à multiplier par 11. Plus il y a d'unités, plus c'est difficile.

Eh bien, qu'en est-il de multiplier par 255? Jusqu'à 8 unités, une tâche cauchemardesque, non? Et voici les figurines! Faisons une feinte délicate avec nos oreilles. Multipliez notre B par 256 (c'est-à-dire, décalez-le de 8 chiffres) et soustrayez-le du résultat. Il s'avère que malgré le look formidable, multiplier par 255 est aussi facile que multiplier par 10. Il est tout aussi facile de multiplier par 254, et par 240, et par 224 (si vous voulez, vérifiez!).

Au total, la soustraction aide à la multiplication. Rappelez-vous cette pensée précieuse. En attendant, nous appelons la difficulté d'un nombre le nombre minimum d'opérations d'addition (ou de soustraction) nécessaires pour le multiplier. Les décalages ne sont pas pris en compte. Car dans le contexte du problème (nous avons des circuits, pas de programmation!) Ils sont obtenus pour rien. Formulons une affirmation évidente mais utile:

La difficulté d'un nombre est inférieure ou égale au nombre d'unités dans sa notation binaire.
En fait, si nous multiplions honnêtement sans astuces de soustraction, comme nous l'avons enseigné à l'école, le nombre d'additions sera égal au nombre d'unités en binaire A. Et si on commence à tromper et d'ailleurs, on a de la chance, alors on va réduire le nombre d'opérations.

Une conséquence intéressante de cette affirmation:
La difficulté de tout nombre à n bits est toujours strictement inférieure à n .
Après tout, le plus grand nombre d'unités dans un nombre à n chiffres est n , pour un nombre comme 255. D'un autre côté, il est clair que la mise au point, comme en multipliant par 255, nous pouvons répéter pour les nombres de n'importe quelle capacité. Cela ouvre des perspectives d'optimisation des multiplicateurs à usage général.

Donnons à notre raisonnement un aspect plus régulier. Pour commencer, ayons déjà une sorte de schéma de multiplication par A. Nous prenons comme unité. Ensuite, tous les termes se déplacent, s'additionnent et se soustraient de telle manière que le résultat est le même A. Au total, notre schéma de multiplication par A n'est rien d'autre qu'une représentation du nombre A sous la forme de la somme de puissances de deux dans laquelle les termes peuvent être à la fois avec le signe + et avec le signe - . Et vous pouvez regrouper les termes positifs et négatifs, et dire que le schéma est décrit par la différence de certains nombres A + et A- , égaux à A. C'est mauvais ... Les membres de la différence peuvent être arbitrairement grands. Pensons s'il y a des considérations pour les limiter?
Tout d'abord, nous notons que chaque puissance de deux ne peut entrer dans le circuit qu'une seule fois. En fait, si elle entre deux fois avec le même signe, celui-ci peut être remplacé par une puissance de deux par une unité de plus. Si elle entre deux fois avec des signes différents, ils sont mutuellement soustraits. Au total, le schéma est très similaire à la représentation binaire habituelle de A. La seule différence est que ses «bits» (ci-après nous les appellerons trits ) peuvent prendre non pas deux, mais trois valeurs: 1, 0 et -1.

Total Si A est un nombre binaire à n bits, le schéma de multiplication par celui-ci est décrit par la somme:

$$

$$A = {t_m} 2 ^ m + {t_ {m-1}} 2 ^ {m-1} + .... + {t_1} 2 + {t_0}$$

où $$${t_i}$- trits, prenant les valeurs 1, 0 et -1, et m est un nombre inconnu.

À l'avenir, nous appellerons une telle expression un schéma ternaire ou simplement un schéma ou un schéma de multiplication pour le nombre A.

Essayons de trouver m . Comme le montre l'exemple avec multiplication par 255, m n'est en aucun cas inférieur à n . Voyons si elle peut être égale à n + 1 .
Soit A, comme précédemment, un nombre positif à n chiffres. Ensuite, le schéma de multiplication est défini comme suit:

$$

$$A = {t_ {n + 1}} 2 ^ {n + 1} + {t_ {n}} 2 ^ {n} + {t_ {n-1}} 2 ^ {n-1} .... + {t_1} 2 + {t_0}$$

Rappelez-vous que $$$2 ^ k + 2 ^ {k-1} + .... + 2 + 1 = 2 ^ {k + 1} -1$
Par conséquent, le trit le plus élevé ne peut en aucun cas être égal à -1. En effet, même si tous les autres sont 1, la somme sera toujours -1. Et par la condition A est positive. Maintenant, laissez le trit supérieur être 1. Mais dans ce cas, le trit suivant devrait être -1. Sinon, le montant sera trop important. En fait, si le prochain trit est 0, la somme ne sera pas inférieure à $$$2 ^ {n + 1} - (2 ^ {n-1} + ... + 1) = 2 ^ {n + 1} - (2 ^ n - 1) = 2 ^ n + 1$
Alors que n- bit A n'est pas plus $$ . Mais si le trit supérieur est 1, et le -1 suivant, alors la somme des deux membres supérieurs est $$$2 ^ {n + 1} -2 ^ n = 2 ^ n$. Donc, le trit supérieur est 0.

Ainsi, une déclaration importante est prouvée: m = n .

En d'autres termes, pour représenter tout schéma de multiplication par un n- bit A , n + 1 puissances de deux suffisent - de 0 à n (un de plus que la représentation binaire), ce qui nous sauve immédiatement de l'infini.

Vous pouvez maintenant essayer de calculer les difficultés (voir ci-dessus) de tout nombre spécifique. La chose la plus simple est de faire ce que nous faisons en écrivant des nombres binaires dans l'ordre. Premièrement, nous n'avons pas de bits ici mais des trites (trois valeurs possibles), deuxièmement, certaines combinaisons de trites donnent des nombres négatifs et elles doivent être rejetées, troisièmement, certaines combinaisons peuvent donner des nombres coïncidents. Cela signifie que pour un tel nombre, il existe plusieurs régimes.

Nous allons écrire en python. Non pas parce que je suis tellement fan de lui, mais parce qu'il est extrêmement pratique de travailler avec lui dans des cahiers jupyter. Pour commencer, nous écrivons la classe TriScheme qui fonctionne avec les schémas ternaires présentés ci-dessus, la fonction allSchemes, qui calcule avec elle tous les schémas de nombres d'une taille de bit donnée par une énumération simple, et la fonction printSchemes qui imprime le résultat:


Nous calculons les schémas pour tous les nombres à 4 bits:

0 0 1 [00000]
1 1 5 [0000+, 000 + -, 00 + -, 0 + ---, + ----]
2 1 4 [000 + 0, 00 + -0, 0 + - 0, + --- 0]
3 2 7 [000 ++, 00 + - +, 00 + 0-, 0 + - +, 0 + -0-, + --- +, + - 0-]
4 1 3 [00 + 00, 0 + -00, + - 00]
5 2 8 [00 + 0 +, 00 ++ -, 0 + -0 +, 0 + - + -, 0 + 0--, + - 0+, + - + -, + -0--]
6 2 5 [00 ++ 0, 0 + - + 0, 0 + 0-0, + - + 0, + -0-0]
7 2 7 [00 +++, 0 + - ++, 0 + 0- +, 0 + 00-, + - ++, + -0- +, + -00-]
8 1 2 [0 + 000, + -000]
9 2 7 [0 + 00 +, 0 + 0 + -, 0 ++ -, + -00 +, + -0 + -, + - + -, +0 ---]
10 2 5 [0 + 0 + 0, 0 ++ - 0, + -0 + 0, + - + - 0, + 0-0]
11 3 8 [0 + 0 ++, 0 ++ - +, 0 ++ 0-, + -0 ++, + - + - +, + - + 0-, +0 - +, + 0-0 -]
12 2 3 [0 ++ 00, + - + 00, + 0-00]
13 3 7 [0 ++ 0 +, 0 +++ -, + - + 0+, + - ++ -, + 0-0 +, +0 - + -, + 00--]
14 2 4 [0 +++ 0, + - ++ 0, + 0- + 0, + 00-0]
15 2 5 [0 ++++, + - +++, +0 - ++, + 00- +, + 000-]

Voici au début de la ligne un nombre, suivi de sa difficulté (le nombre minimum d'éléments non nuls dans le circuit), puis le nombre de circuits, et enfin une liste de circuits.

Dans le schéma, + désigne 1, 0 - 0 et - - -1. Le plus vieux trit sur la gauche (comme avec l'orthographe habituelle des nombres)

Le tableau montre tout d'abord que seuls les nombres 13 et 11 ont la difficulté 3 (le maximum pour les nombres 4 bits, comme prouvé ci-dessus). Et deuxièmement, que le nombre de schémas différents pour chaque numéro est assez important. Cela suggère, premièrement, que la multiplication est le plus souvent l'opération est beaucoup plus simple que ce qu'on nous a enseigné à l'école. Et d'autre part, que pour la mise en œuvre de dispositifs de multiplication par plusieurs constantes utilisant des ressources cristallines communes, le choix des circuits est assez large. Les données sur les nombres plus longs sont encore plus intéressantes. Ainsi, pour les nombres de 14 bits, la difficulté maximale est de 8. Et le nombre maximal de circuits est de 937.

Tout irait bien, mais l'algorithme ci-dessus est trop cher. Sa complexité augmente à mesure que $$ en fonction de la longueur des nombres n . Pour 8 chiffres compte instantanément. Pendant 14 minutes. Pendant 16 heures. Si vous avez besoin de lire les circuits POUR TOUS les nombres de n bits, rien d'autre ne peut être fait que de le réécrire en C et de prendre un ordinateur plus puissant. Cependant, l'algorithme est parfaitement parallélisé et peut certainement être exécuté sur le GPU ou sur le cluster.

Pour la conception de pièces de fer spécifiques, des listes de schémas pour des numéros spécifiques sont généralement requises. Et TOUT est souhaitable, et pas seulement optimal. Pour lequel choisir peut dépendre des circonstances (par exemple, un dispositif pour multiplier par plusieurs constantes). Et ici, vous pouvez proposer un algorithme beaucoup plus humain. Encore une fois, nous rappelons la remarquable égalité: $$$2 ^ k + 2 ^ {k-1} + .... + 2 + 1 = 2 ^ {k + 1} -1$.

Dans le contexte de la tâche, cela signifie ce qui suit. Supposons que plusieurs schémas trit supérieurs soient connus. Tous les trits mineurs commençant à la position k sont inconnus et sont auparavant considérés comme égaux à zéro. Ensuite, en changeant les trits inconnus de quelque façon que ce soit, nous changerons la valeur du circuit de plus / moins $$$2 ^ {k + 1} -1$. De plus, avec l'avancement vers les trits inférieurs, la valeur de cette incertitude diminue. Cela vous permet de rechercher des schémas par approximations successives, trit après trit.

Soit un nombre positif A. Nous devons trouver tous les schémas pour cela parmi les nombres à n bits. La valeur absolue de la différence entre A et la valeur d'un certain circuit est appelée l' erreur du circuit. Pour commencer, nous prenons un schéma n + 1- bits décrivant des nombres à n bits, tous inconnus et initialement définis comme étant nuls. Et commençons à définir les trits, un par un, en commençant par l'ancien. En position k- ème, le circuit peut générer trois nouveaux motifs - avec des valeurs de k-trit 1, 0 et -1. Nous ne laissons dans la liste des régimes de continuation que ceux d'entre eux dont l'erreur ne dépasse pas $$ . Avec la liste de circuits résultante, passons à l'étape à la position k-1 . Ainsi, dans la liste résultante (à la position 0), il y aura TOUS les schémas possibles dont la valeur est A. Écrivons une telle fonction calcSchemes.


Et enfin, la vente promise des rêves.

Dans ce projet, il y avait deux coefficients à multiplier: 16351 et 16318. En utilisant calcSchemes, nous trouvons les schémas de ces coefficients:


Nous avons de la chance! Les deux facteurs ont des difficultés 3. Nous choisissons les schémas optimaux pour les deux:
Pour 16318 + 0000000-0000-0 et pour 16351 - + 00000000-0000- . Nous avons encore eu de la chance! Faites attention aux queues des régimes. Ils pour 16318 et 16351 ne diffèrent que par un décalage à gauche d'une position. Ainsi, le dispositif multipliant par 16318 et 16351, ne comprend qu'un seul multiplexeur supplémentaire, commutant l'opérande décalé et non décalé à l'entrée de l'additionneur.

Voyons le résultat. Nous écrivons au veril trois options pour le dispositif de multiplication par 16318 et 16351:

1. Option «école» (uniquement les ajouts et les quarts)
2. Circuit optimal
3. Schéma optimal utilisant des ressources partagées

Pour les trois options, nous effectuons la synthèse et voyons combien de ressources cristallines seront dépensées pour chacune d'entre elles.


Les trois options fonctionnent correctement, en multipliant à 0 à l'entrée s par 16318 et à 1 à 16351. En même temps, yosys donne 488 cellules pour la version scolaire, 206 pour la version optimale et 202 pour la variante avec des ressources partagées. il optimise, bien qu'il y ait encore une différence dans 4 cellules. Comme vous pouvez le voir, la différence avec l'option scolaire est très décente.

Enfin, enfin. Peut-être, il semblerait inutile que quelqu'un clôture un tel jardin, uniquement pour réaliser simplement que 16318 = 16384-64-2 et 16351 = 16384-32-1. Cependant, premièrement, les chiffres peuvent être plus compliqués. Deuxièmement, si l'appareil doit multiplier plusieurs nombres, il est loin d'être évident que des schémas optimaux doivent être pris. J'ai juste eu de la chance dans ce projet. En général, un programme de recherche de circuits peut être très utile. J'espère que l'article est utile à quelqu'un. Et celui qui l'a lu, j'espère ne paniquera pas si vous avez besoin de vous multiplier, mais il n'y a pas de multiplicateur.