Potenzen

Übersicht

BlitzBasic

Allgemein

Gehe zu Seite 1, 2 Weiter

	Triton Betreff: Potenzen	Fr, Dez 23, 2005 23:14 Antworten mit Zitat
Dies ist nicht direkt ein Programmierproblem. Mir fehlt es vielmehr an einer Idee um dieses mathematisch begründete Problem zu lösen. Algorithmisch umsetzen dürfte dann einfach sein. Nun, angenommen ich will die zahl 2^10000 (oder 2^33000000 oder sonst eine hohe Potenz) ermitteln. Wie schaffe ich das, ohne zuvor 2^1 bis 2^9999 ausrechnen zu müssen? Oder allgemeiner: Hat jemand ne Idee, wie man a^b aus rechnen könnte, ohne zuvor a^b-1, a^b-2, ... a^1 ausrechnen zu müssen? Bisher sähe eine Funktion so aus (die aber 2^1 bis 2^9999 berechnet, was freilich unnötiger aufwand ist). Pseudocode, der nur bis 2^31 funzt: Code: [AUSKLAPPEN] [EINKLAPPEN] ;--- Function ahochb(a,b) ;a;b element N If a = 0 Then Return 0 If b = 0 Then Return 1 c=1 d=a While c < b c = c + 1 a=a*d Wend Return a End Function Vorschläge?
Coding: silizium-net.de \| Portfolio: Triton.ch.vu

Triton

Betreff: Potenzen

Fr, Dez 23, 2005 23:14
Antworten mit Zitat

Dies ist nicht direkt ein Programmierproblem. Mir fehlt es vielmehr an einer Idee um dieses mathematisch begründete Problem zu lösen. Algorithmisch umsetzen dürfte dann einfach sein.

Nun, angenommen ich will die zahl 2^10000 (oder 2^33000000 oder sonst eine hohe Potenz) ermitteln. Wie schaffe ich das, ohne zuvor 2^1 bis 2^9999 ausrechnen zu müssen?

Oder allgemeiner:
Hat jemand ne Idee, wie man a^b aus rechnen könnte, ohne zuvor a^b-1, a^b-2, ... a^1 ausrechnen zu müssen?

Bisher sähe eine Funktion so aus (die aber 2^1 bis 2^9999 berechnet, was freilich unnötiger aufwand ist). Pseudocode, der nur bis 2^31 funzt:

Code: [AUSKLAPPEN]

;---
Function ahochb(a,b) ;a;b element N
If a = 0 Then Return 0
If b = 0 Then Return 1
c=1
d=a
While c < b
c = c + 1
a=a*d
Wend
Return a
End Function

Vorschläge?

Coding: silizium-net.de | Portfolio: Triton.ch.vu

	Mr.Keks	Fr, Dez 23, 2005 23:32 Antworten mit Zitat
Mir file jetzt spontan nur folgendes ein: (a^(b/2) * a^(b/2)) Für ungerade Zahlen könnte man dann nochmal mit a multiplizieren. aber so sollte sich der rechenaufwandt schonmal halbieren lassen...
MrKeks.net

Mr.Keks

Fr, Dez 23, 2005 23:32
Antworten mit Zitat

Mir file jetzt spontan nur folgendes ein:
(a^(b/2) * a^(b/2))
Für ungerade Zahlen könnte man dann nochmal mit a multiplizieren. aber so sollte sich der rechenaufwandt schonmal halbieren lassen...

MrKeks.net

	Triton	Fr, Dez 23, 2005 23:36 Antworten mit Zitat
das Problem sind die vielen Rechenschritte bei hohen Exponenten. Bei 2^10000 muss ich eben schon 9999 mal den kack ausführen. Ich könnte natürlich 4^5000, oder 8^2500 oder 16^1250 usw. rechnen, was die Anzahl der Schritte verringern würde, aber das wäre ja nur für den spefiellen fall 2^10000. Eine Systematisierung wär wohl nciht so einfach (z.B bei 23^101?).
Coding: silizium-net.de \| Portfolio: Triton.ch.vu

Triton

Fr, Dez 23, 2005 23:36
Antworten mit Zitat

das Problem sind die vielen Rechenschritte bei hohen Exponenten.
Bei 2^10000 muss ich eben schon 9999 mal den kack ausführen.

Ich könnte natürlich 4^5000, oder 8^2500 oder 16^1250 usw.
rechnen, was die Anzahl der Schritte verringern würde, aber das wäre ja nur für den spefiellen fall 2^10000. Eine Systematisierung wär wohl nciht so einfach (z.B bei 23^101?).

Coding: silizium-net.de | Portfolio: Triton.ch.vu

	hectic Sieger des IS Talentwettbewerb 2006	Fr, Dez 23, 2005 23:37 Antworten mit Zitat
Die maximale Zahl die du in eine Variable in BB speichern kannst liegt etwa im Bereich von 2^128. Potenzrechnung wird auch so gemacht. Hier mal ein Beispiel:Code: [AUSKLAPPEN] [EINKLAPPEN] a=2 b=128 Print a^b WaitKey Falls größere Zahlen benötigt werden, fällt mir keine andere Möglichkeit ein als es über eine Stringrechnung zu machen.

hectic

Sieger des IS Talentwettbewerb 2006

Fr, Dez 23, 2005 23:37
Antworten mit Zitat

Die maximale Zahl die du in eine Variable in BB speichern kannst liegt etwa im Bereich von 2^128. Potenzrechnung wird auch so gemacht. Hier mal ein Beispiel:Code: [AUSKLAPPEN]

