Je travaille sur une puce avec un seul noyau (le stm32f103c8t6) et je veux évaluer un polynôme jusqu'à un exposant prédéterminé, donc f(x) = a0 + a1*x +a2*x^2 +...+an*x^n où n est connu au moment de la compilation.
Les coefficients a0 ... an changeront pendant l'exécution et certains d'entre eux sont très susceptibles de devenir nuls et je veux trouver un moyen de les ignorer lors de l'évaluation de f (x) . Notez que la plupart seront différents de zéro. Idéalement, je voudrais réécrire f (x) pendant l'exécution pour que les coefficients qui sont nuls ne soient plus dans la fonction, mais je ne veux pas entrer dans le territoire de code auto-modifiable (à moins qu'il n'y ait un moyen facile de le faire en C ++) . La micropuce est capable de multiplier une seule instruction, donc toute solution équivalente à avoir des instructions if pour vérifier si le coefficient est zéro serait la même ou plus lente que d'évaluer simplement l'expression dans son ensemble.
Les évaluations se produiront plusieurs fois, il est donc utile de sauver un seul cycle d'évaluation de la fonction. Actuellement, je n'ai pas de solution viable pour cela et j'évalue simplement le polynôme dans son ensemble.
J'écris en C ++ pour la puce, bien que je travaille actuellement sur les algorithmes en python car il est plus facile de tracer les résultats et ainsi de suite je n'ai pas de code pour le problème.
3 Réponses :
Utilisation d'une machine à états finis. Vous devez écrire le code pour chaque état possible. Mais c'est probablement le moyen le plus rapide de calculer.
Ceci est un exemple, il utilise des exemples de fonctions mathématiques et un exemple de valeur d'itérations. OP doit fournir ses propres fonctions mathématiques et sa propre valeur d'itération pour chaque état.
#include <iostream>
int main(int argc, char *argv[]){
/* MAX_COEFFICIENTS <-- states == 2^coefficients */
const int MAX_COEFFICIENTS = 3;
int coefficientsv[] = {1, 0, 3}; /* {A, B, C} */
int coefficientsc = sizeof coefficientsv / sizeof coefficientsv[0];
if(coefficientsc > MAX_COEFFICIENTS) return -1; /* Out of bounds! */
register int A = 0, B = 0, C = 0;
for(int i = 0; i < coefficientsc; i++){
if(i == 0) A = coefficientsv[i];
else if(i == 1) B = coefficientsv[i];
else if(i == 2) C = coefficientsv[i];
}
register long polycalc = 0; /* or use just int, if int is big enough */
register int iteration = 1000; /* example value */
/* state truth table */
/* A B C */
/* 0 0 0 goto STATE_0 */
/* 1 0 0 goto STATE_A */
/* 0 1 0 goto STATE_B */
/* 1 1 0 goto STATE_AB */
/* 0 0 1 goto STATE_C */
/* 1 0 1 goto STATE_AC */
/* 0 1 1 goto STATE_BC */
/* 1 1 1 goto STATE_ABC */
STATE_SELECT:
if(!A && !B && !C) goto STATE_0;
if( A && !B && !C) goto STATE_A;
if(!A && B && !C) goto STATE_B;
if( A && B && !C) goto STATE_AB;
if(!A && !B && C) goto STATE_C;
if( A && !B && C) goto STATE_AC;
if(!A && B && C) goto STATE_BC;
if( A && B && C) goto STATE_ABC;
STATE_0:
while(iteration){
polycalc = 0;
iteration--;
}
goto END;
STATE_A:
while(iteration){
polycalc = A;
iteration--;
}
goto END;
STATE_B:
while(iteration){
polycalc = B * B;
iteration--;
}
goto END;
STATE_AB:
while(iteration){
polycalc = A + B * B;;
iteration--;
}
goto END;
STATE_C:
while(iteration){
polycalc = C * C * C;
iteration--;
}
goto END;
STATE_AC:
while(iteration){
polycalc = A + C * C * C;
iteration--;
}
goto END;
STATE_BC:
while(iteration){
polycalc = B * B + C * C * C;
iteration--;
}
goto END;
STATE_ABC:
while(iteration){
polycalc = A + B * B + C * C * C;
iteration--;
}
/* Example: Pseudo-Code */
/* Maybe your first calculation has shown that C becomes 0. */
/* So simply use "goto STATE_AB", maybe set some variables. */
/* In another example, you only know that some coefficient */
/* has become 0, but you don't know which one, */
/* so use "goto STATE_SELECT", maybe set some variables too. */
goto END;
END:
std::cout << polycalc << std::endl;
return 0;
}
L'OP a écrit " le polynôme serait évalué comme a0+a1x+a2x^2 ". Votre code semble calculer a0 + a1^2 + a2^3 place, 1000 fois. Comment est-ce même lié, et encore moins «le plus rapide »?
@dxiv Relisez quel est le problème de l'OP. L'objectif principal est d'éliminer le "si coefficient == 0 alors ne calcule pas" , ce que fait clairement mon programme. J'utilise des exemples de valeurs et des exemples de fonctions mathématiques, qui doivent être modifiés par OP.
1) L'OP cherche à optimiser l'évaluation d'un polynôme pour différentes valeurs de la variable, que la réponse ne mentionne même pas. 2) En supposant que vous ayez résolu cela, l'approche ne se met pas à l'échelle, car le nombre d'observations croît de façon exponentielle avec le degré du polynôme. 3) Même pour un quadratique avec seulement 2 ^ 1 + 1 = 3 coefficients, le code est sous-optimal, il y a une boucle for inutile, puis 2 ^ 3 = 8 if s + goto s au lieu de 1 switch ou une fonction dispatch. Je ne voterai pas si vous publiez quelque chose au moins à égalité avec la méthode par défaut de Horner .
Maintenant, disons que certains de ces coefficients sont 0 à la suite de certaines mises à jour et / ou entrées de l'utilisateur, idéalement, je voudrais supprimer ces termes lors de l'évaluation de la fonction afin de ne pas avoir à calculer x ^ 5, puis simplement le jeter car le coefficient était 0. ... Je veux aussi le faire le plus efficacement possible (sans entrer dans le domaine de l'écriture de code auto-modificateur), donc idéalement pas de déclarations if pour vérifier si chaque coefficient est 0 avant d'évaluer chaque terme ou quelque chose comme ça mais peut-être une chaîne de magie de pointeur ou quelque chose? OP utilise une machine embarquée où chaque cycle CPU compte!
@dxiv PS Faire cela sur une puce où chaque cycle compte, donc je ne veux pas gaspiller de cycles. Je vais l'évaluer plusieurs fois, donc même en économisant un seul cycle, chaque itération s'additionne rapidement ... Il y a l'itération, votre boucle for "inutile". Le problème est peut-être qu'OP n'a pas été très clair dans la rédaction de sa question. PPS Selon vous, qu'est-ce qu'un interrupteur avec 8 boîtiers?
La boucle for inutile est celle qui fait A = coefficientsv[0]; et similaire pour B , C Et, par exemple, switch((A == 0) + ((B == 0) << 1) + ((C == 0) << 2)) avec le case 0: au case 7:
Non, ce n'est pas le "inutile" for , car vous aurez toujours au moins 1 if pour déterminer si la valeur est nulle ou non nulle. Autant que je sache, OP lit un polynôme et fait plusieurs opérations dessus, il l'itère, c'est pourquoi j'utilisais des états. Vous pensez vraiment que ce changement est plus rapide? Ça ne l'est pas.
Peut-être plus rapide, certainement pas pire, et je vais en rester là car cela ne semble aller nulle part.
@dxiv Désolé, mais vous n'avez aucune idée du fonctionnement d'un processeur. Votre commutateur effectue plusieurs comparaisons et opérations mathématiques et plusieurs sauts et même des décalages binaires, tandis que j'utilise des jonctions NON-ET suivies d'un seul saut.
Dans un premier temps, rappelez-vous qu'il est généralement préférable de calculer les polynômes d'une autre manière que la présentation habituelle:
float value = x;
for (int i = 1; i < max_powers; ++i) {
x_powers[i] = value;
value *= x;
}
x_powers[max_powers] = value;
La première ligne est la présentation conventionnelle, et a le problème que vous pouvez finir par abuser de votre plage dynamique.
La deuxième ligne tend à éviter les problèmes numériques liés au calcul des puissances successives de x, et est une manière assez conventionnelle de calculer réellement des polynômes. Malheureusement, il a toujours une longue chaîne de dépendances, ce qui limite le parallélisme au niveau des instructions que vous pouvez en tirer.
La troisième ligne évite la longue chaîne de dépendances, et est également parfaitement adaptée pour exploiter une unité vectorielle si vous en avez une.
D'après votre discussion sur les commentaires, il semble que vous travaillez avec un processeur intégré de faible puissance. Supposons donc qu'aucun processeur vectoriel et peu d'ILP ne soit disponible de toute façon, et adaptons la deuxième ligne. (J'écrirai ceci en termes de virgule flottante, mais il devrait être facilement adaptable à virgule fixe).
Tout d'abord, la méthode simple, sans essayer de sauter les coefficients nuls:
int max_powers = 0;
for (power: inc_powers) {
if (power > max_powers) { max_powers = power; }
}
std::vector<float> x_powers(max_powers + 1);
Maintenant, la méthode intelligente: en supposant que vos coefficients sont fixes, vous pouvez les prétraiter pour déterminer les puissances de x vous pouvez ignorer, et donc les puissances incrémentielles que vous devrez calculer (une fois, à l'avance):
int i = a.size() - 1;
float result = a[i];
for (int i = 0; i < inc_powers.size(); ++i) {
result = a[inc_indices[i]] + x_powers[inc_powers[i]] * result;
}
return result;
Pour évaluer le polynôme:
// compute powers between nonzero coefficients
int max_idx = a.size() - 1;
assert(a[max_idx] != 0); // you should not have leading zeroes in the first place
std::vector<int> inc_powers;
std::vector<int> inc_indices;
int inc_pow = 0;
int i = max_idx;
while (i > 0) {
-- i;
++ inc_pow;
if (a[i] != 0 || i == 0) {
inc_powers.push_back(inc_pow);
inc_indices.push_back(i);
inc_pow = 0;
}
}
Vous aurez besoin de calculer x_powers - un tableau de puissances de x utilisé dans le calcul polynomial ci-dessus. Il existe probablement un moyen intelligent de calculer et de spécifier un calcul minimum pour générer exactement les puissances de x dont vous aurez besoin, mais il sera probablement à peu près aussi rapide (pour les petits polynômes sur un processeur lent sans ILP) pour les générer de manière incrémentielle. Vous devrez déterminer (une fois, à l'avance) le nombre de pouvoirs dont vous avez besoin:
int max_idx = a.size() - 1;
float result = a[max_idx];
int i = max_idx;
while (i > 0) {
-- i;
result = a[i] + x * result;
}
return result;
Puis, pour chaque évaluation, calculez-les successivement comme préparation pour le calcul de la valeur polynomiale:
polynomial = a0 + a1*x + a2*x^2 + a3*x^3 + a4*x^4 + a5*x^5 + ...
= a0 + x*(a1 + x*(a2 + x*(a3 + x*(a4 + x*(a5 + ... )...)
= (a0 + x*a1) + x^2*(a2 + x*a3) + x^4*((a4 + x*a5) + x^2*(a6 + x*a7)) + ...
(J'ai configuré les choses pour que x_powers[i] == x^i et x_powers[0] soient pas utilisés. J'espère que cela facilitera le suivi des choses; bien sûr, dans la pratique, vous n'avez pas à le faire de cette façon. .)
(Dans un esprit similaire, notez que vous pouvez simplement copier les coefficients différents de zéro au lieu d'utiliser un index - mais cela pourrait être plus instructif en l'état, donc je vais le laisser ainsi)
Enfin, puisque vous êtes préoccupé par les performances, vous devez en fait évaluer à la fois la version simple et la version intelligente pour vous assurer que votre «amélioration» est en fait une amélioration.
La boucle for ne va-t-elle pas ajouter une instruction if avant chaque itération dans la boucle pendant l'évaluation? Ou le compilateur changera-t-il cela en une séquence d'instructions «fixes» si je dis au compilateur d'optimiser la vitesse? :)
En réfléchissant un peu plus à cette solution, le compilateur ne peut pas le convertir en un ensemble fixe d'instructions, n'est-ce pas? Puisque max_powers n'est pas connu au moment de la compilation? Alors cette solution serait exactement la même que de simplement vérifier if (coeff != 0) avant d'évaluer chaque terme?
Il y aura un test par coefficient différent de zéro dans l'évaluation polynomiale. Si (comme cela semble probable pour le cas d'utilisation de la question), il existe plusieurs évaluations avec le même ensemble de coefficients, vous avez le potentiel de gagner du temps.
Je ne veux pas dire lors du calcul des inc_powers et inc_indices , je veux dire lors de l'évaluation réelle du polynôme lui-même. Dans la boucle for (int i = 0; i < inc_powers.size(); ++i) qui évalue le polynôme, puisque inc_powers.size() ne peut pas être connu au moment de la compilation, la boucle doit vérifier la condition à chaque fois dans la boucle, d'où l'ajout d'un "if statement" pour chaque coefficient qui est calculé. Puisque la multiplication est la même vitesse (un cycle) qu'une instruction if, cela ne sera-t-il pas aussi rapide ou plus lent que l'évaluation «directe»?
Le but de l'étape de prétraitement est de sauter les coefficients 0 (comme demandé dans la question). La taille de inc_powers et inc_indices est le nombre de coefficients non nuls . Supposons que votre polynôme n'a que des coefficients non nuls impairs: alors inc_powers et inc_indices auront à peu près la moitié de la taille de a , et votre évaluation "intelligente" aura environ la moitié du nombre de tests.
Bien sûr, mais je n'aurai probablement que 1 ou 2 sur 6 coefficients qui sont 0. Donc, le contrôle de condition et ++i serait plus cher que de simplement faire ces deux multiplications 0, non? Je devrais peut-être mettre à jour la question à nouveau pour spécifier que seuls quelques coefficients seront nuls, désolé à ce sujet. Je commence à penser que je devrais simplement essayer de m'assurer qu'il n'y a pas de coefficients nuls pour commencer plutôt que de trouver des moyens avancés pour les gérer: P
Vous avez raison, bien sûr: si vous n'attendez qu'un petit nombre de coefficients 0, vous ne gagnerez pas de temps en les sautant. En fait, si vous avez un petit nombre total fixe de coefficients, le déroulement de la boucle est une évidence (facile à trouver pour le compilateur), et est probablement impossible à battre avec quelque chose d'intelligent.
Ok, je demandais seulement parce que cela ressemblait à un problème "normal" qui devrait avoir une solution simple comme utiliser une sorte de pointeur de fonction ou quelque chose, mais je suppose que la seule façon de procéder "correctement" serait de modifier la fonction d'évaluation sur runtime et c'est bien au-delà de mes compétences, je ne suis pas très bon avec l'assemblage :(
Si vous avez généré un nombre exponentiel de fonctions, une pour chaque modèle possible de 0-coefficients, vous pouvez sélectionner un pointeur de fonction vers l'une des 2^n fonctions. Cela pourrait même être pratique pour n==6 -> 2^n==64 si vous avez la place. Cependant, je ne suis pas sûr que cela conviendrait à un processeur intégré.
Hmm, ça pourrait être une option :) Au niveau de la mémoire, j'ai quelque chose comme 128 ko, donc pas beaucoup mais pas rien non plus. Puisque j'aurai une assez bonne idée des termes qui pourraient être nuls, je n'aurai peut-être pas besoin de tant de fonctions. Les coefficients sont pour une équation différentielle, donc je sais avec certitude lequel ne sera pas nul, ce ne sera que des termes d'ordre supérieur dont je ne suis pas sûr. Existe-t-il vraiment aucun moyen d'écrire une fonction au moment de l'exécution en C ++? : S
@BeaconofWierd doing those two 0 multiplications Cela donne l'impression que l'évaluation suivrait le modèle a_k * x^k , mais ce n'est pas le cas (sauf peut-être dans l'implémentation naïve). Dans la méthode standard de Horner (2e ligne de la réponse), tous les coefficients sauf le dernier sont additionnés par quelque chose et non multipliés par rien. En d'autres termes, le nombre de multiplications requises ne change pas si vous sautez d'une manière ou d'une autre les coefficients nuls, juste le nombre d'additions. Pour optimiser au-delà de cela, vous auriez besoin de quelques astuces sur le calcul des puissances de x travers les «écarts».
@dxiv Le microprocesseur sur lequel je travaille prend le même temps (un cycle) pour préformer une multiplication qu'une addition, donc économiser une addition ou une multiplication est équivalent.
@BeaconofWierd Dans ce cas, il est peu probable que vous puissiez faire une optimisation significative, à l'exception du code auto-modifiable ou de 2 ^ N copies statiques de codes personnalisés. Le simple fait de lire / d'utiliser les coefficients de quelque manière que ce soit donne une limite inférieure de N cycles. Le schéma de Horner donne une borne supérieure de 2N cycles. Entre ces deux limites, toute vérification d'exécution et / ou branche nécessitera probablement au moins un cycle supplémentaire par étape, de sorte que la limite 2N sera difficile à battre.
@dxiv Vous avez probablement raison, même si 2 ^ N copies statiques pourraient en valoir la peine puisque mon N ne sera pas si grand :) Le meilleur moyen est probablement de m'assurer de ne pas inclure de termes qui pourraient devenir zéro , j'espère qu'ils n'auront pas beaucoup d'impact sur les performances du système ... Espérons que: P
Connexes: théorème de Rice et quelques théorèmes de Robinson . IIRC votre problème est indécidable ou du moins insoluble , et lié au problème P versus NP . Essayez d'utiliser REDUCE .
Notez que l'intelligence artificielle est probablement un meilleur endroit pour demander
Vous pouvez essayer des techniques d' interprétation abstraite et d'évaluation partielle
Etudiez le code source de GCC , de MILEPOST GCC et de l' analyseur statique Clang . Les deux font de telles optimisations du compilateur (avec plus ou moins de succès). Pensez également à utiliser Frama-C .
Je suis sûr que ce problème a déjà une solution mais je ne l'ai pas trouvée
et si vous en trouvez un, vous obtiendrez le prix Turing .
Lisez le livre de J.Pitrat, Artificial Beings: the Conscience of a Conscious Machine (ISBN 978-1848211018). Cela donne des informations utiles sur votre problème.
Pensez à l'algorithme que vous utiliseriez pour cela. Vous calculeriez (disons) x ^ 3 à partir de x ^ 2 * x, et ainsi de suite, il est donc inutile de se soucier de zéro coefficients.
Êtes-vous préoccupé par les performances de
a * x ^ nsiavaut 0? Si vous finissez par écrire du code en C ++, vous n'avez pas à vous en soucier.Faire cela sur une puce où chaque cycle compte, donc je ne veux pas gaspiller de cycles. Je vais l'évaluer plusieurs fois, donc même en économisant un seul cycle, chaque itération s'additionne rapidement, c'est pourquoi je ne veux pas perdre de cycles à calculer 0 * x ^ n. Peu importe si j'évalue le polynôme entier "séquentiellement", je vais quand même gaspiller un cycle pour chaque coefficient égal à 0.
Pouvez-vous s'il vous plaît fournir votre implémentation technique réelle (votre code source de votre calcul et le code source de l'utilisation de ces calculs)? Alors on peut vous donner une réponse adéquate? PS Je pense qu'une machine à états finis répondrait à votre problème, mais je ne suis pas sûr à 100%, car je ne peux pas ignorer tout votre problème technique.
@BeaconofWierd
a microchip where every cycle countsQue diriez-vous d'octets, alors? Les astuces intelligentes qui sauvent les cycles ont tendance à exiger plus de code et / ou de mémoire. Vous devez fournir un contexte, ainsi que la mise en œuvre de base que vous espérez améliorer.