3. Optimierung: Addition und Shifting

Optimierung: Addition und Shifting

  • J

    Jede Java-Cryptlib ist noch schneller. Ich glaube, die Implementierung ist sicherlich noch nicht so gut, dass nur noch Assembler aushelfen könnte.

    0
  • ?

    Aber ohne Assembler musst du solange mit Deinem Code rumspielen, bis der Compiler von selbst auf die Idee kommt, Add-With-Carry zu benutzen. Da gehst Du echt effizienter mit Deiner begrenzten Zeit um, wenn Du gleich die "optimale" Lösung hinschreibst.

    0
  • C

    Welche Java-Bibliotheken meinst du denn? Und bist du dir auch sicher, dass die hinterher nicht einfach native-calls machen?
    PS: Du machst da etwas rekursiv? Das solltest du vielleicht zu erst mal fixen. 😉

    0
  • V

    Wird

    if(result <= storage[n] && summand.storage[n] != 0 || result <= summand.storage[n] && storage[n] != 0)
          carry = 1;

    nicht einfach zu

    if(result < storage[n])
          carry = 1;

    ?

    Ansonsten würde ich mir eine Funktion addWithCarry oder so bauen, die den Assemblerbefehl mappt, mit #ifdef für msvc und gcc auf x86 und #else mit if(<). Aber keine Schleifen oder sowas in asm machen, sondern immer nur mal einen einzigen Befehl.

    0
  • C
    Mod 

    carry = carry ? result <= storage[n] : result < storage[n];
    0
  • C

    volkard: Das geht leider nicht, weil das Carry-Bit mit addiert wird. Nur bei der ersten Addition würde es funktionieren. Und das mit dem Assembler-Befehl mappen ist auch nicht so leicht, weil man sich ja sicher sein muss, was der letzte Arithmetische Befehl war. Letztlich hat man eigentlich nur die Chance das passend zur Schlüsselgröße direkt in Assembler zu implementieren, das sieht dann mehr oder weniger so aus:

    add
