end-Iterator decrement definiert?

volkard

Arcoth schrieb:

Du vielleicht. Und deine Kollegen?

Welche Kollegen? Ich arbeite mit niemandem, und das habe ich auch noch nie (das erklärt einiges, was?).

Naja, das mit den Kollegen ist ein verdammt gutes Modell, um selber Code zu schreiben, den man in einem halben Jahr noch versteht. Schreibe so, daß Dein Kollege, der nicht eingearbeitet ist, es lesen kann, dann kannst Du es auch in einem halben Jahr lesen. Schreibe ihn so, daß der Azubi ihn lesen kann, dann kannste ihn auch lesen, wenn Du mal einen schlechten Tag hast. Machst ja auch bei Schnittstellen diese Vorgehen, machst alle private und so, vermeidest Redundanz, tust Liskov-Prinzip, Regel der großen 3-5, und endlos mehr. Obwohl nur Du selber der Benutzer der Klassen bist, programmierst Du gegen einen hypothetischen Idiotenbenutzer, gegen Dich. Und Viola, Du läßt unglaublich viele spätere logische Fehlerchen vom Compiler rausfischen dadurch. Unit-Tests? Ist was für Java-Leute, damit sie mit fünffacher Arbeit nur noch doppelt so viele Fehler rauslassen wie wir, wenn wir der Nase nach programmieren (bevor jetzt Aufschreie kommen, wir können Unit-Tests auch machen bei Bedarf je nach Anforderungen).

Arcoth schrieb:

Auch wenn ich nach wie vor nicht verstehe, wie man diese beiden Zeilen
unsigned i = 0;
while( ++i < 10 )
Nicht sofort verstehen kann. Ist doch nicht so schwer. Strengt ihr euch beim Code lesen nicht an?

Naja, mich hat's vielleicht viel stärker erwischt.

Mit dem 64-er aufgewachsen. Keine lokalen Variablen, kein new/delete. Pascal habe ich übersprungen, war auch gut so. Dann C auf dem PC. Von BASIC nach C war schon nicht leicht, aber auf einmal konnte ich "alles" machen in der Hochsprache! Geil! (Naja, gerade mal Maustreiber-Callbacks bauen und absetzen.) Voller Begeisterung schrieb ich auch mal einen Datenkomprimierer. Warum PK-Zip, wenn ich es vielleicht besser kann?

Habe mir ein schon nettes Verfahren überlegt. Und das hatte ich so auch Papier an kleinen Beispielen auch gemacht. Und reingeknüppelt in die Tastatur habe ich es auch. Es hat nicht so stark komrpimiert, wie ich es mir vorstellte…
Vielleicht einen Monat lang dran gerätselt, dies und das probiert, nöö, es wurde nicht besser. Verflixt!

Studienbeginn!! Echt keine Zeit gerade für sowas!

Halbes Jahr später sah es so aus: Ich wusste noch haargenau wie mein Algo funktionierte. Nebenbei bemerkt, das weiß ich heute noch ebenso genau. Nur vom Code konnte ich bis aig triviale Sachen wie "void main()" oder includes keine eine Zeile mehr entzuffern, was ich vor einem nur halben Jahr damit beabsichtigt hatte. Auch nicht durch eine Woche Anstarren des Codes. Er war komplett für die Tonne.

Und sowas mag ich nicht mehr. Code von mir seit 1995 kann ich flüssig lesen, seitdem schreibe ich kompromisslos gegen mich selber.

Tja, das ist mein persönlicher Spleen. Sozusagen ein Engramm, wenn ich Dianetiker wäre. Darum folge ich Dir auch nicht in die Tiefen der TMP, sondern warte lieber eine Sprache ab, wo man mit der Sprache selber Compilezeitsachen machen kann, ohne, daß sie Lispelt.

Arcoth schrieb:

volkard schrieb:

Nee, mal ehrlich, eine komplexte Laufbedingung nervt Dich weniger als eine komplexe Initialisierung, das finde ich irgendwie C.

Was genau daran assoziierst du mit C?

Sterne-Programmierer. Im frühen C war die Begeisterung enorm, mit wenigen Zeichen komplexe Sachen auszudrücken. Wo man mit ASM 20 Befehle brauchte oder in BASIC 5 Zeilen, war man mit einer "einfachen" Zeile in C fertig. Krass! Geniale Sprache!

minastaros

Arcoth schrieb:

Welche Kollegen? Ich arbeite mit niemandem, und das habe ich auch noch nie (das erklärt einiges, was?).

Ja, das merkt man.

Der Vergleich von Volkard gefällt mir: Mein zukünftiges Ich ist selbst mein erster Kollege.

Arcoth schrieb:

Auch wenn ich nach wie vor nicht verstehe, wie man diese beiden Zeilen
unsigned i = 0;
while( ++i < 10 )
Nicht sofort verstehen kann. Ist doch nicht so schwer. Strengt ihr euch beim Code lesen nicht an?

Nochmal: Es geht nicht um "verstehen". Code arbeitet auf mehreren Ebenen, die reine Funktionalität ist nur die unterste. Technisch gesehen funktionieren alle Lösungen, keine Frage.

Aber darüber kommt die Semantik. Nicht: was tut der Code, sondern was will er im gröberen Kontext sein? Und da ist, wenn ich es noch härter ausdrücke, while an dieser Stelle einfach das falsche Tool.

While: Ein bestimmter Block wird mehrfach wiederholt, bis oder solange eine bestimmte allgemeine Bedingung eintritt.

For: Es gibt eine Menge (pure Zahlen, ein Container, eine Liste usw.) und auf jeden Fal eine Laufvariable, im Allgemeinen deren Index oder Iterator. Und Aufgabe dieses Code-Blockes ist es, über die Menge zu iterieren (das kann auch rückwärts oder in 2er-Schritten sein, aber im Prinzip bleibt es beim Iterieren).

Genauso, wie man for nicht für andere Dinge missbrauchen darf (z.B. in der Laufbedingung etwas ganz anderes prüfen, oder im Fortsetzungsblock Dinge tun, die in den Schleifenkörper gehören usw.), "lügt" der Code, wenn ein while da steht, es aber in Wirklichkeit um eine Iteration geht.

Der Punkt ist, dass man beim Lesen (Faustregel: Code wird 10% geschrieben, aber 90% gelesen; von mir, von anderen, von dem, der unter Zeitdruck einen Fehler finden muss usw.) oft nur durch schnelles Überfliegen etwas sucht oder verstehen muss, weil die Zeit fehlt, ins Detail zu gehen. Ist wie beim Fachbuch die Schlagwörter zu überfliegen oder die Überschriften. Wenn ich dann im Code sehe, aha, ein Container, und dann ein for , weiß ich schon im Prinzip, was passieren wird und brauche die Details womöglich erstmal nicht. Bei while geht das nicht, zumindest nicht so schnell, weil ich auf jeden Fall die Laufbedingung durchlesen muss. Das ist dass, was mit "Getriebeschaden" gemeint war: aus der schnellen Geschwindigkeit runterbremsen.

Arcoth schrieb:

Tut mir Leid.
(Die Meisten hier sind übrigens recht jung, höchstens 30)

Akzeptiert. Ist eine Frage der Höflichkeit, weniger des Alters (die 25 war von dir - hab ja nur, äh, zitiert.)
Es macht Spaß, auch über kleinste Details heftig zu debattieren. Aber es sollte sachlich bleiben.

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.