Power für Integer?

Heiko · Beiträge: 3169 Erhaltene Danke: 11

Gibt es ein Power das nur Integer (Byte reicht auch) erwartet und Integer zurückgibt?
Ich will immer 2^0, ..., 2^7 berechnet haben, will aber das Ergbnis nicht runden. IntPower ist leider das gleiche wie Power, macht also nicht was der Name sagt.

delfiphan · Beiträge: 2684 Erhaltene Danke: 32

Jo: 1 shl Exponent (= 2^Exponent)

IntPower ist nicht dasselbe wie Power. IntPower ist für ganzzahlige (d.h. auch negative) Exponenten.

retnyg · Verfasst: Fr 13.05.05 20:39

ansonsten:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:

function hoch(base,exp:integer):int64;
// (c) retasmtools
var i : integer;
begin
    result := 1;
    for i := 1 to exp do result := result * base;
end;

_________________
es gibt leute, die sind genetisch nicht zum programmieren geschaffen.
in der regel haben diese leute die regel...

delfiphan · Beiträge: 2684 Erhaltene Danke: 32

Etwas Off-Topic aber trotzdem: Bei user profile icon

retnyg's Prozedur wird die Basis exp-mal zu 1 multipliziert. Eine solche Iteration ist vor allem für grössere Exponenten (bei mir aber schon ab sehr kleinen wie 4) langsamer als IntPower+Runden.
Dafür ist die Genauigkeit bei seiner Methode (mit Int64 gerechnet) garantiert.

PS:
Etwas praxisfern, aber theoretisch könnte man zuerst die Primfaktorenzerlegung von exp vornehmen und über diese Zahlen iterieren.
Beispiel 3^18 => statt 3*3*3*3*3*3*... 18-mal auszuführen, könnte man einfach ((3^3)^3)^2 rechnen. Aber okay. Bis man die Zahl faktorisiert hätte, ginge es wohl länger

BenBE · Verfasst: Fr 13.05.05 21:59

Schneller geht es über die Binär-Darstellung vom Exponenten:

Exp = 0 --> 1
Exp = 1 --> Basis
Exp and 1 = 0 --> Power(Basis, Exp shr 1);
Exp and 1 = 1 --> Power(Basis, Exp shr 1) * Basis;

Sonderfälle:
0^0 --> Exception
Basis = 0, Exp <> 0 --> 0;

_________________

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

raziel · Verfasst: Fr 13.05.05 22:05

BenBE hat folgendes geschrieben:

0^0 --> Exception

Wieso das? 0^0 = 1

_________________
JSXGraph

BenBE · Verfasst: Fr 13.05.05 22:15

raziel hat folgendes geschrieben:

BenBE hat folgendes geschrieben:

0^0 --> Exception

Wieso das? 0^0 = 1

Nein, weil dann folgende Bedingung gelten müsste:

markieren

Quelltext

1:	lim(Basis^0, Basis --> 0) = lim(0^Exp, Exp --> 0)

Diese kann aber nicht gelten, da 0^Exp nicht stetig über dem Definitionsbereich abgeleitet werden kann.

Außerdem gibt es noch genug andere Widersprüche dieser Definition.

_________________

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

delfiphan · Beiträge: 2684 Erhaltene Danke: 32

@BenBE:
Du meinst sowas: (?)
3^18 => 3^(16+2) => 3^16*3^2 => Power(3,16)*Power(3,2)

Das ergibt 16+2 = 18 Multiplikationen.
Für ((3^3)^3)^2 sind aber nur 8 Multiplikationen nötig. Bzw. wenn du schon Power aufrufst, dann nur einmal, um gleich das Schlussresultat zu erhalten (=> 1 x exp und 1 x ln).

Oder hab ich was falsch verstanden?

@raziel:
lim 0^x = 0
x->0
Aber:
lim x^0 = 1
x->0

(Jedoch gibt es tatsächlich Taschenrechner, die für 0^0 einfach 1 rausspucken.)

//Edit: BenBE war schneller ;O

BenBE · Verfasst: Fr 13.05.05 22:27

delfiphan hat folgendes geschrieben:

@BenBE:
Du meinst sowas: (?)
3^18 => 3^(16+2) => 3^16*3^2 => Power(3,16)*Power(3,2)

Nicht ganz:
3^18 => (3^9)^2 => ((3^4)^2 * 3)^2 => (((3^2)^2)^2 * 3)^2

Das sind zwar ein paar mehr Multiplikationen (für kleine Zahlen), aber es entfällt der Aufwand für's Faktorisieren.

Außerdem wird diese Methode auch häufig zum Potenzieren Modulo genutz (z.B. bei Rabbin-Miller und RSA).

_________________

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

retnyg · Verfasst: Fr 13.05.05 22:39

BenBE hat folgendes geschrieben:

Schneller geht es über die Binär-Darstellung vom Exponenten:

