Kehrwert Integer-Division

[Walter T. (nicolas)]

Hallo zusammen,

ich habe mal wieder ein Integer-Denkproblem. Wie immer wäre mir eine 
Quelle (Link/Buchnennung) sogar noch lieber als die direkte Lösung.

Ich habe eine Funktion, die eine zur Compile-Zeit bekannte Konstante 
durch eine Variable dividiert:

#define MARKER 16777213ULL


uint32_t overflowVal(uint32_t divisor)
{
    uint64_t marker = MARKER;
    uint64_t overflow = marker * marker/(2*divisor);
    const uint64_t threshold = INT32_MAX/2;

    assert( overflow <= threshold ); 

    return overflow;
}

Für den Divisor gibt es einen kleinstmöglichen erlaubten Wert (>0), den 
ich exakt berechnen will. Dass es toll ist, wenn das zur Compilezeit 
geschieht, ist jetzt erst einmal nur am Rande interessant.

Der naive Ansatz:

uint32_t minDivider(void)
{
    uint64_t marker = MARKER;
    const uint64_t threshold = INT32_MAX/2;

    uint32_t dMin = marker*marker/(2*threshold);
    return dMin;
}

hat einen Eins-daneben-Fehler für alle bisher getesteten Werte von 
"Marker".

Wie kann ich den kleinsten Divisor d, bei dem d-1 einen unerlaubten 
Überlauf liefert und d im gültigen Bereich liegt, für beliebige Werte 
des Dividenden berechnen?

Viele Grüße
W.T.

[W.S. (Gast)]

Walter T. schrieb:
> ich habe mal wieder ein Integer-Denkproblem.

Hä?

Bahnhof meinerseits...

Also ich interpretiere das mal so:

Du hast

int64 i, j;

und willst feststellen, ab wann

erg = (i*i) / (2*j);

größer ist als 0x7FFFFFFF. Ist das so?

Also erstens wird das Ganze unterschiedlich, je nachdem in welcher 
Reihenfolge du die Rechenoperationen ausführst, weil du ja zum Erhalt 
möglichst vieler gültiger Stellen weder bei i*i einen Überlauf, noch bei 
i/(2*j) oder (i*i)/(2*j) einen Überlauf oder einen Unterlauf, sprich ne 
Null, haben willst.

Aber wenn du eine 64 Bit Zahl i durch eine Zahl j teilen willst, ohne 
daß das Ergebnis größer ist als 0x7FFFFFFF, dann mußt du den Bitabstand 
der führenden Bits beider Zahlen vergleichen und anschließend ggf. noch 
die Quasi-Mantissen.

Also mal ganz grob aus dem Handgelenk:
n = 0;
while ((i > j)
{ j = j<<1);
  ++n;
}
if (n > 30) //oder 31 ??
{ throwevent("Überlauf"); }

W.S.

[Joe F. (easylife)]

Durch Umformen deiner Gleichung komme ich auf

divisor >= (marker * marker) / INT32_MAX

overflow <= threshold : (marker * marker) / (2 * divisor)     <= INT32_MAX/2
*2                    : (2 * marker * marker) / (2 * divisor) <= INT32_MAX
Bruch kürzen          : (marker * marker) / divisor           <= INT32_MAX
*divisor, /INT32_MAX  : (marker * marker) / INT32_MAX         <= divisor

[Johann L. (gjlayde)]

Joe F. schrieb:
> Durch Umformen deiner Gleichung komme ich auf
>
> *2

Falls INT32_MAX wie üblich ungerade ist, dann ist (INT32_MAX/2)*2 != 
INT32_MAX.

Stattdessen: (INT32_MAX/2)*2 = INT32_MAX - 1 = INT32_MAX - (INT32_MAX % 
2)