ultra große Zahlen berechnen

Offizieller deutscher Support für das MASM32 SDK. Download FAQ

Moderatoren: crack, Krüsty, Marwin

ultra große Zahlen berechnen

Beitragvon ---Loki--- » Sonntag 4. Dezember 2005, 19:24

Hallo,

da man meine Registrierung bis heute ja noch nicht freigeschaltet hat muss ich halt hier posten.... :evil:

So ich möchte die Quadratwurzel einer Zahl mit unendlicher Größe ziehen. Das heißt die kann eventuell ein paar Millionen stellen haben. :shock:
Da so eine große Zahl ja nicht aufeinmal im CoPro verarbeitet werden kann muss ich die Berechnung stückchenhaft durchführen. Und genau da ist mein Problem... ich hab keine Ahnung wie :?: :?: :?:


Wäre nett wenn mir einer sagen könnte wie mans macht.

PS: Ich bin mir darüber bewusst das die Berechnung lange dauern kann.
Benutzeravatar
---Loki---
Newbie
 
Beiträge: 9
Registriert: Montag 8. August 2005, 14:44

Beitragvon crack » Sonntag 4. Dezember 2005, 19:30

Ich sage nur ... Newton Raphson Verfahren!
Hier ist ne kleine Anleitung zu finden:
http://www.hvviehof.de/dogs/newton%20raphson%20verfahren.htm

Ich hoffe geholfen zu haben ... (isch lieeebe dat Plusquamperfekt :wink: )

and never forget: "the crack's of the bisquit is the apostrophe..." (Frank Zappa)
mit freundlichen grüssen,
with best regards,

crack
Benutzeravatar
crack
Administrator
 
Beiträge: 280
Registriert: Dienstag 21. Dezember 2004, 15:02
Wohnort: 53783 Eitorf

Re: ultra große Zahlen berechnen

Beitragvon Krüsty » Sonntag 4. Dezember 2005, 21:03

---Loki--- hat geschrieben:Hallo,

da man meine Registrierung bis heute ja noch nicht freigeschaltet hat muss ich halt hier posten.... :evil:

Hallo ---Loki---!

Wie bei fast allen Foren ist es auch bei uns der Fall, dass man seine Email verfizieren muss. Die wird durch eine Email realisiert, in der ein Link zu Freischaltung steht. Wenn du diesen Link nicht besuchst, so wirst du auch nicht freigeschaltet. Die Email ging eindeutig raus und kam auch nicht zurück.
Es kann sein, dass web.de die Mail mal wieder als Spam aussortiert hat. Das kommt in letzter Zeit leider öfter vor.
Wie dem auch sei, ich hab dich jetzt manuell freigeschaltet.
Kontaktaufnahme ist im Übrigen über http://www.codingcrew.de/impressum.php#kontakt möglich.
Grüße,
Krüsty
a member of CodingCrew.de
Air conditioned computer. Please keep WINDOWS closed.
Bild
Benutzeravatar
Krüsty
Administrator
 
Beiträge: 96
Registriert: Donnerstag 8. Mai 2003, 21:25
Wohnort: Dresden, Deutschland

Beitragvon ---Loki--- » Sonntag 4. Dezember 2005, 23:20

Danke Crack,

aber damit hab ich nur ein Annäherungsverfahren... aber das Problem mit den großen Zahlen besteht nachwievor. (Oder hab ich jetzt was nicht verstanden?)

Im Prinzip könnte ich das Problem lösen wenn ich wüßte wie der Prozessor intern eine Wurzel berechnet (Binärkombination). Dann könnte ich eine Funktion programmieren die genau das selbe macht. Und da ja alles auf Binärcode basiert denke ich das man dann auch die Wurzel in stückchen berechnen kann.

Und um größenwahnsinnig zu werden.... Ich rede von Zahlen die sich nicht in meinen 256MB Arbeitsspeicher darstellen lassen :lol:
Benutzeravatar
---Loki---
Newbie
 
Beiträge: 9
Registriert: Montag 8. August 2005, 14:44

Beitragvon crack » Montag 5. Dezember 2005, 15:20

Ich gebe zu, ein etwas komplexeres Problem...

aber damit hab ich nur ein Annäherungsverfahren... aber das Problem mit den großen Zahlen besteht nachwievor. (Oder hab ich jetzt was nicht verstanden?)