a=2
b=128
Print a^b
WaitKey

Falls größere Zahlen benötigt werden, fällt mir keine andere Möglichkeit ein als es über eine Stringrechnung zu machen.

	Triton	Fr, Dez 23, 2005 23:43 Antworten mit Zitat
Jaja, ich bin da schon einige Schritte weiter als du Ich kann ja 2^10000 längst berechnen (mit absoluter Genauigkeit) mit nem eigenen Programm. Das ist mir nur viel zu langsam. Mit speziellem, auf 2er Potenzen geeichten Algorithmus dauert das etwa 10 Sekunden. Ziel ist es 2^33000000 in irdischer Zeit (Sekunden bis Stunden) auszurechnen. Das würde bisher aber astronomisch lange Zeit in Anspruch nehmen.
Coding: silizium-net.de \| Portfolio: Triton.ch.vu

Triton

Fr, Dez 23, 2005 23:43
Antworten mit Zitat

Jaja, ich bin da schon einige Schritte weiter als du Wink

Ich kann ja 2^10000 längst berechnen (mit absoluter Genauigkeit) mit nem eigenen Programm. Das ist mir nur viel zu langsam. Mit speziellem, auf 2er Potenzen geeichten Algorithmus dauert das etwa 10 Sekunden.

Ziel ist es 2^33000000 in irdischer Zeit (Sekunden bis Stunden) auszurechnen. Das würde bisher aber astronomisch lange Zeit in Anspruch nehmen.

Coding: silizium-net.de | Portfolio: Triton.ch.vu

Zuletzt bearbeitet von Triton am Fr, Dez 23, 2005 23:45, insgesamt einmal bearbeitet

	Dreamora	Fr, Dez 23, 2005 23:44 Antworten mit Zitat
Also bei Zweierpotenzen wäre ohne Frage BitShift der schnellste Weg: 2^1000 = 2 shl 1000 Bei anderen kann man zumindest in Float über "NäherungsCheats" viel Speed rausholen, wie bei Sqr auch. Die, die ich gesehen habe und auch einigermassen verstanden, basieren alle auch direkt oder indirekt auf BitShift
Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen.

Dreamora

Fr, Dez 23, 2005 23:44
Antworten mit Zitat

Also bei Zweierpotenzen wäre ohne Frage BitShift der schnellste Weg:

2^1000 = 2 shl 1000

Bei anderen kann man zumindest in Float über "NäherungsCheats" viel Speed rausholen, wie bei Sqr auch. Die, die ich gesehen habe und auch einigermassen verstanden, basieren alle auch direkt oder indirekt auf BitShift

Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen.

Zuletzt bearbeitet von Dreamora am Sa, Dez 24, 2005 2:37, insgesamt einmal bearbeitet

	Mr.Keks	Sa, Dez 24, 2005 0:58 Antworten mit Zitat
hihi.. dreamora... irgendwie erscheint mir das sinnlos . nach der shrmasche muss man ja dann doch wieder zur dezimalzahl umrechnen, wozu man all das gerechne braucht, das triton hier ja umgehen will ^^.
MrKeks.net

Mr.Keks

Sa, Dez 24, 2005 0:58
Antworten mit Zitat

hihi.. dreamora... irgendwie erscheint mir das sinnlos Wink

. nach der shrmasche muss man ja dann doch wieder zur dezimalzahl umrechnen, wozu man all das gerechne braucht, das triton hier ja umgehen will ^^.

MrKeks.net

	Dreamora	Sa, Dez 24, 2005 2:37 Antworten mit Zitat
??? Warum sollte man das müssen? /2 = shr 1 *2 = shl 1 Wenn du also a = 2^1000 hast ist das das gleiche a = 2 shl 1000, nur das letzteres in 1 Schritt zu machen ist (unter der Annahme, es gäbe überhaupt einen Datentyp der das annimmt. Da das aber für beide Fälle nicht existiert im numerischen bereich, ist das egal) Er wollte etwas, was ihm die rekursive Berechnung erspart und bei 2^X ist dies durch shl und shr der Fall. Für alle anderen Werte gibt es Näherungsmethoden die im Bereich der jeweiligen Genauigkeit arbeiten, die die rekursiven Berechnung ebenfalls verhindern.
Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen.

Dreamora

Sa, Dez 24, 2005 2:37
Antworten mit Zitat

???
Warum sollte man das müssen?

/2 = shr 1
*2 = shl 1

Wenn du also a = 2^1000 hast ist das das gleiche a = 2 shl 1000, nur das letzteres in 1 Schritt zu machen ist (unter der Annahme, es gäbe überhaupt einen Datentyp der das annimmt. Da das aber für beide Fälle nicht existiert im numerischen bereich, ist das egal)

Er wollte etwas, was ihm die rekursive Berechnung erspart und bei 2^X ist dies durch shl und shr der Fall.
Für alle anderen Werte gibt es Näherungsmethoden die im Bereich der jeweiligen Genauigkeit arbeiten, die die rekursiven Berechnung ebenfalls verhindern.

Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen.

	Absoluter Beginner	Sa, Dez 24, 2005 3:17 Antworten mit Zitat
potenz = Exp(Log(basis)*exponent)
Error Inside!

Absoluter Beginner

Sa, Dez 24, 2005 3:17
Antworten mit Zitat

potenz = Exp(Log(basis)*exponent)

Error Inside!

	Triton	Sa, Dez 24, 2005 3:30 Antworten mit Zitat
