Zahlgenauigkeit mit c++?

Hi,
kann man irgendwie
1. mit akzeptabler geschwindigkeit mit zahlen wie dieser rechnen?
38875493060628784669852485843008042995400437811290540575288354271143675146093967
58916373506548846064623968545229736839089892921584976866482139753315058255955085
40192203744825717
2. erreichen, dass zahl - sqrt(zahl)^2 nicht um die -5.6e+160 ist?
sorry, wenn das jetzt totale newbie-fragen sind, sie passen zu mir, ich bin nämlich einer.
wenn ich mal programmiere, dann meistens ruby oder php, ein bisschen pascal ist auch noch drin.
mal ein abschnitt ruby:

puts zahl - Math.sqrt(zahl)**2
puts (zahl - Math.sqrt(zahl)**2).to_i

gibt

-5.623642243179e+160
-56236422431789954785131731346074773235871213978773957913759444657647969758393598378988008576298635714374011382919011189040103325693678746112606439760814548189184

danke schoma,
Lorenz

Walli

Google nach GMP. Das sind Klassen für beliebig genaue (Fließkomma)zahlen.

Jester

lolo1992 schrieb:

1. mit akzeptabler geschwindigkeit mit zahlen wie dieser rechnen?
38875493060628784669852485843008042995400437811290540575288354271143675146093967
58916373506548846064623968545229736839089892921584976866482139753315058255955085
40192203744825717

Naja, geht so. Es gibt Bibliotheken (z.B. GMP), die solche Datentypen anbieten. So richtig schnell ist das aber nicht.

2. erreichen, dass zahl - sqrt(zahl)^2 nicht um die -5.6e+160 ist?

Ja, das ist ein gewisses Problem. Du weißt vielleicht aus der Schule, daß zum Beispiel sqrt(2) eine Zahl ist, die nach dem Komma nicht abbricht und auch niemals periodisch wird. Das heißt, um die Dezimalentwicklung dieser Zahl zu speichern bräuchte man sozusagen unendlich viel Speicher. Leider steht der auf den meisten Systemen nicht zur Verfügung, daher schneidet man irgendwann einfach ab. Dadurch entstehen diese Rechenfehler.

Die einfachste Möglichkeit das zu behandeln ist einen kleinen Schwellwert festzulegen, ab dem man eine Zahl als 0 betrachtet. Btw. biste sicher, daß Deine angegebene Zahl da stimmt? imho müßte es eher -5.6e-160 heißen, was für eine sehr sehr kleine Zahl, nämlich -5.6/(10^160) also -5.6 an der 160. Stelle nach dem Komma, steht.

Wenn Dich lediglich die Ausgabe stört, dann runde die Zahlen doch vor der Ausgabe auf 5 Nachkommastellen, dann hat sich das erledigt.

MfG Jester

hi,
die klasse probier ich morgen aus.

ja, danke, die wurzeln kenn ich.

nein, ich meinte definitiv nicht -5.6e-160, das wär ja kein problem.
genau das ist ja das problem, das das so irrsinnig ungenau ist.

ich weiß, dass das nicht absolut genau geht, wenn die differenz < 200 wäre, würde das absolut langen.

eine schwierigkeit wäre noch, dass das ganze innerhalb von 0.5 sek über die bühne gehen sollte.

es geht darum, dass ich eben diese zahl habe, und die in 2 primfaktoren zerlegen muss, von denen ich nur weiß, dass sie nahe beieinander, d.h. nahe bei der wurzel liegen. dann nehm ich floor(wurzel / 2) * 2 - 1, d.h. mach das ganze ungerade, und zähl in 2erschritten hoch.

nochmal danke & ciao

Lorenz

p.s. nein, die ausgabe ist sogar eine integer

Du weißt hoffentlich, daß Primzahlzerlegung nicht gerade zu den "schnell lösbaren" Problemen gehört, oder? Sprich: Dafür mußt du auf jeden Fall eine gewisse Rechenzeit einplanen, gerade bei so großen Zahlen wie du verwendest.

Lorenz schrieb:

es geht darum, dass ich eben diese zahl habe, und die in 2 primfaktoren zerlegen muss, von denen ich nur weiß, dass sie nahe beieinander, d.h. nahe bei der wurzel liegen. dann nehm ich floor(wurzel / 2) * 2 - 1, d.h. mach das ganze ungerade, und zähl in 2erschritten hoch.

ja, danke, das weiß ich... der knackpunkt ist, dass diese beiden faktoren nahe beieinander liegen.

Lorenz

Wie definierst du "nahe beieinander"? Bei solchen Zahlen, wie in deinem Eröffnungspost genannt, landest du auf jeden Fall in einer Größenordnung, in der die Komplexitätstheorie eine Rolle spielt (und da dürfte nichtmal eine einfache Multiplikation oder Division wirklich schnell zu erledigen sein).

Jester

CStoll (off) schrieb:

Wlandest du auf jeden Fall in einer Größenordnung, in der die Komplexitätstheorie eine Rolle spielt

Das tut sie doch eigentlich immer, oder?

Naja, eine einzelne Division durchzuführen ist zwar aufwendig, aber nicht sooo aufwendig. Und wenn die Zahlen nah beieinander liegen, dann heißt das, wenn er von der Wurzel ausgehend sucht, dann findet er bald was. Er braucht nicht den langen weg gehen, bis zu den kleinen bzw. großen Zahlen. Mit ein bißchen Glück sind das vielleicht nur um die 100 Tests oder so.

CStoll

Jester schrieb:

Das tut sie doch eigentlich immer, oder?

Nur macht es bei 8-Bit-Zahlen noch nicht wirklich einen Unterschied, ob man mit O(n²) oder mit O(2ⁿ) Laufzeiten zu kämpfen hat.

Hi,
ich hab das Problem gelöst.
zwar nicht mit c++, sondern mit aribas, aber es geht...
für die, dies interessiert:

function getPrimFaktor(zahl: integer): integer;
        var p: integer;
        begin
                set_floatprec(1024);
                p := floor(sqrt(zahl) / 2) * 2 - 1;
                while zahl mod p /= 0  do
                        p := p + 2;
                end;
                return p;
        end.

load("nummer.ari").
transcript("faktor").
getPrimFaktor(nummer).
transcript(0).
exit.

das ding kriegt die zahl in < 0.1 sekunden raus
Danke für eure Hilfe,
Lorenz