Im Prinzip ist der Wert der Eingangsgrösse für die Durchführung des Newton-Raphson-Verfahrens unerheblich, was jedoch in Betracht zu ziehen ist, ist die Fragen wie schnell das Newton Raphson Verfahren 'konvergiert' also sich dem Endwert annähert...
Im Prinzip könnte ich das Problem lösen wenn ich wüßte wie der Prozessor intern eine Wurzel berechnet (Binärkombination). Dann könnte ich eine Funktion programmieren die genau das selbe macht. Und da ja alles auf Binärcode basiert denke ich das man dann auch die Wurzel in stückchen berechnen kann.

Meines Wissens nach benutzt der CoPro da NR-Verfahren... Hm, mit der Annahme der CoPro berechne die Zahlen als Binärwerte liegst Du nich ganz richtig, bei dem vom CoPro verwendeten Datenformat handelt es sich um eine 'normierte Fliesskommazahl nach IEEE' wobei das erste Bit das Vorzeichen repräsentiert, die folgenden 8 Bit den Exponenten (Biased Exponent) und die folgenden 23 Bit die Mantisse bilden.
Und um größenwahnsinnig zu werden.... Ich rede von Zahlen die sich nicht in meinen 256MB Arbeitsspeicher darstellen lassen

Uff! Das'n ganz schöner Hammer Ey Mann ;) Hm, also an einem Stück wirst Du diese Zahlen auf einem normalen PC wohl nicht verarbeiten können, und ob man die Zahl in 'Einzelteile' zerlegen kann um die Wurzel zu ziehen, da bin ich auch ehrlich gesagt überfragt, aber wenn's möglich ist, dann würde ich meinen das es genau die Problemstellung ist die ein Cluster von Linux Rechnern wohl am effizientesten abarbeitet. Solltest Du aber eine Gangbare Methode finden diese exorbitant grosse Zahl auf einer konventionellen Windows Maschine zu verarbeiten, dann würde es mich sehr freuen wenn Du mir sagst wie ;)
mit freundlichen grüssen,
with best regards,

crack
Benutzeravatar
crack
Administrator
 
Beiträge: 280
Registriert: Dienstag 21. Dezember 2004, 15:02
Wohnort: 53783 Eitorf

Beitragvon crack » Montag 5. Dezember 2005, 15:59

So, hab mich mal was umgehört: (8ung ist zweite Hand Info):
Wurzel (A²*B) = A * Wurzel B und wenn man B = C²*D setzt geht das Spiel genau so weiter ...


Noch Beispiel:
Wurzel 81 = Wurzel (3²*9) = 3 * Wurzel 9 = 3 * Wurzel 3² = 3 * 3 = 9


Hoffe da kannste was mit anfangen ...
mit freundlichen grüssen,
with best regards,

crack
Benutzeravatar
crack
Administrator
 
Beiträge: 280
Registriert: Dienstag 21. Dezember 2004, 15:02
Wohnort: 53783 Eitorf

Beitragvon ---Loki--- » Dienstag 6. Dezember 2005, 01:28

Übrigens Crack,

noch effizienter als die Cluster arbeitet meines wissens nach das Internet.
Man braucht natürlich ein gewisses Umfeld an Nutzern welche sich das Tool runterladen welches dann vom Server einen Teilbereich der Zahl zugewiesen bekommt und dann wenn der User nicht arbeitet die Werte abarbeitet.

Mit diesem Verfahren arbeiten z.B. Forscher an der Genetischen Lösung gegen Krebs. | Ein anderes Beispiel ist die Findung von Primzahlen.... dort setzt man auch auf ein solches Netz.

Lohnt natürlich nur bei ganz zeitaufwändigen Berechnungen.
Benutzeravatar
---Loki---
Newbie
 
Beiträge: 9
Registriert: Montag 8. August 2005, 14:44

Beitragvon Gast » Donnerstag 8. Dezember 2005, 02:01

