C Implementierung der Potenzierung durch Quadrieren

Question

Ich habe versucht, die "Potenzierung durch Quadrieren" -Algorithmusn in C zu implementieren, aber mein Programm hat ein seltsames Verhalten. Als erstes ist hier ein kleiner Code-Schnipsel:

long long fast_power_1(long long base, long long power){ 
    long long result = 1; 
    while (power > 0) 
    { 
     if (power % 2 == 0) 
     { 
      power = power/2; 
      base = base * base; 
     } 
     else 
     { 
      power = power - 1; 
      result = (result*base); 
      power = power/2; 
      base = (base * base); 
     } 
    } 
return result;} 

Wenn ich die Funktion mit rufen:

printf("%d\n",fast_power_1(2,100)); 

Ich erwarte, dass der Ausgang so etwas wie 976.371.285 sein, aber das Ergebnis ist 0 und ich weiß nicht verstehe ganz genau warum.

Answer 1

long long sollte mit %lld Formatbezeichner gedruckt werden, andernfalls ist es undefiniertes Verhalten. Auch diese Methode hat bereits einen Überlauf innerhalb großer Werte von power - weil lange lange nicht halten kann 2^100 (ab sofort in 32 oder 64 Bit-Systeme- wenn es 128 Bit-System natürlich kann es).

Ab sofort in Ihrem Code, wenn Sie nicht zu großen Wert des Exponenten geben und printf("%lld",..) verwenden, dann würde es Ihnen ein gültiges Ergebnis geben.

Vielleicht wollten Sie modulare Arithmetik damit haben. (Im Allgemeinen stoppen Anforderungen an das - wie Modulo einige große Primzahl, d. H. 10^9+7).