IsPowerOfN

[Wolfgang Mix]

Des öfteren möchte man testen, ob eine ganze Zahl (>=1) eine ganze Potenz von n (>=1) ist,
zb. 1,3,9,27,81,243 für n=3 usw. Die beiden nachfolgenden Funktionen erledigen das.

Anmerkung: Bei sehr großen Zahlen werden fehlerhafte Werte zurückgegeben.

Delphi-Quellcode:

//Wolfgang Mix - Delphi - PRAXiS
function LgX(base, number: Double): Double; //inline;
begin
  if (base <= 0.0) or (number <= 0.0) then
    System.Error(reInvalidOp);
  Result := Ln(number) / Ln(base); //plattformunabhängig
end;

//Wolfgang Mix - Delphi - PRAXiS
function IsPowerOfX(base, number: Double): Boolean;
begin
  Result := Frac(LgX(base, number)) < 1e-9;
end;

Gruß

Wolfgang

[himitsu]

Delphi-Quellcode:

function LgX(base, number: Double): Double; //inline;
begin
  if (base <= 0.0) or (number <= 0.0) then
    System.Error(reInvalidOp);
  Result := Ln(number) / Ln(base);
end; 

function IsPowerOfX(base, number: Double): Boolean; //inline;
begin
  Result := Frac(LgX(base, number)) < 1e-9;
end;

:duck:


Warum ich die Parameterprüfung verschoben hab:
Damit ein einzeln genutztes LgX auch geprüft wird und IsPowerOfX braucht diese nicht, da dort durch LgX gleich mitgeprüft wird,


PS: Das Inline kann man übrigens bei neueren Delphis "aktivieren", dann wird keine eigenständige Funktion erstellt, sondern der Code direkt an Ort und Stelle als Inline-Code eingefügt.
(ältere Versionen kennen den Befehl leider nicht ... drum auskommentiert)

[OldGrumpy]

Habt ihr auch mal getestet ob die Funktion bei sehr großen Zahlen nicht "aus Versehen" ein fälschlich positives Ergebnis liefert? Da bei Fließkommarechnungen immer Unschärfen auftreten, habe ich da etwas Bauchweh mit dem "kleiner 1e-9". Allerdings habe ich mir jetzt nicht die Mühe gemacht, die Grenzen der Wertebereiche der verwendeten Datentypen abzuklopfen. Notfalls müsste man mit Int64 oder BigInt, Div und Modulo arbeiten um sicherzugehen...

[gammatester]

Leider wiedermal ziemlich ungetestet und falsch. Neben OldGrumpys Bedenken, hier ein fetter Bug: Jede Zahl number > 1 ist eine Potenz zu base < 1! Warum? Weil ln(number) > 0 und ln(base) < 0 also lgx(base, number) < 0 < 1e-9. Also ist mindestens ein abs dringend erforderlich.

Delphi-Quellcode:

function IsPowerOfX(base, number: double): boolean;
begin
  result := abs(frac(lgx(base, number))) < 1e-9;
end;

[himitsu]

sollte das Ergebnis von Ln nicht immer größer als 0 sein, wenn auch der übergebene Wert größer 0 ist?

[Wolfgang Mix]

Nein, Log(1) ist immer exakt Null, zu jeder Basis.

Gruß

Wolfgang

[gammatester]

Zitat:

Zitat von himitsu

sollte das Ergebnis von Ln nicht immer größer als 0 sein, wenn auch der übergebene Wert größer 0 ist?

???
Hast Du grad keine Delphi zur Hand? ln(0.5) = -0.6931471805599453094172321215!

[Wolfgang Mix]

Richtig, unter 1 wird der Logarithmus negativ bis - unendlich,
bei Null crashed es

Gruß

Wolfgang

[alzaimar]

Entschuldigt, aber wo ist der Mehrwert? Das ist Schulmathematik bzw. trivial. Mich erinnert das an die Funktion, die zwei Zahlen addiert:

Delphi-Quellcode:

// Alzaimar - Delphi - PRAXiS
Function AddNumbers (A,B : Extended) : Extended;
Begin
  Result := A + B
