Entwickler-Ecke
Delphi Language (Object-Pascal) / CLX - Power für Integer?
Heiko - Fr 13.05.05 20:18
Titel: Power für Integer?
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 - Fr 13.05.05 20:20
Jo: 1 shl Exponent (= 2^Exponent)
IntPower ist nicht dasselbe wie Power. IntPower ist für ganzzahlige (d.h. auch negative) Exponenten.
retnyg - Fr 13.05.05 20:39
ansonsten:
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
| function hoch(base,exp:integer):int64;
var i : integer;
begin
result := 1;
for i := 1 to exp do result := result * base;
end; |
delfiphan - Fr 13.05.05 21:01
Etwas Off-Topic aber trotzdem: Bei
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 - 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;
raziel - Fr 13.05.05 22:05
| BenBE hat folgendes geschrieben: |
| 0^0 --> Exception |
Wieso das? 0^0 = 1
BenBE - 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:
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.
delfiphan - Fr 13.05.05 22:16
@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 - 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).
retnyg - 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 ?
BenBE - 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 ? |
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!!!
Heiko - Sa 14.05.05 09:37
| 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
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 - Sa 14.05.05 11:12
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 - Sa 14.05.05 12:05
sry. Ich hatte ihn nicht ignoriert, aber vergessen, da ich die anderen gelesen noch hatte.
thx delfiphan für deine Erinnerung :wink: .
retnyg - Sa 14.05.05 13:52
| Heiko hat folgendes geschrieben: |
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
Heiko - Sa 14.05.05 17:42
Ich brauche das immer als Byte, da ich immer Byteweise bei meinem Packprogramm schreibe :wink: , ansonsten nehem ich auch immer Integer oder Cardinal.
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!