Wie wäre es direkt optimierte Libs für große Zahlen zu benutzen ;) ? (afaik gibts sowas für mehrere Sprache, aber auf jedenfall für C) - ist in 99% der Fälle schneller, als das, was man so selber hinwurschtelt ;)
Du wirst also selber eine multiplikation/division oder was man da noch braucht, einfach "per Hand" nachbilden müssen - zumindest wäre es die erste Methode, die mir einfallen würde - oder Du schaust hier unter Big Numbers oder änlichen Suchwörtern:
http://win.asmcommunity.net/board/index ... on=search2

So ich möchte die Quadratwurzel einer Zahl mit unendlicher Größe ziehen.

Da Computer sich in endlichen Dimensionen bewegen, ist dieses Problem nicht lösbar ;)
Gast
 

Beitragvon crack » Freitag 9. Dezember 2005, 13:15

Da Computer sich in endlichen Dimensionen bewegen, ist dieses Problem nicht lösbar


Einschränkung: nicht bei endlicher Rechenzeit und endlichen Speicherresourcen...

Was aber möglich ist ist die Grenzwertberechnung:

gesucht x = wurzel von unendlich
x = wurzel von n mit n von 0 bis unendlich ---> bei der 'Grenzwertberechnung' prüfe ich ob die Funktion zu einem bestimmten Wert konvergiert, sonst müsste ich ja tatsächlich bis ins unendliche rechnen ;)
lange rede kurzer Sinn: wenn n sich unendlich annähert nähert sich auch die wurzel x von n unendlich da die wurzel ja eine nichtlinear steigende funktion von n darstellt ;)

hier noch bischen Python gewurzel zum Zeitvertreib ( und fyr die Skeptiker ;) ):



from math import *
from string import *

n = 0
fake = 1
while fake ==1:
n = n + 1
x = sqrt(n)
print "zahl:" + str(n) + " " + "Wurzel:" + str(x);



Vielleicht wär's in Assembler schneller, spiel aber keine Rolle das ne Schleife ohne abbruchbedingung ist :lol:
mit freundlichen grüssen,
with best regards,

crack
Benutzeravatar
crack
Administrator
 
Beiträge: 280
Registriert: Dienstag 21. Dezember 2004, 15:02
Wohnort: 53783 Eitorf

Beitragvon Axel » Samstag 10. Dezember 2005, 20:47

Wie bereits jemand sagte: besser man schaut erst mal, was es gibt (auch
jenseits von Assembler). Ein Standard ist GMP (GNU) oder MPFR (Zimmermann)
oder Zeug von Bailey (C oder Fortran?). Vom letzteren gibt es viel sehr
Erstaunliches, ev ein Einstieg für eine ernsthafte Suche (parallelisier-
bar?). Von Zimmermann, INRIA, gibt es einen Artikel "Efficient Algorithms
on Numbers ..." (Google wird ihn finden), der neben Komplexitätsbetrachtungen
(-> Rechenzeit!) auch Stichworte für weitere Recherchen liefert. Du hast
zwar über Deine große Zahl nix gesagt, aber so Du sie genau kennst (also
nicht etwa "n Stellen von function(Pi)"), dann kannst Du sie als ganz
annehmen. "Wozu das alles?" will ich i d Adventszeit nicht fragen ...
Axel
 

Beitragvon nappeldidappel » Donnerstag 16. November 2006, 05:37

wäre es da nicht möglich mit BCD (Binary Coded Decimal) zu rechnen ?
Meines Wissens nach ist die Zahl dann 80 bit lang, und mit 2^80 ist doch schon ein sehr hoher Wertebereich (so um die 1208 Trilliarden) möglich ^^ CUL8'er.
nappeldidappel
 

Beitragvon CDW » Sonntag 26. November 2006, 23:50

und mit 2^80 ist doch schon ein sehr hoher Wertebereich

Jep, Wertebereich ist dann riesieg, allerdings hat man trotzdem insgesammt 2^80 Werte und dazwischen Lücken. Also zum Teil sehr sehr ungenau.
Wobe: für masm sollte es auch BigNum Libs geben. Zumindest hatte ich die mal hier gesichtet: http://wasm.ru/srclist.php?list=9 (BigShit)
Wobei es auch eine bessere geben sollte (win32asm Forum oder MASM Forum (die englischen ;) ) durchsuchen bzw. siehe Link im oberen Post)
CDW
Alter Hase
 
Beiträge: 62
Registriert: Donnerstag 2. Oktober 2003, 17:17


Zurück zu MASM32-Package

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder

cron