End;

Und anstatt LgX sollte/könnte man auch die Funktion LogN aus der Unit Math nehmen. Weiterhin ist mir der Mehrwert der präventiven Prüfung der Parameter ggü. einem einfachen An-die-Wand-fahren-lassen nicht klar bzw. bedarf einer Erklärung: Was passiert, wenn man die Prüfung weglässt?

[gammatester]

Zitat:

Zitat von alzaimar

Entschuldigt, aber wo ist der Mehrwert? Das ist Schulmathematik bzw. trivial.

Zitat:

Zitat von alzaimar

Und anstatt LgX sollte/könnte man auch die Funktion LogN aus der Unit Math nehmen. Weiterhin ist mir der Mehrwert der präventiven Prüfung der Parameter ggü. einem einfachen An-die-Wand-fahren-lassen nicht klar bzw. bedarf einer Erklärung: Was passiert, wenn man die Prüfung weglässt?

Voll einverstanden. Eine ähnliche Diskussion hatten wir schon im Vorgängerthread zu lgx bzw. logn. Dort hatte ich auch auf math.logn verwiesen, und andere hatten den Nährwert bezweifelt.

Das hält manche allerdings nicht davon ab, völlig triviale matmematische Aussagen in schlechte und falsche Programme umzusetzen.

Wäre ja irgendwo kein Problem, wenn's nicht als Beitrag zu Codelibrary vertrieben würde.

[Wolfgang Mix]

Zeigt doch 'mal bitte Eure Profi-Version,
dürfte auch andere interessieren.

MFG

Wolfgang

[gammatester]

Zitat:

Zitat von Wolfgang Mix

Zeigt doch 'mal bitte Eure Profi-Version,
dürfte auch andere interessieren.

MFG

Wolfgang

Profi-Version von was? Wie schon gesagt, lgx gibt's in math als logn. Das ist vielleicht(?) eine Profi-Version (und nebenbei eine Funktion, die Codegier/E.. im Laufe der Zeit nicht verschlimmbessert hat).

IsPowerOfN ist mE überflüssig, weil sie in der Praxis eigentlich keiner braucht. Was gebraucht wird, sind Funktionen wie

Delphi-Quellcode:

IsPrimePower(n: int64): boolean;
IsPower(n: int64): boolean;

die testen, ob n eine Primzahlpotenz n = p^k oder eine allgemeine Potenz n=m^k ist. Man beachte: Potenz für irgendeine Basis, zB IsPower(6) = false, IsPower(216) = true, IsPrimePower(216) = false. Sowas wird wirklich gebraucht, zB bei Primzahltests.

Wenn man unbedingt will, könnte man zB sowas benutzen

Delphi-Quellcode:

function IsPowerOfX(base, number: double): boolean;
begin
  result := IsZero(abs(frac(logn(base, number)));
end;

[Wolfgang Mix]

Zitat:

Wenn man unbedingt will, könnte man zB sowas benutzen

Delphi-Quellcode:

function IsPowerOfX(base, number: double): boolean;
begin
  result := IsZero(abs(frac(logn(base, number)));
end;

Aja, und Du bist sicher, daß das mit der Null (IsZero) wirklich funktioniert?
Halte ich für ein Gerücht!
Das abs ist überflüssig, da Nachkommastellen immer positiv sind.
Und was soll nun wirklich besser sein?


Gruß

Wolfgang

[alzaimar]

Wolfgang, dein 'Code' wird durch die Verwendung von LogN aus der Math-Unit auf einen 1-Zeiler reduziert. Und dieser Einzeller ist doch nur eine Ausformulierung einer einschlägig bekannten Definition: Ähnlich trivial wie meine ironische 'AddNumbers'-Funktion.

Sie taugt durchaus als Veranschaulichung eines der Grundprinzipien der Programmierung: Ausformulierung einer Problemlösung bzw. Definition. Aber einen Mehrwert stellt es imho nicht dar, denn es steckt keine neue Erkenntnis in dieser einen(!) Zeile.

Muss man wirklich weitere Worte über dieses Highlight kompakter Programmierkunst verlieren? :roll:

Zitat:

Zitat von Wolfgang Mix

Aja, und Du bist sicher, daß das mit der Null (IsZero) wirklich funktioniert?

Jupp.

Zitat:

Zitat von Wolfgang Mix

Halte ich für ein Gerücht!

Warum? Schau doch einfach nach, wie diese Funktion definiert ist.

Zitat:

Zitat von Wolfgang Mix

Und was soll nun wirklich besser sein?

Sie definiert nichs redundantes und bewegt sich dadurch weiterhin in einem geschlossenen Kalkül. Bereits definierte und einschlägig bekannte Funktionen zu verwenden ist in Fachkreisen allgemein als guter Programmierstil bekannt: DRY-Prinzip wäre ein Schlagwort, das mir spontan einfällt.

Wenigstens hast Du mit einem Recht: Das 'Abs' ist überflüssig. Auch weil die funktionierende Standardfunktion 'IsZero' ihrerseits 'Abs' aufruft.

Je mehr ich deinen Ausführungen folge, desto weniger verstehe ich deine Signatur. :stupid:

[gammatester]

Zitat:

Zitat von Wolfgang Mix

Zitat:

Wenn man unbedingt will, könnte man zB sowas benutzen

Delphi-Quellcode:

function IsPowerOfX(base, number: double): boolean;
begin
  result := IsZero(abs(frac(logn(base, number)));
end;

Aja, und Du bist sicher, daß das mit der Null (IsZero) wirklich funktioniert?
Halte ich für ein Gerücht!

Vielleicht solltest Du mal in den Quellcode schauen, ehe Du falsche Vorstellungen in die Welt setzt. IsZero testet nicht gegen 0. Wenn Du keine Quellcode hast, wäre es doch keine Schande, zu fragen was IsZero eigentlich macht - jedenfalls bei Leuten, die sich nicht als perfekt bezeichnen :)

Delphi-Quellcode:

IsZero(a) := abs(a) <= (type)Resolution mit
ExtendedResolution = 1E-19 * FuzzFactor;
DoubleResolution   = 1E-15 * FuzzFactor;
SingleResolution   = 1E-7 * FuzzFactor;
FuzzFactor = 1000;

Zitat:

Zitat von Wolfgang Mix

Das abs ist überflüssig, da Nachkommastellen immer positiv sind.

Noch mehr unreflektierter und ungetesteter Blödsinn: z.B. frac(-0.3) = -0.3.

Zitat:

Zitat von Wolfgang Mix

Und was soll nun wirklich besser sein?

Zeig mir einen Fall, wo's schlechter ist. Wie gesagt: da es in der Praxis kein Schwein interessiert, ist's auch eh egal.

[Wolfgang Mix]

Willkommen in der freundlichen Community rund um Embarcaderos/CodeGears Entwicklertool "Delphi"

In diesem Sinn

sei gegrüßt

Wolfgang

[Medium]

Tjaja, Hilfsbereitschaft und Kritikfähigkeit kommen nicht immer im Kombipack gell? :drunken:

[Wolfgang Mix]

Damit kann ich gut leben, bin ja noch lernfähig :-D

[alzaimar]

Zitat:

Zitat von gammatester

Noch mehr unreflektierter und ungetesteter Blödsinn...
...es in der Praxis kein Schwein interessiert...

Das ist kein guter Stil und zudem unhöflich, also überflüssig. Es reicht doch vollkommen aus, Fehler in der Argumentation aufzudecken, zumal sie so offensichtlich sind.

Wolfgang, deine Ignoranz bezüglich meiner und anderer Einwände untermauert das Vorurteil vom beratungsresistenden Lehrer, der irrigerweise meint, über jede Kritik erhaben zu sein: Du bist bisher auf keinen einzigen Einwand eingegangen. Das ist beschämend und eines Akademikers unwürdig. Oder solltest Du dich am Ende mit Federn schmücken, die nicht Deine eigenen sind?

[gammatester]

Zitat:

Zitat von alzaimar

Zitat:

Zitat von gammatester

Noch mehr unreflektierter und ungetesteter Blödsinn...
...es in der Praxis kein Schwein interessiert...

Das ist kein guter Stil und zudem unhöflich, also überflüssig. Es reicht doch vollkommen aus, Fehler in der Argumentation aufzudecken, zumal sie so offensichtlich sind.


Wolfgang, deine Ignoranz bezüglich meiner und anderer Einwände untermauert das Vorurteil vom beratungsresistenden Lehrer, der irrigerweise meint, über jede Kritik erhaben zu sein: Du bist bisher auf keinen einzigen Einwand eingegangen. Das ist beschämend und eines Akademikers unwürdig. Oder solltest Du dich am Ende mit Federn schmücken, die nicht Deine eigenen sind?

OK, nehm ich zurück: Ersetze "Blödsinn" durch "falsche Behauptungen". Bei der anderen Aussage wiederhole ich, was ich in #12 gesagt habe: "IsPowerOfN ist mE überflüssig, weil sie in der Praxis eigentlich keiner braucht."

Leider wird, wie schon angemerkt, auf die eigentlichen Probleme nicht eingegangen: Auch wenn die Fehler in bisherigen Funktionen beseitigt würden, bleiben ernste Schwierigkeiten (und OldGrumpys Bauchweh). Selbst mit den einfachsten (exakten) Zahlen number und base, gibt es falsche Ergebnisse. Ein Problem mit frac ist, das der Test voll daneben geht, sobald logn minimal kleiner als ein Integer ist. Dann ist frac nahe bei 1, es ist völlig egal, ob man mit IsZero oder abs() < epsilon testet. Beispiel zum Finden von solchen Werten

Delphi-Quellcode:

program mixbug;
{$apptype console}
uses math;
var
  a: extended;
  i,j: integer;
  n,b: longint;
begin
  for j:=1 to 2 do begin
    if j=1 then writeln('IsPowerOfN-Fehler mit ln(n)/ln(b)')
    else writeln('IsPowerOfN-Fehler mit math.logn');
    for b:=2 to 50 do begin
      n := b;
      i := 1;
      while n <= MaxLongint div b do begin
        inc(i);
        n := n * b;
        if j=1 then a := ln(n)/ln(b)
        else a := logn(b, n);
        if abs(frac(a)) > 0.5 then begin
          writeln(b:3, n:12, a:15:10, '   ', a-i:20, frac(a):15:10);
        end;
      end;
    end;
  end;
end.

und die Ergebnisse

Code:

IsPowerOfN-Fehler mit ln(n)/ln(b)
 02         128   7.0000000000   -4.33680868994E-0019   1.0000000000
 02       16384  14.0000000000   -8.67361737988E-0019   1.0000000000
 02    33554432  25.0000000000   -1.73472347598E-0018   1.0000000000
 02   268435456  28.0000000000   -1.73472347598E-0018   1.0000000000
 04       16384   7.0000000000   -4.33680868994E-0019   1.0000000000
 04   268435456  14.0000000000   -8.67361737988E-0019   1.0000000000
 07       16807   5.0000000000   -4.33680868994E-0019   1.0000000000
 07      823543   7.0000000000   -4.33680868994E-0019   1.0000000000
 07   282475249  10.0000000000   -8.67361737988E-0019   1.0000000000
 12    35831808   7.0000000000   -4.33680868994E-0019   1.0000000000
 14   105413504   7.0000000000   -4.33680868994E-0019   1.0000000000
 15        3375   3.0000000000   -2.16840434497E-0019   1.0000000000
 15    11390625   6.0000000000   -4.33680868994E-0019   1.0000000000
 16   268435456   7.0000000000   -4.33680868994E-0019   1.0000000000
 33    39135393   5.0000000000   -4.33680868994E-0019   1.0000000000
 35       42875   3.0000000000   -2.16840434497E-0019   1.0000000000
 35  1838265625   6.0000000000   -4.33680868994E-0019   1.0000000000
 41       68921   3.0000000000   -2.16840434497E-0019   1.0000000000
 41   115856201   5.0000000000   -4.33680868994E-0019   1.0000000000
 46   205962976   5.0000000000   -4.33680868994E-0019   1.0000000000
 47      103823   3.0000000000   -2.16840434497E-0019   1.0000000000
 48      110592   3.0000000000   -2.16840434497E-0019   1.0000000000
 49   282475249   5.0000000000   -4.33680868994E-0019   1.0000000000
IsPowerOfN-Fehler mit math.logn
 07      823543   7.0000000000   -4.33680868994E-0019   1.0000000000
 17        4913   3.0000000000   -2.16840434497E-0019   1.0000000000
 17     1419857   5.0000000000   -4.33680868994E-0019   1.0000000000
 17    24137569   6.0000000000   -4.33680868994E-0019   1.0000000000
 17   410338673   7.0000000000   -4.33680868994E-0019   1.0000000000
 34       39304   3.0000000000   -2.16840434497E-0019   1.0000000000
 34    45435424   5.0000000000   -4.33680868994E-0019   1.0000000000
 34  1544804416   6.0000000000   -4.33680868994E-0019   1.0000000000
 35       42875   3.0000000000   -2.16840434497E-0019   1.0000000000
 35  1838265625   6.0000000000   -4.33680868994E-0019   1.0000000000

[nailor]

wenn es um integer geht, dann sollte der richtige ansatz[tm] sein:

iterativ solange alle potenzen der basis berechnen, bis man entweder den zielwert trifft, größer wird als der zielwert oder einen overflow erzeugt. treffer bedeutet dabei, dass es eine potenz ist, die beiden anderen fälle, dass es keine potenz ist.

spezielle basen wie negative, null und eins sollte man dabei aussortieren, bevor man anfängt. für andere basen terminiert das ganze nach höchstens 32 bis 64 schritten, weil 2^32 bzw 2^64 die größten integer-werte darstellen.

das ganze ist unglaublich präzise, da mit integern gerechnet wird. darüber hinaus ist es relativ schnell, wenn von einem "normalen mix" von basen und zielwerten ausgegangen werden kann, da nur integer multipliziert, verglichen und gesprungen wird. alles operationen die billig und exakt sind verglichen mit allem was nur nach fließkomma, division oder logarithmus klingt.

meine bescheidene meinung.

wenn fließkomma unterstützt werden soll, sieht die sache anders aus (und deutlich schlechter/komplizierter) da müsste man nochmal sehr gründlich drüber nachdenken, ich verkneife mir hier eine prognose...

also: worum gehts genau?

[gammatester]

Hinweis: Wolfgang Mix hat am 25.10.2009 den ersten Beitrag editiert und soweit ich beurteilen kann, folgendes eingefügt:

Zitat:

Anmerkung: Bei sehr großen Zahlen werden fehlerhafte Werte zurückgegeben.

Nun kann man geteilter Meinung sein, ob in 2^7 = 128 irgendeine Zahl groß ist (geschweige denn sehr groß), aber das ist ja nur einer von vielen Fehlern. Der aktuelle Code aus dem ersten Beitrag liefert: IsPowerOfX(0.5,2) = true, was ja auch richtig ist, da 0.5 = 2^(-1). Allerdings ist auch IsPowerOfX(0.51,2) = true und wie weiterhin schon bemerkt, IsPowerOfX(x,2) = true für alle 0<x<1, dies als Folge des fehlenden abs.

Solange diese und andere Fehler nicht beseitigt sind, kann man nur dringend von der Benutzung dieses Codelibrary-Beitragskandidaten abraten.

[Wolfgang Mix]

Lieber gammatester, lieber alzaimar,

ich habe vergessen zu erwähnen, daß ich nur mit ganzen Zahlen >=1 getestet habe.
Das werde ich noch reparieren.

Des öfteren möchte man testen, ob eine [Edit] ganze [/Edit ]Zahl eine Potenz von n (>=1) ist, zb. 1,3,9,27,81,243

Zu Deinem Einwand mit 2^7 komme ich zu folgenden Ergebnissen, die von Deinen abweichen.
Hier mein Testcode für 2^1 .. 2^128

Delphi-Quellcode:

procedure TForm1.Button1Click(Sender: TObject);
var base,number,test:double;
    i:integer;
begin
   for i:= 1 to 128 do
   begin
       number:=power(2,i);
       Memo1.Lines.Add(BoolToStr(IsPowerOfx(2,number)));
   end;
   Memo1.Lines.Add(BoolToStr(IsPowerOfx(2,129)));
end;

Alle Werte liefern true bis auf den letzten, was auch richtig ist.

Wenn ich nicht sofurt auf Deine Einwände reagiere, hat das nichts mit Ignoranz zu tun,
denn ich muß gerade einen Trauerfall in meiner Familie abwickeln und bitte daher um
Veständnis.

Liebe Grüße

Wolfgang

[jbaertle]

OT: Jetzt habe ich beim ersten Lesen doch echt kurz gedacht, hier geht es um die Funktion IsPowerOn...

[Medium]

Hatte ich auch beim ersten und zweiten Mal hingucken - mein spontaner Gedanke war in etwa: "Viel code kann's ja nich sein" :lol:

[himitsu]

[OT]

Delphi-Quellcode:

function IsPowerOn: Boolean;
begin
  Result := True;
end;

function IsPowerOff: Boolean;
begin
  Result := False;
end;

Tschutschung, aber ich konnte nicht anders :duck:
[/OT]

[Wolfgang Mix]

Genial :-D

[Medium]

Jetzt noch eine "IsInSleepMode()" Methode! :love:


Hey... genuch OT nu *selfslap*

[gammatester]

Zitat:

Zitat von Wolfgang Mix

Lieber gammatester, lieber alzaimar,

ich habe vergessen zu erwähnen, daß ich nur mit ganzen Zahlen >=1 getestet habe.
Das werde ich noch reparieren.
...
Wolfgang

Das macht die Sache einerseits leichter, aber auch undurchsichtiger. Wenn alles Integerwerte wären, hätten man fast einen Einzeiler:

Delphi-Quellcode:

function IsPowerofN(x,n: int64): boolean;
  {-true wenn x>0, n>1 und x eine Potenz von n; sonst false}
begin
  if (x>0) and (n>1) then begin
    while x mod n = 0 do x := x div n;
    IsPowerofN := x=1;
  end
  else IsPowerofN := false;
end;

Das Prinzip: solange x durch n teilbar ohne Rest teilbar ist, setze x = x div n. Das ursprüngliche x war eine Potenz von n, wenn 1 überbleibt.

Sobald man Fließkommazahlen/-funktionen ins Spiel bringt, tauchen die Probleme wieder auf (in meiner Tabelle oben wären x,n integer und nur die Funktion rechnet intern mit extended).

Bist Du übrigens sicher, daß Du meinst, was Du geschrieben hast?

Da hast eine GANZE Zahl x und willst wissen, ob sie eine (ganzzahlige?) Potenz von einer reellen Zahl n > =1 ist? Zumindest die Variablennamen würde es eher anders herum vermuten lassen.

Wenn Du jetzt IsPowerOfX(2, Power(2,i)) = true hast, must Du eine andere Testfunktion als ln(x)/ln(n) verwenden. Wie sieht's denn mit dem zweiten Teil meiner Tabelle aus?


-------
Edit: Sehe gerade, daß n>1 sein muß in IsPowerofN, sonst gibt's eine Endlosschleife. Potenzen von 1 sind ja auch relativ uninteressant :)

[DP-Maintenance]

Dieses Thema wurde von "alzaimar" von "Neuen Beitrag zur Code-Library hinzufügen" nach "Programmieren allgemein" verschoben.
Grundsätzlich sollten Methoden und Algorithmen für unsere Codelibrary einen Mehrwert zur einschlägig bekannten Schulmathematik bieten, nicht in der bei Delphi mitgelieferten Library enthalten sein und vor allen Dingen sowohl allgemeingültig als auch fehlerfrei sein. Dies scheint hier nicht gegeben