3. Verbot einer Potenz

Verbot einer Potenz

  • B

    Hallo,

    ich benötige als bedingung für if

    daß p2 nicht Potenz sein darf von p1.

    Wie kann man das formulieren. Wenn es nur um das Quadrat ginge, wäre es kein Problem.

    Wenn P1=7 darf P2 nicht die Werte 47, 343 etc. annehmen.

    Danke für den Tip

    0
  • B

    \begin{align} p\_1^x &= p\_2 \\ x &= \log_{p\_1} p\_2 \\ x &= \frac{\ln p\_2}{\ln p\_1} \end{align}

    Prüfen ob Gl. (3) eine natürliche Zahl ist.
    Lieber nochmal überprüfen. Logarithmen waren nie meine Stärke:)

    Ansonsten ist das eher was fürs 'Rund um die Programmierung' oder Mathematik forum.

    0
  • W

    Ist P2 eine (natürlich ganzzahlige) Potenz von P1, so heisst das, dass das Verhältnis des Logarithmus von P2 zum Logarithmus von P1 ganzzahlig ist.

    p2 = p1^n // n e N
log(p2) = log( p1^n ) = n * log(p1)
bzw.:
n = log(p2) / log(p1)

    in Code gegossen:

    #include <cassert>
#include <cmath>
#include <iostream>

bool ist_potenz_von( int x, int base )
{
    assert( x > 0 && base > 0 );
    if( base == 1 )
        return x == 1; // 1^egal == x nur für x==1
    using namespace std;
    const double ex = log( double( x ) ) / log( double( base ) );
    return ex == floor( ex );
}

int main()
{
    using namespace std;
    const int p1 = 7;
    for( int p2; cin >> p2; )
    {
        if( ist_potenz_von( p2, p1 ) )
            cout << "p2=" << p2 << " ist Potenz von " << p1 << endl;
        else
            cout << "p2=" << p2 << " ist KEINE Potenz von " << p1 << endl;
    }
    return 0;
}

    Ergibt z.B.:

    5
p2=5 ist KEINE Potenz von 7
7
p2=7 ist Potenz von 7
1
p2=1 ist Potenz von 7
49
p2=49 ist Potenz von 7
343
p2=343 ist Potenz von 7
344
p2=344 ist KEINE Potenz von 7
342
p2=342 ist KEINE Potenz von 7

    Gruß
    Werner

    0
  • ?

    Das Problem mit Floating-Point-Lösungen ist, dass man mit ungenauen Datentypen rechnet. Werners Lösung liefert mir beispielsweise für 16807 = 7^5 und 282475249 = 7^10 falsche Ergebnisse aufgrund des Rundungsfehlers.

    Mit einem Epsilon-Vergleich kann man sich wohl behelfen, aber die Wahl des Epsilons scheint mir nicht trivial.

    Ich nehme an, dass eine Low-Tech-Lösung für Integer gesucht ist, beispielsweise

    bool is_power_of_aux(int x, int base) {
  return x == 1 || (x % base == 0 && is_power_of(x / base, base));
}

bool is_power_of(int x, int base) {
  if(base == 0) {
    return x == 0 || x == 1;
  }

  return is_power_of_aux(x, base);
}

    Auch wenn das eine deutlich schlechtere Laufzeitkomplexität hat.

    0
  • W

    seldon schrieb:

    Das Problem mit Floating-Point-Lösungen ist, dass man mit ungenauen Datentypen rechnet.

    .. kaum hatte ich mein Posting draußen, schon kam mir der gleiche Gedanke.

    Ich denke, die Lösung von seldon ist in der Praxis die bessere. Das muss noch nicht mal langsamer sein.

    Gruß
    Werner

    0
  • B

    Danke Leute, ich muß das jetzt erst verarbeiten...
    Eine Low Integer Lösung war gesucht.

    0
  • ?

    Nachtrag: Ich meine natürlich

    bool is_power_of_aux(int x, int base) {
  return x == 1 || (x % base == 0 && is_power_of_aux(x / base, base));
}

    ...sonst könnte ich mir das Aussieben von base == 0 auch sparen.

    0
  • A

    Eine vermutlich deutlich schnellere Implementation ist diese hier, da die teure Division vermieden wird:

    bool is_power_of_aux(int x, int base)
{
  if (x==1)return true;
  int rb=base;
  while (rb<x)rb*=base;
  return rb==x;
}
    0
  • ?

    Du müsstest allerdings die Beträge vergleichen oder negative Basen verbieten.

    0
  • V

    Das ist gut.
    Noch ein paar Sprzialfälle abchecken.

    bool is_power_of(unsigned int x, unsigned int base){
  switch(base){
    case 0: return x<2;//annahme, 0 hoch 0 == 1
    case 1: return x==1;
    case 2: return x!=0 && (x&(x-1))==0;
    case 3: //???
    case 4: unsigned int t=x&0x55555555; return x!=0 && (t&(t-1))==0;
    case 8: siehe case 4
    default: return is_power_of_aux(x,base);
  }
}
    0
  • V

    Vielleicht mag für die Basen<256 eine Tabelle anlegen.

    #include <iostream>
#include <map>
using namespace std;

int main(){
	map<unsigned int,unsigned int> powerToBase;
	for(unsigned int base=2;base<256;++base){
		for(unsigned int op=0,power=base;power>op;op=power,power*=base){
			powerToBase[power]=base;
		}
	}
	cout<<powerToBase.size()<<'\n';
}

    Sind nur 1360 Einträge. 256 kleine Arrays für binary_search? Oder eine dicke Hashtable? 256 kleine Hashtables?
    Zuerst x==1 und x==base abchecken.
    Wenn die Basis größer als 65535 ist, reicht return x=basebase.
    Wenn die Basis größer als 1625 ist, reicht return x=base*base || x=base*base    base.
    Wenn sie größer als 256 ist, reichts bis hoch 4 zu testen.

    Übrigens ist

    while (rb<x)

    evtl gefährdet durch Überläufe.

    Oder vielleicht nur sowas

    bool is_power(unsigned int x,unsigned int base){
	if(x<=1)
		if(x==0) 
			return base==0;
		else
			return base<=1;
	unsigned int op;
	unsigned int power=base;
	do{
		if(power==x)
			return true;
		op=power;
		power*=base;
	}while(power>op);
	return false;
}
    0
Anmelden zum Antworten