Exp = 0 --> 1
Exp = 1 --> Basis
Exp and 1 = 0 --> Power(Basis, Exp shr 1);
Exp and 1 = 1 --> Power(Basis, Exp shr 1) * Basis;

Sonderfälle:
0^0 --> Exception
Basis = 0, Exp <> 0 --> 0;

könntest du das in ne delphi funktion verpacken ?

_________________
es gibt leute, die sind genetisch nicht zum programmieren geschaffen.
in der regel haben diese leute die regel...

BenBE · Verfasst: Fr 13.05.05 22:57

retnyg hat folgendes geschrieben:

BenBE hat folgendes geschrieben:

Schneller geht es über die Binär-Darstellung vom Exponenten:

Exp = 0 --> 1
Exp = 1 --> Basis
Exp and 1 = 0 --> Power(Basis, Exp shr 1);
Exp and 1 = 1 --> Power(Basis, Exp shr 1) * Basis;

Sonderfälle:
0^0 --> Exception
Basis = 0, Exp <> 0 --> 0;

könntest du das in ne delphi funktion verpacken ?

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:

Procedure FastPower(B, E: Integer): Int64;
begin
    If B = 0 Then
    Begin
        If E = 0 Then Raise EInvalidOperation.Create('Calculating 0^0.');
        Result := 0;
        Exit;
    end;

    If E = 0 Then
    Begin
        Result := 1;
        Exit;
    end
    else if E = 1 Then
    Begin
        Result := B;
        Exit;
    end
    else if E and 1 = 0 Then
    Begin
        Result := FastPower(B, E shr 1);
        Result := Sqr(Result);
        Exit;
    end
    else 
    Begin
        Result := FastPower(B, E shr 1);
        Result := Sqr(Result) * B;
        Exit;
    end;
end;

Für E >= 0!!!

_________________

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Heiko · Beiträge: 3169 Erhaltene Danke: 11

delfiphan hat folgendes geschrieben:

IntPower ist nicht dasselbe wie Power. IntPower ist für ganzzahlige (d.h. auch negative) Exponenten.

Aber keine vollständiger Power mit Integer. Der Exponent ist nur ein Integer. Ich will aber Base, Exponent und Result als Integer (oder Byte).

Aso und ihr habt ja auch ein paar andere Vorschläge gemacht, die ich leider nicht richtig gebrauchen kann, da ich jedes 8. mal 2^0 brauche. Ich werde es jetzt wohl anders Regeln

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:

procedure IntegerPowerOfTwo(Exponent: Byte);
begin
 case Exponent of
  0: Result:=1;
  1: Result:=2;
  2: Result:=4;
  3: Result:=8;
  4: Result:=16;
  5: Result:=32;
  6: Result:=64;
  7: Result:=128;
end;

Ich hatte eigentlich keine Lust so eine Prozedur mit einzubauen, weshalb ich es mit Power machen wollte. Aber ich glaube bald, dass die Variante am schnellsten sein wird, da ich ja weiß welche Exponenten und Basen ich immer habe, wodurch ich schon das Ergebnis in den Quellcode reinimplementieren kann. Die Variante mit round (oder Trunc) wird sicherlich nicht schneller sein.

Trotzdem thx für die Antworten. Wenn es bessere Varianten gibt bin ich immer noch offen :wink:

.

delfiphan · Beiträge: 2684 Erhaltene Danke: 32

Heiko: Du hast den ersten Teil meines ersten Beitrags einfach ignoriert

1 shl Exponent ist die Lösung.

(1 shl 0) = 1
(1 shl 1) = 2
(1 shl 2) = 4
(1 shl 3) = 8
(1 shl 4) = 16
...

(Die Bemerkung ist jetzt zwar überflüssig, trotzdem: Statt ein solches Case wäre es wohl geschickter, eine konstante array zu definieren)

Heiko · Beiträge: 3169 Erhaltene Danke: 11

sry. Ich hatte ihn nicht ignoriert, aber vergessen, da ich die anderen gelesen noch hatte.

thx delfiphan für deine Erinnerung :wink:

.

retnyg · Verfasst: Sa 14.05.05 13:52

Heiko hat folgendes geschrieben:

markieren

Delphi-Quelltext

1:	procedure IntegerPowerOfTwo(Exponent: Byte);

Wenn es bessere Varianten gibt bin ich immer noch offen

wenn du deine prozeduren schnell machen willst, solltest du keine anderen variablentypen als 32bittige verwenden, da der prozessor sonst immer erst konvertieren muss

meine bruteforce-passwort generator prozedur wurde alleine durch umstellen einiger variablen von byte auf dword um gut 20% schneller

_________________
es gibt leute, die sind genetisch nicht zum programmieren geschaffen.
in der regel haben diese leute die regel...

Heiko · Beiträge: 3169 Erhaltene Danke: 11

Ich brauche das immer als Byte, da ich immer Byteweise bei meinem Packprogramm schreibe :wink:

, ansonsten nehem ich auch immer Integer oder Cardinal.

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme