end-Iterator decrement definiert?

otze

Arcoth schrieb:

Nicht sofort verstehen kann. Ist doch nicht so schwer. Strengt ihr euch beim Code lesen nicht an?

Nein. Wenn ich Probleme hab, den Code zu lesen, dann wird in der Logik sicher ein Fehler sein, also lohnt sich das Code verstehen nicht. Dann schreib ich den Block gleich neu.

Columbo

Gut, ich habe ein Beispiel: Ich implementiere gerade Tonelli-Shanks. Dabei kommt für den zweiten Schritt, also einen quadratischen Nichtrest modulo p zu finden, bei mir folgende Schleife dran:

unsigned z = 1;
while( bin_mod_exp( ++z, (p-1)/2, p ) == 1 ); // per square-and-multiply, weil es größere p sind

Hierbei ist der Startwert von z im Prinzip 2, das verstecke ++ in der Schleife.
Es ginge auch

unsigned z = 2;
for(; bin_mod_exp(z, (p-1)/2, p) == 1; ++z );

Also welches davon soll ich bevorzugen?

volkard

Arcoth schrieb:

Gut, ich habe ein Beispiel: Ich implementiere gerade Tonelli-Shanks. Dabei kommt für den zweiten Schritt, also einen quadratischen Nichtrest modulo p zu finden, bei mir folgende Schleife dran:
unsigned z = 1;
while( bin_mod_exp( ++z, (p-1)/2, p ) == 1 ); // per square-and-multiply, weil es größere p sind
Hierbei ist der Startwert von z im Prinzip 2, das verstecke ++ in der Schleife.
Es ginge auch
unsigned z = 2;
for(; bin_mod_exp(z, (p-1)/2, p) == 1; ++z );
Also welches davon soll ich bevorzugen?

Weder noch!
Die for-Schleife hat ne komplexe Suchbedingung,
die for-Schleife hat ihre triviale Initialisierung ausgelagert,
die while-Schleife (do vergessen?) macht ++ in einem komplexeren Ausdruck,

// TODO: Algorithmus verbessern in dem nur Primzahlen getestet werden!
unsigned quadratic_nonresidue(unsigned p) {
  for (unsigned z = 2; z<p;++z)
    if (powm(z, (p-1)/2, p)==1) // bin_mod_exp: selten dummer Name
      return z;
  assert(false);
}

Columbo

Algorithmus verbessern in dem nur Primzahlen getestet werden!

Und das ist effizienter, selbst, wenn die ersten Nichtreste früh auftauchen?
Siehe http://oeis.org/A053760
Und warum soll das überhaupt schneller sein? Ich finde dazu gar nichts.

Und bin_mod_exp steht offensichtlich für binary modular exponetiation, was ist an dem Namen dumm?

volkard

Arcoth schrieb:

Und bin_mod_exp steht offensichtlich für binary modular exponetiation, was ist an dem Namen dumm?

pow statt exp, mod dahinter, bin ist irrelevant, also pow_mod.

Arcoth schrieb:

Algorithmus verbessern in dem nur Primzahlen getestet werden!

Und das ist effizienter, selbst, wenn die ersten Nichtreste früh auftauchen?
Siehe http://oeis.org/A053760
Und warum soll das überhaupt schneller sein? Ich finde dazu gar nichts.

Selbst wenn du schon die ganzen geraden Zahlen in der Suche weglässt hättest du schon einen Performance-Boost der dich so gut wie keinen Aufwand erfordert.

Und bin_mod_exp steht offensichtlich für binary modular exponetiation, was ist an dem Namen dumm?

Dass er ein Implementierungsdetail (binary modular exmonetiation) im Namen hat und nicht verrät, was er machen soll: a^b mod p berechnen, pow+mod => powm. Der Name powm ist übrigens gängig für alle, die ernsthafte Sachen mit Bigints machen und GMPlib verwenden.

volkard

Arcoth schrieb:

Algorithmus verbessern in dem nur Primzahlen getestet werden!

Und das ist effizienter, selbst, wenn die ersten Nichtreste früh auftauchen?

Glaube nicht, fühlt sich für mich fast an, als würde man mehr n Rechnungen bezahlen, um ein paar von n Rechnungen einzusparen.

volkard

define each schrieb:

Der Name powm ist übrigens gängig für alle, die ernsthafte Sachen mit Bigints machen und GMPlib verwenden.

Naja, die Ersnthaftigkeitskeule war nu nicht nötig.
https://www.google.de/#q=pow_mod 200000
https://www.google.de/#q=powmod 50000
https://www.google.de/#q=powm ???

Columbo

Der Name powm ist übrigens gängig für alle, die ernsthafte Sachen mit Bigints machen und GMPlib verwenden.

Sorry, ich verwende GMP schon eine Weile und da kommt mir nichts mit powm über den Weg gelaufen.

@Volkard: people of walmart - genial

Selbst wenn du schon die ganzen geraden Zahlen in der Suche weglässt hättest du schon einen Performance-Boost der dich so gut wie keinen Aufwand erfordert.

Gut, das tue ich.

Columbo

Nächstes Beispiel: Das ist meine Implementierung von pow_mod:

uint64_t pow_mod( uint64_t x, uint32_t exp, uint32_t mod )
{
	if( !exp )
		return 1;

	uint64_t result = 1;
	x %= mod;

	unsigned mask = 1 << (31-__builtin_clz(exp));
	do
	{
		result *= result;
		if( exp & mask )
			result *= x;

		result %= mod;
	}
	while( mask >>= 1 );

	return result;
}

Ist die Schleife so passabel? Oder soll der Shift in den Körper rein?
Vor allem: Ist das so richtig, oder geht es noch viel schneller und ich habe irgendwas verpennt?

