Zahlenkreis Algorithmus

Sone

volkard schrieb:

Sone schrieb:

Ich dachte, das wäre jetzt eine Spaßaufgabe - du willst das tatsächlich in deiner Anwendung hinschreiben?

Du Nube sollst noch bescheiden und hilfreich sein. Bitte bitte.

Ok ok.

Sone schrieb:

C++ verwendet die symmetrische Variante des Modulo-Operators:
$a ~mod~ m = a - m * ( sgn(a)sgn(m) \lfloor \frac{|a|}{|m|} \rfloor )$

Sind also sowohl a (-4) als auch m (hier -20) negativ, ergibt sich
$a ~mod~ m = a - m * ( \lfloor \frac{a}{m} \rfloor )$
Allerdings kann a wie in diesem Beispiel kleiner sein als m, daher kann es passieren dass $\lfloor \frac{a}{m} \rfloor ~=~ 0$ wird.
Damit ist das Ergebnis a (-4) - was aber nicht stimmen kann.

Wieso kann das nicht stimmen? Wo siehst du hier ein Problem?

Sone

out schrieb:

Sone schrieb:

C++ verwendet die symmetrische Variante des Modulo-Operators:
$a ~mod~ m = a - m * ( sgn(a)sgn(m) \lfloor \frac{|a|}{|m|} \rfloor )$

Sind also sowohl a (-4) als auch m (hier -20) negativ, ergibt sich
$a ~mod~ m = a - m * ( \lfloor \frac{a}{m} \rfloor )$
Allerdings kann a wie in diesem Beispiel kleiner sein als m, daher kann es passieren dass $\lfloor \frac{a}{m} \rfloor ~=~ 0$ wird.
Damit ist das Ergebnis a (-4) - was aber nicht stimmen kann.

Wieso kann das nicht stimmen? Wo siehst du hier ein Problem?

Das Ergebnis sollte wieder im Bereich 1, 20 sein.

Sone schrieb:

out schrieb:

Sone schrieb:

C++ verwendet die symmetrische Variante des Modulo-Operators:
$a ~mod~ m = a - m * ( sgn(a)sgn(m) \lfloor \frac{|a|}{|m|} \rfloor )$

Sind also sowohl a (-4) als auch m (hier -20) negativ, ergibt sich
$a ~mod~ m = a - m * ( \lfloor \frac{a}{m} \rfloor )$
Allerdings kann a wie in diesem Beispiel kleiner sein als m, daher kann es passieren dass $\lfloor \frac{a}{m} \rfloor ~=~ 0$ wird.
Damit ist das Ergebnis a (-4) - was aber nicht stimmen kann.

Wieso kann das nicht stimmen? Wo siehst du hier ein Problem?

Das Ergebnis sollte wieder im Bereich 1, 20 sein.

Ne. Ich habe in der Schule gelernt, dass es 2 "Modulo" gibt. Das mathematische (das du meinst) und das informationstechnische.

Das mathematisches Modulo:
1. Kenn nur einen positiven Rest. Der ganzzahlige Rest muss also positiv sein.
2. a%b Das Ergebnis wiederholt sich alle b Mal:

a:      -9 -8 -7 -6 -5 -4 -3 -2 -1  0  1  2  3  4  5  6  7  8  9
          ----------------------------------------------------------------
          mod b:   3  0  1  2  3  0  1  2  3  0  1  2  3  0  1  2  3  0  1

Du kannst also ein Vielfaches von b dazuaddieren, falls a negativ ist: a%b = (a+i*b)%b

Das informationstechnische Modulo:
1. Der ganzzahlige Rest kann positiv oder negativ sein.
2. a%b Wenn a positiv ist, ist das Ergebnis auch positiv. Wenn a negativ ist, ist das Ergebnis auch negativ. Ergo, das Vorzeichen von b ist egal.

So hab ich das mal gelernt.

volkard

out schrieb:

Sone schrieb:

out schrieb:

Sone schrieb:

C++ verwendet die symmetrische Variante des Modulo-Operators:
$a ~mod~ m = a - m * ( sgn(a)sgn(m) \lfloor \frac{|a|}{|m|} \rfloor )$

