Hallo allerseits,
gibt es eine allgemein genutzte Methode um Rechenoperationen (cycles) auszuzählen?
Es geht bei mir um folgendes: Ich arbeite derzeit mit einem ARM Cortex M4 Prozessor @168MHz und muss ein paar Funktionen in C programmieren. Dazu möchte ich aber bei einigen Berechnungen Vorbetrachtungen implementieren und herausfinden, ob meine Vorbetrachtungen wirklich effizienter sind. Um darüber eine Entscheidung zu treffen, würde ich einfach beide Methoden implementieren und entsprechend die Cycles vergleichen.
Kleines Beispiel: Was ist schneller zu berechnen:
p6-1 oder (p2-1)*(p2(p2+1)+1)
Der Square-and-Multiply Algorithmus liefert für 610= 1102 die Operationen: SMSM (S quadrieren, M multiplizieren):
Initialisierung mit 1:
p6-1=(((12)*p)2*p)2 -1
Ich habe also 4 Multiplikationen (M) und eine Addition (A) (bei 168 MHz ist das wie teuer? ) bzw. wenn ich 1^2 ignoriere, erhalte ich 3 M und 1A.
Andererseits berechne ich nur x:=p2 und kann diesen Wert entsprechend auslesen.
(p2-1)*(p2(p2+1)+1) = (x-1)(x(x+1)+1)
Ich habe also für x, x2 und das Verrechnen der Klammern jeweils eine Multiplikation = 2
hinzu kommen 3 Additionen.
Insgesamt kann ich aber auch die erste Methode dadurch verbessern, indem ich p2 in einem LUT speichere. Dadurch reduziert sich SQM zu: (x*p)2 -1, also 2 M, 1 A und ist damit günstiger.
Ich gehe davon aus, dass eine M weniger teuer ist, als 2A, daher wäre die Vorbetrachtung günstiger (im Trad-of mit Speicher). Btw. p wird zwischen 256 und 521 Bit groß sein.
Aber es gibt ja auch andere Methoden, wie die Sliding Window Methode, oder Montgomery Ladder..[1] (ich operiere letztendlich in einem endlichen Körper der Charakteristik p und Ordnung p^n-1 (F_q mit q=p^n)
[1] https://en.wikipedia.org/wiki/Expone..._window_method
gibt es eine allgemein genutzte Methode um Rechenoperationen (cycles) auszuzählen?
Es geht bei mir um folgendes: Ich arbeite derzeit mit einem ARM Cortex M4 Prozessor @168MHz und muss ein paar Funktionen in C programmieren. Dazu möchte ich aber bei einigen Berechnungen Vorbetrachtungen implementieren und herausfinden, ob meine Vorbetrachtungen wirklich effizienter sind. Um darüber eine Entscheidung zu treffen, würde ich einfach beide Methoden implementieren und entsprechend die Cycles vergleichen.
Kleines Beispiel: Was ist schneller zu berechnen:
p6-1 oder (p2-1)*(p2(p2+1)+1)
Der Square-and-Multiply Algorithmus liefert für 610= 1102 die Operationen: SMSM (S quadrieren, M multiplizieren):
Initialisierung mit 1:
p6-1=(((12)*p)2*p)2 -1
Ich habe also 4 Multiplikationen (M) und eine Addition (A) (bei 168 MHz ist das wie teuer? ) bzw. wenn ich 1^2 ignoriere, erhalte ich 3 M und 1A.
Andererseits berechne ich nur x:=p2 und kann diesen Wert entsprechend auslesen.
(p2-1)*(p2(p2+1)+1) = (x-1)(x(x+1)+1)
Ich habe also für x, x2 und das Verrechnen der Klammern jeweils eine Multiplikation = 2
hinzu kommen 3 Additionen.
Insgesamt kann ich aber auch die erste Methode dadurch verbessern, indem ich p2 in einem LUT speichere. Dadurch reduziert sich SQM zu: (x*p)2 -1, also 2 M, 1 A und ist damit günstiger.
Ich gehe davon aus, dass eine M weniger teuer ist, als 2A, daher wäre die Vorbetrachtung günstiger (im Trad-of mit Speicher). Btw. p wird zwischen 256 und 521 Bit groß sein.
Aber es gibt ja auch andere Methoden, wie die Sliding Window Methode, oder Montgomery Ladder..[1] (ich operiere letztendlich in einem endlichen Körper der Charakteristik p und Ordnung p^n-1 (F_q mit q=p^n)
[1] https://en.wikipedia.org/wiki/Expone..._window_method
Kommentar