Absoluter Beginner hat Folgendes geschrieben: potenz = Exp(Log(basis)exponent) damit erhält man dann den Exponenten der Zehnerpotenz, die aber meist ein unschöner Bruch wäre und damit nicht nutzbar. --- Ich denke die einzige praktikable Lösung ist es, kleinere Potenzen zu finden. Ich hab das mal gemessen. Hier mal paar Beispielwerte, wie lange das dauert: Primfaktorzerlegung: 1000=222555 2^1000 - 16s 672ms 4^500 - 8s 406ms 16^250 - 8s 260ms 256^125 - 6s 190ms (256^5)^25 - 5s 529ms ((256^5)^5)^5 - 5s 750ms Man muss also den Exponenten in seine Primteiler zerlegen und die Basis schrittweise damit Potenzieren (und den Exponenten dadurch teilen). Es ist also grundsätzlich schneller eine große Basis und einen kleinen Exponenten zu haben, als eine kleine Basis und einen großen Exponenten. Also: 2^1000 = (((((((2^2)^2)^2)^5)^5)^5) Das ist zwar immernoch rekursiv, aber mit wesentlich weniger Schritten und somit viel schneller. Ein Problem wäre es dann natürlich, wenn der Exponent eine Primzahl ist. In dem Fall berechnet man bis e-1 (wenn e der exponent ist) nach genannter Methode und multipliziert nochmal mit e. Werde das heute/morgen mal umsetzen müssen.
Coding: silizium-net.de \| Portfolio: Triton.ch.vu

Triton

Sa, Dez 24, 2005 3:30
Antworten mit Zitat

Absoluter Beginner hat Folgendes geschrieben:

potenz = Exp(Log(basis)*exponent)

damit erhält man dann den Exponenten der Zehnerpotenz, die aber meist ein unschöner Bruch wäre und damit nicht nutzbar.

---
Ich denke die einzige praktikable Lösung ist es, kleinere Potenzen zu finden.

Ich hab das mal gemessen. Hier mal paar Beispielwerte, wie lange das dauert:

Primfaktorzerlegung:
1000=2*2*2*5*5*5

2^1000 - 16s 672ms
4^500 - 8s 406ms
16^250 - 8s 260ms
256^125 - 6s 190ms
(256^5)^25 - 5s 529ms
((256^5)^5)^5 - 5s 750ms

Man muss also den Exponenten in seine Primteiler zerlegen und die Basis schrittweise damit Potenzieren (und den Exponenten dadurch teilen).
Es ist also grundsätzlich schneller eine große Basis und einen kleinen Exponenten zu haben, als eine kleine Basis und einen großen Exponenten.
Also: 2^1000 = (((((((2^2)^2)^2)^5)^5)^5)
Das ist zwar immernoch rekursiv, aber mit wesentlich weniger Schritten und somit viel schneller.

Ein Problem wäre es dann natürlich, wenn der Exponent eine Primzahl ist.
In dem Fall berechnet man bis e-1 (wenn e der exponent ist) nach genannter Methode und multipliziert nochmal mit e.

Werde das heute/morgen mal umsetzen müssen.

Coding: silizium-net.de | Portfolio: Triton.ch.vu

Zuletzt bearbeitet von Triton am Sa, Dez 24, 2005 3:41, insgesamt einmal bearbeitet

	Dreamora	Sa, Dez 24, 2005 3:38 Antworten mit Zitat
Das ist als solches nicht verwunderlich, da ein kleinerer Exponent ja weniger Multiplikationen heisst. Grössere Basen indes sind kein so grosses Problem, da der Multiplikator immer noch mit 4 Byte arbeitet, egal ob da jetzt 2 oder 200000 drin steht. Das Problem wird bloss, dass Primfaktorzerlegung dummerweise auch nicht zu den Dingen gehört, die man in einem Schritt erledigen kann, wohingegen die Exp(log) Lösung zumindest in einem gewissen Rahmen in einem Schritt zu lösen ist. (log ist die mit Abstand langsamste mathematische Funktion die es gibt, noch einige Ecken langsamer als Sqr ... ist aber auch gut so, sonst hätte es bis vor kurzem nämlich keine Verschlüsselung im Internet gegeben )
Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen.

Dreamora

Sa, Dez 24, 2005 3:38
Antworten mit Zitat

Das ist als solches nicht verwunderlich, da ein kleinerer Exponent ja weniger Multiplikationen heisst. Grössere Basen indes sind kein so grosses Problem, da der Multiplikator immer noch mit 4 Byte arbeitet, egal ob da jetzt 2 oder 200000 drin steht.
Das Problem wird bloss, dass Primfaktorzerlegung dummerweise auch nicht zu den Dingen gehört, die man in einem Schritt erledigen kann, wohingegen die Exp(log) Lösung zumindest in einem gewissen Rahmen in einem Schritt zu lösen ist. (log ist die mit Abstand langsamste mathematische Funktion die es gibt, noch einige Ecken langsamer als Sqr ... ist aber auch gut so, sonst hätte es bis vor kurzem nämlich keine Verschlüsselung im Internet gegeben Wink

)

Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen.

	Triton	Sa, Dez 24, 2005 3:46 Antworten mit Zitat
Naja, Primfaktorenzerlegungen von Zahlen bis unterhalb von 2^31 (größere exponenten kann das Programm dann nicht mehr handhaben) dürften noch recht schnell gehen. Und da das besagte Ziel 2^33000000 sein soll, und 33 mio noch recht klein ist, sollte dies auch ncoh einem Zeitgewinn entsprechen. Aber das sind nur Vermutungen, man müsste es testen.
Coding: silizium-net.de \| Portfolio: Triton.ch.vu

Triton

Sa, Dez 24, 2005 3:46
Antworten mit Zitat

Naja, Primfaktorenzerlegungen von Zahlen bis unterhalb von 2^31 (größere exponenten kann das Programm dann nicht mehr handhaben)
dürften noch recht schnell gehen.

Und da das besagte Ziel 2^33000000 sein soll, und 33 mio noch recht klein ist, sollte dies auch ncoh einem Zeitgewinn entsprechen.

Aber das sind nur Vermutungen, man müsste es testen.

Coding: silizium-net.de | Portfolio: Triton.ch.vu

	Dreamora	Sa, Dez 24, 2005 11:39 Antworten mit Zitat
Das Problem ist, dass eine Primfaktorzerlegung Primfaktoren braucht. Bei kleinen Zahlen kein Problem, bei grossen Zahlen wie die genannte wird alleine das bestimmen "ob prim" schon seine Zeit in Anspruch nehmen, speziell wenn es eine Primzahl ist ...
Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen.

Dreamora

Sa, Dez 24, 2005 11:39
Antworten mit Zitat

Das Problem ist, dass eine Primfaktorzerlegung Primfaktoren braucht. Bei kleinen Zahlen kein Problem, bei grossen Zahlen wie die genannte wird alleine das bestimmen "ob prim" schon seine Zeit in Anspruch nehmen, speziell wenn es eine Primzahl ist ...

Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen.

	Ctuchik	Di, Dez 27, 2005 21:32 Antworten mit Zitat
Du musst es nicht in Primfaktoren zerlegen: x^a * x^b = x^(a+b) Das heißt du musst den Exponenten nur in zwei beliebige Zahlen zerlegen. Optimal natürlich in 2 gleich große. Also wenn du 2^e berechnest dann würde ich den Exponenten zerlegen mit: a = Floor(e/2) + (e Mod 2) b = e - a und dann jeweils 2^a * 2^b ausrechnen, die sich dann wiederum in kleinere Zahlen zerlegen lassen. EDIT: Sowas in der Art: Code: [AUSKLAPPEN] [EINKLAPPEN] test = MyExp(2,15) Print test WaitKey() End Function MyExp(basis%,e%) If (e = 1) Return basis a = Floor(e/2) + (e Mod 2) b = e - a erg_a = MyExp(basis,a) erg_b = MyExp(basis,b) erg% = erg_a * erg_b Return erg End Function
Zu den Nebenwirkungen gehören trockener Mund, Übelkeit, Erbrechen, Harnstau, schmerzhafter rektaler Juckreiz, Halluzinationen, Demenz, Psychose, Koma, Tod und Mundgeruch! Magie eignet sich nicht für alle! Fraget euren Arzt oder Apotheker!

Ctuchik

Di, Dez 27, 2005 21:32
Antworten mit Zitat

Du musst es nicht in Primfaktoren zerlegen:

x^a * x^b = x^(a+b)

Das heißt du musst den Exponenten nur in zwei beliebige Zahlen zerlegen.
Optimal natürlich in 2 gleich große.
Also wenn du 2^e berechnest dann würde ich den Exponenten zerlegen mit:
a = Floor(e/2) + (e Mod 2)
b = e - a

und dann jeweils 2^a * 2^b ausrechnen, die sich dann wiederum in kleinere Zahlen zerlegen lassen.

EDIT: Sowas in der Art:
Code: [AUSKLAPPEN]

test = MyExp(2,15)
Print test
WaitKey()
End

Function MyExp(basis%,e%)
If (e = 1) Return basis
a = Floor(e/2) + (e Mod 2)
b = e - a
erg_a = MyExp(basis,a)
erg_b = MyExp(basis,b)
erg% = erg_a * erg_b
Return erg
End Function

Zu den Nebenwirkungen gehören trockener Mund, Übelkeit, Erbrechen, Harnstau, schmerzhafter rektaler Juckreiz, Halluzinationen, Demenz, Psychose, Koma, Tod und Mundgeruch!
Magie eignet sich nicht für alle!
Fraget euren Arzt oder Apotheker!

	Triton	Di, Dez 27, 2005 22:10 Antworten mit Zitat
Gute Idee, aber folgendes Problem: wenn ich so vorgehe wie du ( 2^15 = 2^7 * 2^8 = 32768 ) dann muss ich insgesamt 7+8=15 mal die Potenz bilden. Somit dürfte deine Fkt. kein Plus an Geschwindigket bringen, da ich bei a^b trotzdem stehts b mal die Potenz bilden müsste. Wenn ich allerdings 15 in seine Primfaktoren zerlege (3*5=15), dann erhalte ich 2^15 = (2^3)^5 = 32768 Wo ich nur 2+3+5=10 mal die Potenz bilden muss. Was dann bei sehr großen Zahlen - um die es sich hier dreht - einen starken Geschwindigkeitszuwachs bedeuten dürfte. -- hab btw. noch eine Primfaktorenzerlegungsprog geschrieben und ins codearchiv gepostet: https://www.blitzforum.de/viewtopic.php?p=165291 Dreamora hat Folgendes geschrieben: Das Problem ist, dass eine Primfaktorzerlegung Primfaktoren braucht. Bei kleinen Zahlen kein Problem, bei grossen Zahlen wie die genannte wird alleine das bestimmen "ob prim" schon seine Zeit in Anspruch nehmen, speziell wenn es eine Primzahl ist ... Erübrigt sich dann quasi. Es geht ausreichend schnell (bei mir immer deutlich unter 20 ms).
Coding: silizium-net.de \| Portfolio: Triton.ch.vu

Triton

Di, Dez 27, 2005 22:10
Antworten mit Zitat

Gute Idee, aber folgendes Problem:

wenn ich so vorgehe wie du ( 2^15 = 2^7 * 2^8 = 32768 )
dann muss ich insgesamt 7+8=15 mal die Potenz bilden.
Somit dürfte deine Fkt. kein Plus an Geschwindigket bringen, da ich bei
a^b trotzdem stehts b mal die Potenz bilden müsste.

Wenn ich allerdings 15 in seine Primfaktoren zerlege (3*5=15),
dann erhalte ich

2^15 = (2^3)^5 = 32768

Wo ich nur 2+3+5=10 mal die Potenz bilden muss.
Was dann bei sehr großen Zahlen - um die es sich hier dreht - einen starken Geschwindigkeitszuwachs bedeuten dürfte.

--
hab btw. noch eine Primfaktorenzerlegungsprog geschrieben und ins codearchiv gepostet:

https://www.blitzforum.de/viewtopic.php?p=165291

Dreamora hat Folgendes geschrieben:

Erübrigt sich dann quasi.
Es geht ausreichend schnell (bei mir immer deutlich unter 20 ms).

Coding: silizium-net.de | Portfolio: Triton.ch.vu

	Ctuchik	Di, Dez 27, 2005 22:44 Antworten mit Zitat
ok, dann hab ich hier noch basierend auf einer anderen Idee folgendes Programm geschrieben: Code: [AUSKLAPPEN] [EINKLAPPEN] test = MyExp(2,15) Print test WaitKey() End Function MyExp(basis%,e%) count = -1 a = 1 While (a < e) a = a Shl 1 count = count + 1 Wend b = e - (a Shr 1) y = basis For a=1 To count y = y * y Next If (b = 1) Then z = basis Else z = MyExp(basis,b) End If erg = yz Return erg End Function Vielleicht kannst du da einfach mal die Geschwindigkeit testen, ich weiss nicht wie schnell es ist! Bei mir ist es etwa 3,5 mal schneller als das andere. Wie es im Vergleich zu dem mit vorherigem Primzahlzerlegen abschneidet weiss ich nicht. Idee ist folgende: basis^e soll berechnet werden. Ich suche die Zweierpotenz die möglichst nah unter e liegt. Also bei e = 19 z.B. 2^4 = 16 Dann ist basis^19 = basis^16 basis^3 basis^16 lässt sich dann sehr schnell berechnen weil immer nur quadriert wird, nämlich ((((basis^2)^2)^2)^2). basis^3 wird dann rekursiv nach dem selben Prinzip berechnet. Das sollte vor allem bei Primzahlen die sich nicht in Primfaktoren zerlegen lassen vorteilhaft sein, da dort die andere Methode nicht effektiv ist!
Zu den Nebenwirkungen gehören trockener Mund, Übelkeit, Erbrechen, Harnstau, schmerzhafter rektaler Juckreiz, Halluzinationen, Demenz, Psychose, Koma, Tod und Mundgeruch! Magie eignet sich nicht für alle! Fraget euren Arzt oder Apotheker!

Ctuchik

Di, Dez 27, 2005 22:44
Antworten mit Zitat

ok, dann hab ich hier noch basierend auf einer anderen Idee folgendes Programm geschrieben:
Code: [AUSKLAPPEN]

test = MyExp(2,15)
Print test
WaitKey()
End

Function MyExp(basis%,e%)
count = -1
a = 1
While (a < e)
a = a Shl 1
count = count + 1
Wend
b = e - (a Shr 1)
y = basis
For a=1 To count
y = y * y
Next
If (b = 1) Then
z = basis
Else
z = MyExp(basis,b)
End If
erg = y*z
Return erg
End Function

Vielleicht kannst du da einfach mal die Geschwindigkeit testen, ich weiss nicht wie schnell es ist! Bei mir ist es etwa 3,5 mal schneller als das andere. Wie es im Vergleich zu dem mit vorherigem Primzahlzerlegen abschneidet weiss ich nicht.

Idee ist folgende:
basis^e soll berechnet werden.
Ich suche die Zweierpotenz die möglichst nah unter e liegt.
Also bei e = 19 z.B. 2^4 = 16
Dann ist basis^19 = basis^16 * basis^3
basis^16 lässt sich dann sehr schnell berechnen weil immer nur quadriert wird, nämlich ((((basis^2)^2)^2)^2).
basis^3 wird dann rekursiv nach dem selben Prinzip berechnet.
Das sollte vor allem bei Primzahlen die sich nicht in Primfaktoren zerlegen lassen vorteilhaft sein, da dort die andere Methode nicht effektiv ist!

	Triton	Mi, Dez 28, 2005 3:31 Antworten mit Zitat
Wieder eine gute Idee, die noch schneller sein dürfte, aber das Problem hierbei ist, dass bei Stringrechnung und Zahlen über 2^31 eine 2er Potenz nicht so einfach über "a = a Shl 1" gebildet werden kann. Somit hätte ich trotz basis^19 = basis^16 * basis^3 wieder 19 mal das potenzieren. Zitat: Vielleicht kannst du da einfach mal die Geschwindigkeit testen Kann ich leider nicht, da das ganze wie gesagt beim String-Langzahl-Rechnen nicht mehr funktioniert. Zitat: die sich nicht in Primfaktoren zerlegen lassen vorteilhaft sein, da dort die andere Methode nicht effektiv ist! Nicht unbedingt. Wenn man a^p nach meiner Methode (Primfaktorzerlegung) ausrechnen will, und man erkennt, dass p eine Primzahl ist, so nimmt man einfach die Pf.zerlgung von p-1 und multipliziert am ende nochmal mit a.
Coding: silizium-net.de \| Portfolio: Triton.ch.vu

Triton

Mi, Dez 28, 2005 3:31
Antworten mit Zitat

Wieder eine gute Idee, die noch schneller sein dürfte, aber das Problem hierbei ist, dass bei Stringrechnung und Zahlen über 2^31 eine 2er Potenz nicht so einfach über "a = a Shl 1" gebildet werden kann.

Somit hätte ich trotz basis^19 = basis^16 * basis^3 wieder 19 mal das potenzieren.

Zitat:

Vielleicht kannst du da einfach mal die Geschwindigkeit testen

Kann ich leider nicht, da das ganze wie gesagt beim String-Langzahl-Rechnen nicht mehr funktioniert.

Zitat:

die sich nicht in Primfaktoren zerlegen lassen vorteilhaft sein, da dort die andere Methode nicht effektiv ist!

Nicht unbedingt.

Wenn man a^p nach meiner Methode (Primfaktorzerlegung) ausrechnen
will, und man erkennt, dass p eine Primzahl ist, so nimmt man einfach
die Pf.zerlgung von p-1 und multipliziert am ende nochmal mit a.

Coding: silizium-net.de | Portfolio: Triton.ch.vu

	Ctuchik	Mi, Dez 28, 2005 11:22 Antworten mit Zitat
Zitat: das Problem hierbei ist, dass bei Stringrechnung und Zahlen über 2^31 eine 2er Potenz nicht so einfach über "a = a Shl 1" gebildet werden kann. Es wird lediglich nach der größten Zweierpotenz gesucht die noch kleiner ist als der Exponent (!) um diesen dann zu zerlegen. Auch bei 2^33000000 ist der Exponent ja "nur" 33000000, was noch im Bereich eines 32-Bit Integers liegt. Zitat: Wenn man a^p nach meiner Methode (Primfaktorzerlegung) ausrechnen will, und man erkennt, dass p eine Primzahl ist, so nimmt man einfach die Pf.zerlgung von p-1 und multipliziert am ende nochmal mit a. Das stimmt natürlich. Trotzdem kann dabei aber eine Zahl entstehen die z.B. nur durch 2 teilbar ist, also nur 2 Primfaktoren hat. Vielleicht kannst du die Funktionen zum String-Rechnen hier mal posten, ich würde mein programm gerne mal mit großen Zahlen ausprobieren. EDIT: Habs im Codearchiv gefunden! Für 2^1000 braucht er 98ms Für 2^10000 braucht er 17400ms 2^100000 hab ich mich noch nicht getraut ^^ Hab jetzt auch keine Zeit, ich werds später oder morgen weiter testen! EDIT2: Ich halte 2^33000000 für ein bischen arg krass erst recht wenn mans genau haben will. Vor allem BB ist dafür sicher zu langsam. Der Windows-Rechner macht übrigens noch bis etwa 2^142000 mit danach sind ihm die Zahlen zu groß. Und allein 2^140000 hätte schon 42747 Stellen!
Zu den Nebenwirkungen gehören trockener Mund, Übelkeit, Erbrechen, Harnstau, schmerzhafter rektaler Juckreiz, Halluzinationen, Demenz, Psychose, Koma, Tod und Mundgeruch! Magie eignet sich nicht für alle! Fraget euren Arzt oder Apotheker!

Ctuchik

Mi, Dez 28, 2005 11:22
Antworten mit Zitat

Zitat:

das Problem hierbei ist, dass bei Stringrechnung und Zahlen über 2^31 eine 2er Potenz nicht so einfach über "a = a Shl 1" gebildet werden kann.

Es wird lediglich nach der größten Zweierpotenz gesucht die noch kleiner ist als der Exponent (!) um diesen dann zu zerlegen.
Auch bei 2^33000000 ist der Exponent ja "nur" 33000000, was noch im Bereich eines 32-Bit Integers liegt.

Zitat:

Wenn man a^p nach meiner Methode (Primfaktorzerlegung) ausrechnen
will, und man erkennt, dass p eine Primzahl ist, so nimmt man einfach
die Pf.zerlgung von p-1 und multipliziert am ende nochmal mit a.

Das stimmt natürlich. Trotzdem kann dabei aber eine Zahl entstehen die z.B. nur durch 2 teilbar ist, also nur 2 Primfaktoren hat.

Vielleicht kannst du die Funktionen zum String-Rechnen hier mal posten, ich würde mein programm gerne mal mit großen Zahlen ausprobieren. Smile

EDIT: Habs im Codearchiv gefunden!
Für 2^1000 braucht er 98ms
Für 2^10000 braucht er 17400ms
2^100000 hab ich mich noch nicht getraut ^^
Hab jetzt auch keine Zeit, ich werds später oder morgen weiter testen!

EDIT2:
Ich halte 2^33000000 für ein bischen arg krass erst recht wenn mans genau haben will. Vor allem BB ist dafür sicher zu langsam.
Der Windows-Rechner macht übrigens noch bis etwa 2^142000 mit danach sind ihm die Zahlen zu groß. Und allein 2^140000 hätte schon 42747 Stellen!

	Ctuchik	Do, Dez 29, 2005 22:44 Antworten mit Zitat
So, hab mich nochmal drangesetzt und Funktionen zum Rechnen mit großen Zahlen mit Hilfe von Banks geschrieben. Die sind wesentlich schneller als Strings!! Ich kann 2^10000 jetzt in 156ms berechnen und 2^100000 hat er nach 16 Sekunden raus. EDIT: Habe gerade festgestellt dass ich Debug noch an hatte. Ohne Debug berechnet er 2^100000 sogar in nur 3 Sekunden. Hier ist der Code: Code: [AUSKLAPPEN] [EINKLAPPEN] Graphics 1024,300,0,2 t=Millisecs() test$ = MyExpBank$("2",10000) Print "Zeit: " + (millisecs()-t) Print Len(test$) Print test$ WaitKey() End Function MyExpBank$(basis$,e%) base% = GetNumber(basis$) erg% = MyExpBankSub(base%,e%) dez$ = MakeNumber(erg%) Return dez$ End Function Function MyExpBankSub%(basis%,e%) count = -1 a = 1 While (a < e) a = a Shl 1 count = count + 1 Wend b = e - (a Shr 1) y% = CopyNumber(basis%) For a=1 To count y% = FastMult(y%,y%,True) Next If (b = 1) Then z% = CopyNumber(basis%) Else z% = MyExpBankSub(basis%,b) End If erg% = FastMult(y%,z%,True) Return erg% End Function Function GetNumber(snum$) While (Len(snum$) Mod 4 <> 0) : snum$ = "0" + snum$ : Wend bank = CreateBank(Len(snum$)/2) b = 0 For i=Len(snum$) To 1 Step -4 zahl = Int(Mid$(snum$,i-3,4)) PokeShort bank,b,zahl b = b + 2 Next Return bank End Function Function MakeNumber$(bnum%) ret$ = "" For i=0 To BankSize(bnum%)-1 Step 2 number% = PeekShort(bnum%,i) n$ = Str(number%) If (i < BankSize(bnum%)-3) Then While (Len(n$) < 4) : n$ = "0" + n$ : Wend End If ret$ = n$ + ret$ If number > 9999 Then RuntimeError("Critical Error!") Next Return ret$ End Function Function CopyNumber(num%) bank = CreateBank(BankSize(num)) CopyBank(num,0,bank,0,BankSize(num)) Return bank End Function Function FastMult(numa,numb,deleteold=False) bank = CreateBank(BankSize(numa)+BankSize(numb)) over_mult=0 For i=0 To BankSize(numa)-1 Step 2 a=PeekShort(numa,i) For j=0 To BankSize(numb)-1 Step 2 b=PeekShort(numb,j) mult=a*b+over_mult over_mult = (mult - (mult Mod 10000)) / 10000 t=PeekShort(bank,i+j) nt=(mult Mod 10000)+t If nt > 9999 Then over_mult = over_mult + 1 : nt = nt Mod 10000 PokeShort bank,i+j,nt Next If over_mult Then If (i+j) = BankSize(bank) Then ResizeBank(bank,i+j+2) t = PeekShort(bank,i+j) PokeShort(bank,i+j,t+over_mult) over_mult=0 End If Next i=BankSize(bank) While (PeekShort(bank,i-2) = 0) : i = i - 2 : Wend ResizeBank(bank,i) If deleteold Then FreeBank(numa) : FreeBank(numb) Return bank End Function
Zu den Nebenwirkungen gehören trockener Mund, Übelkeit, Erbrechen, Harnstau, schmerzhafter rektaler Juckreiz, Halluzinationen, Demenz, Psychose, Koma, Tod und Mundgeruch! Magie eignet sich nicht für alle! Fraget euren Arzt oder Apotheker!

Ctuchik

Do, Dez 29, 2005 22:44
Antworten mit Zitat

So, hab mich nochmal drangesetzt und Funktionen zum Rechnen mit großen Zahlen mit Hilfe von Banks geschrieben.
Die sind wesentlich schneller als Strings!!
Ich kann 2^10000 jetzt in 156ms berechnen und 2^100000 hat er nach 16 Sekunden raus.
EDIT: Habe gerade festgestellt dass ich Debug noch an hatte. Ohne Debug berechnet er 2^100000 sogar in nur 3 Sekunden.

Hier ist der Code:
Code: [AUSKLAPPEN]

Graphics 1024,300,0,2
t=Millisecs()
test$ = MyExpBank$("2",10000)
Print "Zeit: " + (millisecs()-t)
Print Len(test$)
Print test$
WaitKey()
End

Function MyExpBank$(basis$,e%)
base% = GetNumber(basis$)
erg% = MyExpBankSub(base%,e%)
dez$ = MakeNumber(erg%)
Return dez$
End Function

Function MyExpBankSub%(basis%,e%)
count = -1
a = 1
While (a < e)
a = a Shl 1
count = count + 1
Wend
b = e - (a Shr 1)
y% = CopyNumber(basis%)
For a=1 To count
y% = FastMult(y%,y%,True)
Next
If (b = 1) Then
z% = CopyNumber(basis%)
Else
z% = MyExpBankSub(basis%,b)
End If
erg% = FastMult(y%,z%,True)
Return erg%
End Function

Function GetNumber(snum$)
While (Len(snum$) Mod 4 <> 0) : snum$ = "0" + snum$ : Wend
bank = CreateBank(Len(snum$)/2)
b = 0
For i=Len(snum$) To 1 Step -4
zahl = Int(Mid$(snum$,i-3,4))
PokeShort bank,b,zahl
b = b + 2
Next
Return bank
End Function

Function MakeNumber$(bnum%)
ret$ = ""
For i=0 To BankSize(bnum%)-1 Step 2
number% = PeekShort(bnum%,i)
n$ = Str(number%)
If (i < BankSize(bnum%)-3) Then
While (Len(n$) < 4) : n$ = "0" + n$ : Wend
End If
ret$ = n$ + ret$
If number > 9999 Then RuntimeError("Critical Error!")
Next
Return ret$
End Function

Function CopyNumber(num%)
bank = CreateBank(BankSize(num))
CopyBank(num,0,bank,0,BankSize(num))
Return bank
End Function

Function FastMult(numa,numb,deleteold=False)
bank = CreateBank(BankSize(numa)+BankSize(numb))
over_mult=0
For i=0 To BankSize(numa)-1 Step 2
a=PeekShort(numa,i)
For j=0 To BankSize(numb)-1 Step 2
b=PeekShort(numb,j)
mult=a*b+over_mult
over_mult = (mult - (mult Mod 10000)) / 10000
t=PeekShort(bank,i+j)
nt=(mult Mod 10000)+t
If nt > 9999 Then over_mult = over_mult + 1 : nt = nt Mod 10000
PokeShort bank,i+j,nt
Next
If over_mult Then
If (i+j) = BankSize(bank) Then ResizeBank(bank,i+j+2)
t = PeekShort(bank,i+j)
PokeShort(bank,i+j,t+over_mult)
over_mult=0
End If
Next
i=BankSize(bank)
While (PeekShort(bank,i-2) = 0) : i = i - 2 : Wend
ResizeBank(bank,i)
If deleteold Then FreeBank(numa) : FreeBank(numb)
Return bank
End Function

	Triton	Fr, Dez 30, 2005 18:54 Antworten mit Zitat
Wow, nicht schlecht. Ich schaus mir mal, wenn ich mehr Zeit habe genauer an und werd auch mal diverse Tests machen. Trotzdem schon ne beeindruckende Geschwindigkeit. Meinen Respekt. mal ein theoretischer Test für 2^33219280: Also wenn ich deine Methode richtig verstanden habe, rechnest du folgendes: 2^33219280 = 2^(2^24) * 2^(2^23) * 2^(2^22) * 2^(2^21) * 2^(2^20) * 2^(2^19) * 2^(2^17) * 2^(2^15) * 2^(2^14) * 2^(2^13) * 2^(2^9) * 2^(2^7) * 2^(2^6) * 2^(2^4) Das sind schon ganz schön viele Zerlegungen (auch wenn das nichts negatives heißen muss hinsichtlich der Geschwindigkeit). wenn bei a^b b eine 2er-Potenz minus eins ist (z.B 2^511), dann gibts ja noch mehr: 2^511 = 2^(2^8 ) * 2^(2^7) * 2^(2^6) * 2^(2^5) * 2^(2^4) * 2^(2^3) * 2^(2^2) * 2^(2^1) * 2^(2^0) 2^3300 hat bei mir 3 ms gedauert, 2^33000 etwa 300 ms und 2^330000 33 s. Demnach musste nach deiner Methode 2^33mio etwa 3 mio ms dauern - etwa 50 min Mal testen
Coding: silizium-net.de \| Portfolio: Triton.ch.vu

Triton

Fr, Dez 30, 2005 18:54
Antworten mit Zitat

Wow, nicht schlecht. Ich schaus mir mal, wenn ich mehr Zeit habe genauer an und werd auch mal diverse Tests machen.

Trotzdem schon ne beeindruckende Geschwindigkeit. Meinen Respekt. Smile

mal ein theoretischer Test für 2^33219280:
Also wenn ich deine Methode richtig verstanden habe, rechnest du folgendes:

2^33219280 =
2^(2^24)
* 2^(2^23)
* 2^(2^22)
* 2^(2^21)
* 2^(2^20)
* 2^(2^19)
* 2^(2^17)
* 2^(2^15)
* 2^(2^14)
* 2^(2^13)
* 2^(2^9)
* 2^(2^7)
* 2^(2^6)
* 2^(2^4)

Das sind schon ganz schön viele Zerlegungen (auch wenn das nichts negatives heißen muss hinsichtlich der Geschwindigkeit). wenn bei a^b
b eine 2er-Potenz minus eins ist (z.B 2^511), dann gibts ja noch mehr:

2^511 =
2^(2^8 )
* 2^(2^7)
* 2^(2^6)
* 2^(2^5)
* 2^(2^4)
* 2^(2^3)
* 2^(2^2)
* 2^(2^1)
* 2^(2^0)

2^3300 hat bei mir 3 ms gedauert, 2^33000 etwa 300 ms und 2^330000 33 s. Demnach musste nach deiner Methode 2^33mio etwa 3 mio ms dauern - etwa 50 min Confused

Mal testen Smile

Coding: silizium-net.de | Portfolio: Triton.ch.vu

Gehe zu Seite 1, 2 Weiter

Übersicht

BlitzBasic

Allgemein

Nach Oben

BlitzBasic Portal

Potenzen

Betreff: Potenzen