Das deutsche QBasic- und FreeBASIC-Forum

[Name.and(2)=Andreas]

Hallo,

ich suche einen Algorithmus um z.b. die 254. Nachkommastelle der wurzel von 2 ohne großen Aufwand zu berechnen.
In dem Programm soll es dann folgendermaßen realisiert werden:


1) Ich gehe zu einer bestimmten Nachkommastelle einer bestimmten Wurzel.
2) Ich führe meine Rechenoperationen damit aus.
3) Ich nehme die Nachkommastelle nach der jetzigen Nachkommastelle und gehe zu 2) bis eine Bedingung erfüllt ist.


Kennt jemand ein passenden Algorithmus oder einen Tipp um das ohne viel Rechenaufwand zu realisieren?

Andreas

[Jojo]

in FB bekommst du maximal 15 Nachkommastellen.
die x.te nachkommastelle kannst du da so extrahieren:

[Name.and(2)=Andreas]

Ja, so geht das, bloß sind 15 ja eben zu wenig, deshalb stelle ich diese Frage...ich bräuchte mehr als 15.

Kann man Pi denn nicht so berechnen, das wäre schon mal die halbe Miete.

Ich hab das vor bis theoretisch mehrere Millionen Nachkommastellen, deshalb hab ich auch nach nem schnellen Algorithmus gefragt.

Evtl. kann man das aber anders machen:

Ich möchte einer beliebigen Zahl x eine unendliche einzigartige Folge y (geplant war da dann die wurzel einer zahl)
zuordnen, aber aus y(n) sollte y(n-1) nicht berechenbar sein.

Evtl. kann jemand mir da jetzt mehr helfen.

Andreas
_________________
Fluchen ist die einzige Sprache, die alle Programmierer wirklich beherrschen!

[28398]

Also wenn du das in endlicher Zeit berechnet haben willst... Shader!
Texturen als Datencontainer benutzten (bei 32 BPP = 1 Integer pro Pixel, oder 2 Pixel = ULongInt/Double and so on).
Sprich ganzen Viewport mit zwei (oder mehr je nach Algorithmus) GL_QUADS belegen, texturieren, und dann im Fragmentshader per Multitexturing die Texturen verknüpfen (Addieren, Multiplzieren, Dividieren, Subtrahieren und alles was es so gibt, auch komplexere Sachen, sinus, cosinus usw.)

Dann im Hauptprogramm per glReadPixels den Bidlschirm auslesen und ins gewünschte Datenformat transformieren
volá!

Warum Shader?
Weil Shader die schnellsten Recheneinheiten am ganzen PC sind (sofern die Grafikkarte sie unterstützt).
Außerdem ist bsp. GLSL sehr leicht zu erlernen.

Beim Algorithmus kann ich dir leider nicht helfen, ich kann dir lediglich Wege und Technologien aufzeigen, wie du deine Berechnungen sehr schnell durchführen kannst...

[Name.and(2)=Andreas]

Also, ich brauche lediglich eine Funktion, der aus einem gegebenen y(n) ein y(n+1) macht, aber man aus y(n+1) nicht auf y(n) zurückschließen kann.

quasi eine Einweg-Funktion, was ich also brauche ist evtl. ein Link oder eine Beispiel-Funktion...oder bloß den Fachbegriff, wie man solche Funktionen nennt, dann such ich mir den Rest schon zusammen

Andreas
_________________
Fluchen ist die einzige Sprache, die alle Programmierer wirklich beherrschen!

[28398]

Hash / Hashing