Edit: Die Frage hat sich schnell von selbst beantwortet, nach ein wenig Recherce. Ich sollte öfter Recherche machen, das hilft.

otze

Es hat mich gerade 10 Sekunden gekostet zu verstehen, dass das >>= kein >= ist und mask in der Schleifenbedingung verändert wird.

Columbo

otze schrieb:

Es hat mich gerade 10 Sekunden gekostet zu verstehen, dass das >>= kein >= ist und mask in der Schleifenbedingung verändert wird.

Wau.

Was die Recherche angeht: Natürlich funktioniert schon

uint64_t pow_mod(uint64_t x, uint32_t y, uint32_t z)
{
    uint64_t number = 1;
    while (y)
    {
        x %= z;
        if (y & 1)
            number *= x;
        y >>= 1;
        x *= x;

        number %= z;
    }
    return number;
}

Eigentlich ein trivialer Algo, nur darauf kommen war bei mir nicht drin...

minastaros

Arcoth schrieb:

uint64_t pow_mod( uint64_t x, uint32_t exp, uint32_t mod )
	while( mask >>= 1 );
}
Ist die Schleife so passabel? Oder soll der Shift in den Körper rein?
Vor allem: Ist das so richtig, oder geht es noch viel schneller und ich habe irgendwas verpennt?

Nein. Der code "lügt" schon wieder: In der while-Klammer steht die Laufbedingung, und nur die. Bei dir jedoch sind es zwei Dinge:

mask wird verändert.
2. Und dann auf != 0 geprüft.

Du versuchst immer, zwei Dinge gleichzeitig zu machen, dabei entstehen gefährliche Doppeldeutigkeiten (schließe mich otze an).

Do one thing, and one thing right.

Arcoth schrieb:

unsigned z = 1;
while( bin_mod_exp( ++z, (p-1)/2, p ) == 1 ); // per square-and-multiply, weil es größere p sind
...
unsigned z = 2;
for(; bin_mod_exp(z, (p-1)/2, p) == 1; ++z );

Hier genauso: abgesehen von der Mathematik (jetzt auf die Schnelle zu viel):
In die Klammer() bei while und for : Die Laufzeitsteuerung
In den Körper{}: das, was in der Schleife getan wird.

Deine Schleifen haben keinen Körper, allein das ist schlechter Stil. Es sollte wenigstens ein {} da sein. Warum nicht die ganze Rechnung da rein? oder oben das mask >>= 1 ? In while wird dann nur das Ergebnis gegen 0 geprüft.

Es tut keine Not, so knauserig mit Platz und Klammern zu sein.

Arcoth schrieb:

uint64_t pow_mod(uint64_t x, uint32_t y, uint32_t z)

x, y und z? Wie wärs mit

uint64_t pow_mod(uint64_t base, uint64_t exp, uint64_t mod)

?

uint64_t number = 1;

number? Wie wärs mit result oder so?

x %= z;
if (y & 1)
    number *= x;
y >>= 1;
x *= x;

number %= z;

Gut, man kann darüber streiten, ob man das mit Binäroperatoren oder mit Modulo machen will, aber was ist das für eine willkürliche Anordnung der Anweisungen? Klar übersieht man da ein unötiges modulo =>

if (exp & 1)
    result = (result*base)%mod;
exp >>= 1;
base *= base;

Du iterierst über die Bits des Exponenten, warum kein for?

uint64_t result = 1;
for (; exp; exp >>= 1) {
    if (exp & 1)
        result = (result*base)%mod;
    base *= base;
}
return result;

Columbo

@define each: Dank dir habe ich gerade zehn Minuten verloren, weil da ein == statt einem != in quadratic_nonresidude stand und ich es 1:1 übernahm, in der Annahme, du kannst wenigstens einen Dreizeiler ungetestet ordentlich schreiben.

number? Wie wärs mit result oder so?

Ich habe den Code kopiert und angepasst, daher die Bezeichner.

Du iterierst über die Bits des Exponenten, warum kein for?

Ich würde sagen, for passt hier nicht. Ich warte mal ab, was Volkard sagt.

Klar übersieht man da ein unötiges modulo =>

Und wo ist in deiner finalen Variante das Modulo für base ?

volkard

otze schrieb:

Es hat mich gerade 10 Sekunden gekostet zu verstehen, dass das >>= kein >= ist und mask in der Schleifenbedingung verändert wird.

Ja, statt

}
    while( mask >>= 1 );

hätte

mask >>= 1;
    }
    while( mask );

sicher überhaupt nicht weh getan.
Warum nicht bool-Denk erzwingen?

mask >>= 1;
    }
    while( mask != 0 );

volkard

Arcoth schrieb:

Ich würde sagen, for passt hier nicht. Ich warte mal ab, was Volkard sagt.

Sehe ich auch so.

Außerdem würde ich %2 und /2 benutzen, der Kontext ist so furchtbar mathematisch, da mag ich im Kontext bleiben.

volkard

Außerdem würde ich pow_mod(b,e,m) auf mul_mod(a,b,m) stützen!

So ein

mul_mod(uint64_t b,uint64_t e,uint64_t m){
   uint64_t result;
   __asm{mul…}
   __asm{mod…}
   return…

darf dann ruhig mal gebaut werden.

Columbo

Außerdem würde ich %2 und /2 benutzen, der Kontext ist so furchtbar mathematisch, da mag ich im Kontext bleiben.

Das ist doch Quatsch. Weil das &1 da ganz klar fragt, ob das Bit gesetzt ist. Und nicht ob die Zahl durch zwei Teilbar ist, oder welchen Rest selbige Division hervorbringt. Daher verstehe ich nicht: warum die Bedeutung beider Operationen durcheinanderbringen?