Réduire le nombre d'opérations sur une simple expression

Question

Disons que je prends un calcul qui implique plus seulement et la multiplication:

(a+b)*(c+d)

qui peut être fait dans bien d'autres façons, par exemple.

a*(c+d) + b*(c+d)
a*c + a*d + b*c + b*d

En termes d'additions et de multiplications le nombre d'opérations nécessaires pour chacun des trois exemples indiqués sont (2,1) (3,2) (3,4) respectivement. Il est clair que, si l'objectif est de réduire le nombre total d'opérations est la première supérieure. Est-il possible, étant donné une expression arbitraire pour trouver l'ordre de calcul qui nécessite le moins d'opérations?

Remarque: Cette question est en cours de re-demandé de SE.math pour la perspicacité et de la perspective de la foule CS.

Answer 1

Qu'est-ce que vous voulez est de générer efficacement tous les possibles expressions algébriques équivalentes, et choisir celui qui prend le moins de coûteux nombre d'étapes (en ajoutant X trois fois est moins cher sur la plupart des machines que de multiplier les X par 3 ).

Il est impossible de le faire, car le nombre de formules « équivalent » est infini.

Cependant, Pelegri-Llopart a trouvé un système pour générer le code optimal étant donné un nombre fixe de règles de réécriture algébriques, appelé "noreferrer BURS" (bottom-up système de réécriture) . Cela a été mis en œuvre dans certains générateurs de code.

En substance, il construit hors ligne un grand automate dont les états suivre l'ensemble des réécritures possibles appliquées. Chaque Etat sait ce qu'il faut générer quand il se produit, de sorte que le temps en ligne pour la génération de code ne coûte pas cher.

Answer 2

Ignorer les pouvoirs des variables et coefficients entiers, ce qui réduit au problème d'un Karnaugh Plan.

K-cartes peut être représenté de somme de produits et de former le produit-de-sommes forment, chacun d'entre eux représente un circuit binaire. Une forme "plus petit nombre d'opérations" représenterait une optimisé circuit binaire , non?

Answer 3

Il y a une règle de Horner pour l'évaluation efficace des polynômes sous forme monôme. Selon lui, étant donné un polynôme de degré n

p (x) = a _n x ⁿ + a _n-1 x ^n-1 + ... + a ₁ x ¹ + a ₀

Seuls n multiplications sont nécessaires (non n + (n-1) + (n-2) + ... + 1 = n (n + 1) / 2, que cela puisse paraître dès le premier coup d'oeil). En effet, le polinomial peut être réécrite comme

p (x) = (((a _n x + a _n-1 ) x + a _n-2 ) x + ... a ₁ ) x + a ₀

Answer 4

Une idée - considérons les variables comme valeurs booléennes et écrire le formulaire maxterm texte du lien

Answer 5

Je ne sais pas sur le cas général, mais il semble que les polynômes d'affacturage améliore les performances. Un exemple d'un cours de science-maquette à distance:

a * x^2 + b * x + c

est améliorée par factorisation des x:

x * (a * x + b) + c