MD5 vll.?
Schau mal auf FBP.de (http://freebasic-portal.de/) da war irgendwo ein MD5 Code...

[Name.and(2)=Andreas]

Iwie ist ein Hash was völlig anderes, dort wird quasi ein Fingerabdruck eines Textes erstellt. ich hatte gedacht, dass man die kernfunktion benutzen kann, allerdings geht das wohl doch nicht.

Nein, was ich bräuchte ist sowas wie die RSA Schlüsselerstell Funktion.

Die ist nicht umkehrbar, so ähnliche Funktionen muss es ja auch für nicht primzahlen, also für beliebige zahlen geben oder?
_________________
Fluchen ist die einzige Sprache, die alle Programmierer wirklich beherrschen!

[28398]

Eine Hasingfunktion ist eine Einwegfunktion!
Und du kannst den MD5 Hash auch als Zahl haben, und zwar als zwei ULongInts...

Du kannst MD5 auch so vereinfachen, dass du nur ein Segment hashest (=512 Bit).

[Jojo]

jaja, in dem alter denkt man noch, man kann alles... xD willst du wirklich RSA toppen?
_________________
» Die Mathematik wurde geschaffen, um Probleme zu lösen, die es nicht gäbe, wenn die Mathematik nicht erschaffen worden wäre.

[Name.and(2)=Andreas]

Also, eine Hash-Funktion ist zu umständlich, denn ich würde dann ja nich einmal was hashen sondern mehrere millionen mal und dafür ist eine hashfunktion zu langsam.


Schneller ist doch einfach eine schöne kurze mathematische Funktion.

Theoretisch könnte ich eine Hashfunktion mit viel mühe einbauen, hätte dann aber ein langsames Programm und wenig Sicherheit, da ,man einen Hash man später wieder mit seiten wie www.hashkiller.com oder www.milw0rm.com wieder knacken kann.

Andreas


EDIT: @Jojo: hä? Ich hab nich vor RSA zu toppen ...bloß eine nicht umkehrbare rechenoperation mit einer zahl bzw. einer komplexen zahl machen und das durch iteration immer weiter fortsetzen und so eine reihe von mehr oder minder zufälligen Zahlen zu bekommen.



EDIT2: Also ich will nicht abstreiten, dass ich das was ich vorhab mit einem hash erledigen kann, jedoch muss es doch was einfacheres geben, und genau das suche ich.
_________________
Fluchen ist die einzige Sprache, die alle Programmierer wirklich beherrschen!

[Mao]

Milworm ist einfach nur 'ne Exploit-Datenbank, wie willst du damit 'nen Hash zurückrechnen? oO
Ich halt den Link auch nicht für besonders angebracht.
_________________
Eine handvoll Glück reicht nie für zwei.
--

[Name.and(2)=Andreas]

oben bei milworm gibs nen link zu nem hash cracker^^

nunja, ich verwende jetzt die simple Trapdoor-Einwegfunktion x^e mod n ;
die geht
Ich muss das nur noch vereinfachen, wegen der komplexen zahl x.
Also, damit ist das Thema gelöst, ich hab gefunden, was ich wollte...


Sry, ja der Link ist eig. nicht angebracht...*sry*

Andreas
_________________
Fluchen ist die einzige Sprache, die alle Programmierer wirklich beherrschen!

[MisterD]

pseudozufallsgeneratoren gibts im überfluss, brauch man nur mal googlen.. Oo
_________________
"It is practically impossible to teach good programming to students that have had a prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration."
Edsger W. Dijkstra

[dreael]

Zum Titelthema: Da musst Du im Prinzip eine eigene Hochgenau-Arithmetik-"Klasse" zusammenstellen, d.h. mit TYPE einen Zahlentyp definieren - als interne Darstellung wäre ein Dezimalstring oder binäre Verkettung von unsigned Integer (meines Wissens unterstützt FB Unsigned im Gegensatz zu QB sogar) + zugehörige SUB/FUNCTIONs, wobei Du es bei FreeBasic auch wiederum so komfortabel hast, dafür, "+", "-", "*" usw. entsprechend überladen zu können. => Dann solltest Du schlussendlich auch in der Lage sein, Deine Quadratwurzel mit entsprechend beliebig hoher Genauigkeit berechnen zu können.
_________________
Teste die PC-Sicherheit mit www.sec-check.net

[Name.and(2)=Andreas]

Ja genau, ich kannte bisher bloß die Intervall-Schachtelung und das Heron-verfahren.

Ich hab mich jetzt aber nochmal schlau gemacht und noch ein Verfahren gefunden, was sich leicht mit dem Pc realisieren lässt: die Potenzreihe berechnen.

Da kann man bei erreichen einer bestimmten genauigkeit aufhören und später damit mit einer einfachen multiplikation wieder weiter machen.

Bloß ich versteh nicht ganz wie du das mit dem UDT genau meinst.
Kannst du ein Code-Beispiel posten? (Das Prinzip hab ich verstanden bloß hab ich keine Ahnung wie man das realisiert)


Andreas

EDIT: ja pseudozufallsgeneratoren gibs auch...viele rechnen ja sogar selber mit Wurzeln.
Also ich kenn nix zufälligeres als eine Wurzel.
Aber du hast recht, Pseudozufallsgeneratoren wären eine Möglichkeit. Ich muss mal abwägen, welches die bessere ist.
_________________
Fluchen ist die einzige Sprache, die alle Programmierer wirklich beherrschen!

[psygate]

Also, ich hab des Thema mal überflogen, und das was du suchst, ist eine sog. Trapdoor Funktion.

Mit Wurzeln und normalen Funktionen wirst du nicht weit kommen, weil die entweder eineindeutig sind oder nicht und wenn nciht, dann kannst du sie zur sicheren identifikation eh nicht benutzen. Und wenn du Wurzeln als "Hash" oder als Signatur deiner Daten verwenden willst, denk mal nach, die Wurzel ist eine eineindeutige Funktion und auch noch ganz einfach umzukehren, also versteh ich nciht ganz, warum du kein MD5 oder SHA1 nimmst?

Und AES kannst du dir auch abschminken, das ist nämlich ein Verschlüsselungsalgorithmus und hat nichts mit einer Trapdoorfunktion zutun. Hashing mit dem ist nicht gerade erste Wahl?

Schau mal SHA1.

Und wenn du sicher verschlüsseln willst, was nicht Hashen und keine Trapdoor ist, dann schau unter Elliptischen Kurven, Diskreter Logarithmus und Modular Formen, das sind die gängigsten und sichersten.
_________________
Danke an Volta für seine großartige MMX_fade function. *verneig*
Personal-DNA:
<script src="http://personaldna.com/h/?k=qtrCFboSuCOpFrX-OI-AADBA-f78d&t=Free-Wheeling+Leader">
</script>

[Triton]

In BlitzBasic habe ich das so gelöst, dass ich mir ein neues Zahlenformat geschaffen habe, welches aus Strings besteht. Die können unendlichg groß werden (bis der Speicher platzt), sind aber langsamer als normale Zahlen.

Dann muss man sich "nurnoch" die ganzen Rechenoperationen nachcoden (quasi wie man es in der schule mit den schriftlichen Rechnen gelernt hat). Das ist ziemlich aufwendig, funktioniert aber.

Nun ja, ich code glaube ich seit 3 Jahren oder so daran (was aber auch daran liegt, dass ich so wenig Zeit habe und lange zeit nichts dann mache )..
_________________
Coding: silizium-net.de | Portfolio: Triton.ch.vu