Sind also sowohl a (-4) als auch m (hier -20) negativ, ergibt sich
$a ~mod~ m = a - m * ( \lfloor \frac{a}{m} \rfloor )$
Allerdings kann a wie in diesem Beispiel kleiner sein als m, daher kann es passieren dass $\lfloor \frac{a}{m} \rfloor ~=~ 0$ wird.
Damit ist das Ergebnis a (-4) - was aber nicht stimmen kann.

Wieso kann das nicht stimmen? Wo siehst du hier ein Problem?

Das Ergebnis sollte wieder im Bereich 1, 20 sein.

Ne. Ich habe in der Schule gelernt, dass es 2 "Modulo" gibt. Das mathematische (das du meinst) und das informationstechnische.

Das mathematisches Modulo:
1. Kenn nur einen positiven Rest. Der ganzzahlige Rest muss also positiv sein.
2. a%b Das Ergebnis wiederholt sich alle b Mal:
a:      -9 -8 -7 -6 -5 -4 -3 -2 -1  0  1  2  3  4  5  6  7  8  9
          ----------------------------------------------------------------
          mod b:   3  0  1  2  3  0  1  2  3  0  1  2  3  0  1  2  3  0  1
Du kannst also ein Vielfaches von b dazuaddieren, falls a negativ ist: a%b = (a+i*b)%b

Das informationstechnische Modulo:
1. Der ganzzahlige Rest kann positiv oder negativ sein.
2. a%b Wenn a positiv ist, ist das Ergebnis auch positiv. Wenn a negativ ist, ist das Ergebnis auch negativ. Ergo, das Vorzeichen von b ist egal.

So hab ich das mal gelernt.

War es nicht so, daß in C++ dem Compiler freigestellt ist, ob er das mathematische oder das informationstechnische benutzt?

volkard schrieb:

War es nicht so, daß in C++ dem Compiler freigestellt ist, ob er das mathematische oder das informationstechnische benutzt?

Hab mal eben nachgeschaut. Wie es scheint, hat mein Prof. das wohl etwas doof erklärt damals. Es gibt nur 1 Modulo, nämlich das, das Sone meint: a%b = 0...b-1
Das, was wir hier in C++ haben... das ist gar kein Modulo. Das nennt sich auch nicht Modulo-Operator. Das Teil heißt remainder operator . Demnach darf sich der Compiler wohl auch nichts aussuchen :p

krümelkacker

Sone schrieb:

Jetzt habe ich dich.

Sind wir hier im Kindergarten?

#include <cassert>
#include <iostream>

int restklasse(int wert,
               int divisor,
               int start = 0)
{
   wert = (wert - start) % divisor;
   if (wert < 0) wert += divisor;
   return start + wert;
}

int main()
{
   int a = 1;  // von (einschliesslich)
   int b = 20; // bis (einschliesslich)
   int c = 5;  // stand
   int d = -9; // delta
   int x = restklasse(c+d, b-a+1, a); // <-- Einzeiler ;-)
   assert(a <= x);
   assert(x <= b);
   std::cout << x << '\n';
}

Bzgl des Divisionsrest-Operators: Der war und ist immer noch so definiert, dass bei b != 0 folgendes gilt:

(a / b) * b + (a % b) = a

Allerdings ist, soweit ich weiß, erst ab C++11 (und C99) garantiert, dass bei der Ganzzahl-Division immer zur Null hin gerundet wird, egal was die Operanden für Vorzeichen haben.

dd++ 0

ISO/IEC 14882:2011 sagt:

C.2.2 Clause 5: expressions [diff.cpp03.expr]
5.6
Change: Specify rounding for results of integer / and %
Rationale: Increase portability, C99 compatibility.
Effect on original feature: Valid C++ 2003 code that uses integer division rounds the result toward 0 or
toward negative infinity, whereas this International Standard always rounds the result toward 0.

Sone

Wen es noch interessiert: Natürlich gibt es auch die entsprechenden Funktionen in der C++11-Standardbibliothek:

Sind wir hier im Kindergarten?

Nein. Wie kommst du darauf?

Sone

Was die Benennung angeht: Ich meinte den symmetrischen Modulo. Wikipedia unterscheidet auch zwischen beiden. Deswegen.