adc
adc
adc
...

    Was, wie man sicher auf einen Blick erkennen kann, relativ effizient ist. Schade dass C++ da keinen eingebauten Mechanismus für hat, der Compilern erlaubt solchen Code aus Templates zu generieren. Na ja, vielleicht für C++17. 🤡

    0
  • J

    Assembler ist für mich nicht wirklich eine Option. Dadurch, dass ich den Code möglichst plattformunabhängig brauche (und es für Visual Studio z.B. nicht mal mehr Inline-Assembler für x64 gibt (ja, der Code soll auch im 64-bit Modus laufen)) und er für int32, int64, int16 etc. Basistypen laufen sollte.

    Campers Vorschlag ist sehr gut, er hat die Modulare Exponentiation um gute 10% beschleunigt. Vermutlich kann ich jetzt aber nicht mehr aus der Addition herauskratzen.

    In der Tat ist der Karatsuba-Algorithmus rekursiv. Den aber mithilfe von std::stack iterativ zu implementieren ist nicht gerade einfach und ich bin mir nicht sicher, ob das am Ende wirklich schneller ist (gleichwohl die Komplexität wohl besser sein sollte). Ich werde es mal probieren.

    Wie sieht es mit Bitshifting aus? Mein aktueller Algorithmus für Left-Shift sieht so ähnlich aus wie

    ... shift_left_(int n) { ...
// shifting over bitsize is undefined behaviour --> catch this case
if(n >= ATOM_BITSIZE) {
	// carrys full 0s are filled at the right
	const AtomType carrys = n / ATOM_BITSIZE;
	// move the important bytes left to make place for 0s
	storage_type temp;
	std::fill(temp.begin(), temp.end(), 0);
	std::copy(storage_.begin(), storage_.end() - carrys, temp.begin() + carrys); // swap direction for big endian
	storage_.swap(temp);
	shift_left_(n % ATOM_BITSIZE); // now try an simple shift
}
else {
	AtomType carry = 0, next_carry = 0;
	for(int i = 0; i < N; ++i) { // swap direction for big endian
		// range_mask sets a bitmask with 1s at bits ATOM_BITSIZE - n to ATOM_BITSIZE
		carry = (storage_[i] & range_mask<AtomType>(ATOM_BITSITE - n)) >> (ATOM_BITSIZE - n);
		((storage_[i] <<= n) |= next_carry);
		next_carry = carry;
	}
}

    Ich finde den ersten Fall verdächtig, wo ich Nullen auffüllen muss, falls die Shiftgröße größer ist als ein Basistyp.

    0
  • ?

    Ich weiss nicht ob das schneller ist, aber für unsigned gilt:

    carry_neu = (carry_alt & a^b) | (a&b);

    wobei a und b jeweils die obersten bits der beiden Summanden sind.

    Also:

    carry = (carry & (storage[n]>>sizeof(storage_type-1))^(summand.storage[n]>>sizeof(storage_type-1))) | 
((storage[n]>>sizeof(storage_type-1))&(summand.storage[n]>>sizeof(storage_type-1)));
    0
  • ?

    Alternativ

    carry = ~(~carry&(a^b));
    0
  • C

    Carry Fisher: Das könnte in der Tat schneller sein. (Wenn's stimmen würde..)
    Jodocus: Also mal ganz naiv, shift würde ich einfach so implementieren:

    if (n >= sizeof data_ * 8)
{
	memset(data_, 0, sizeof data_);
}
else
{
	if (n >= sizeof(base_type) * 8)
	{
		auto n0 = n / (sizeof(base_type) * 8);
		n = n % (sizeof(base_type) * 8);

		size_t i = N;
		while (i-- != n0)
		{
			data_[i] = data_[i - n0];
		}
		data_[i] = 0;
		while (i-- != 0)
		{
			data_[i] = 0;
		}
	}
	if (n != 0)
	{
		base_type carry = 0;
		for (size_t i = 0; i != N; ++i)
		{
			data_[i] = data_[i] << (n) | carry;
			carry = data_[i] >> (sizeof(base_type) * 8 - n);
		}
	}
}

    Allerdings braucht man da auch eine Sonderbehandlung für Werte die >= sizeof carry * 8 sind.

    0
  • W

    @Carry Fisher: Bist du sicher, dass das erste stimmt? Für mich sieht das so aus, als ob das nur für 1-bit-Zahlen gilt. (Beispiel a = 0, b = 1, carry = 1)
    Und bei deinem zweiten Posting wird das neue carry 1, wenn a=0, b=0 und carry=0...

    0
  • C
    Mod

    Carry Fisher schrieb:

    Ich weiss nicht ob das schneller ist, aber für unsigned gilt:

    carry_neu = (carry_alt & a^b) | (a&b);

    wobei a und b jeweils die obersten bits der beiden Summanden sind.

    Das kann ich nicht nachvollziehen.

    mit carry_alt == 0, x == AtomType_max, y == 1
    sollte x + y + carry_alt liefern:
    sum == 0, carry_neu == 1

    Edit: da war jemand schneller.

    0
  • ?

    wxSkip schrieb:

    Carry Fisher: Bist du sicher, dass das erste stimmt? Für mich sieht das so aus, als ob das nur für 1-bit-Zahlen gilt. (Beispiel a = 0, b = 1, carry = 1)
    Und bei deinem zweiten Posting wird das neue carry 1, wenn a=0, b=0 und carry=0...

    Vor Fehlern ist natürlich niemand gefeit 😉 Mal schaun. Die zweite Anmerkung von Dir ist leicht zu beantworten:

    0 XOR 0 = 0 -> 0 AND 0 = 0 -> NOT 0 = 1 -> NOT 1 = 0
    Ich hätte noch eine Klammer mehr spendieren müssen :

    carry = ~(~(carry&(a^b)))

    Ich habe mir einen Tabelle auf gestellt und dann die boolschen Gleichungen dafür aufgeschrieben, mit a, b, c als Eingangsdaten, x als Ergebnis und c' als neuem Carry

    a  1 0 1 0 1 1
b  0 1 0 1 1 1
c  0 0 1 1 0 1

x  1 1 0 0 0 1

c' 0 0 1 1 1 1

    Und da ist auch schon der Fehler: Ich habe nicht alle acht möglichen Fälle betrachtet.

    Also nochmal:

    a  0 1 0 1 0 1 0 1
b  0 0 1 1 0 0 1 1
c  0 0 0 0 1 1 1 1

x  0 1 1 0 1 0 0 1

c' 0 0 0 1 0 1 1 1

    c' = ab OR (a XOR b)c (Der erste Post von mir, also richtig)

    Der zweite Post von mir war aber falsch, weil nicht alle Fälle betrachtet wurden. Und Deine Anmerkung, dass das nur für eine Stelle gilt ist insofern richtig, als dass noch betrachtet werden muss, wie das Carry durch mehrere Stellen durchläuft. c ist in diesem Fall nämlich nicht das ursprüngliche carry, sondern das aus der Addition des bits n-2. Hmm, da muss ich noch mal nachdenken,aber ich halte den Ansatz für vielversprechend...

    0
Anmelden zum Antworten