Tag
So, hier nun eine Vorstellung meiner Arbeit, die ich im Urlaub für meine Facharbeit geschrieben habe.
Es handelt sich um eine Klasse, mit der sich (in der Theorie) beliebig große Zahlen darstellen lassen.
Die Klasse basiert auf dem Prinzip des chinesischen Restsatzes. Laut dem hat ein System von Kongruenzen genau eine Lösung x im Zahlenraum Zm wenn gilt:
x = a1 (mod m1)
...
x = an (mod mn)
m = m1 * ... * mn
Vorraussetzung dafür ist, dass die sogenannten Module m1, ..., mn teilerfremd sind (ich benutze hierfür Primzahlen)
Die Zahl x befindet sich damit im Raum zwischen 0 und m-1
Darstellen kann man die Zahl nun durch ihre Reste a1, an
Mit diesen Resten kann man dann auch rechnen:
xa + xb = xc
=> a1 + b1 = c1 (mod m1)
Soweit komme ich mit beliebig großen Zahlen im Moment auf eine ganz annehmbare Geschwindigkeit....nämlich ca 50-60 Prozent der Geschwindigkeit bei Integer-Rechnungen.
Problem ist im Moment, dass ich die Zahlen nicht in ihrer Größe vergleichen kann. Aus diesem Problem folgt auch, dass ich die Zahlen nicht effizient ausgeben kann.
Das dürfte ersichtlich werden, wenn man sich die Ausgabemethode ansieht^^
Fertig bin ich natürlich noch nicht. Die Klasse wird dazu da sein die sehr großen Zahlen aufzunehmen, die bei Verschlüsselungsalgorithmen wie RSA anfallen.
Achja: Die Dateien hab ich mal signiert, um nachweisen zu können, dass sie von mir stammen, ich in meiner Facharbeit also nichts geklaut habe.
Zahlen über chinesischen Restsatz
- Dirty Oerti
- Beiträge: 2229
- Registriert: Di Jul 08, 2008 5:05 pm
- Wohnort: Thurndorf / Würzburg
Zahlen über chinesischen Restsatz
Du hast keine ausreichende Berechtigung, um die Dateianhänge dieses Beitrags anzusehen.
Bei Fragen einfach an daniel[ät]proggen[Punkt]org
Ich helfe gerne!
----------
Wenn du ein Licht am Ende des Tunnels siehst, freu dich nicht zu früh! Es könnte ein Zug sein, der auf dich zukommt!
----
It said: "Install Win95 or better ..." So I installed Linux.
Ich helfe gerne!
----------
Wenn du ein Licht am Ende des Tunnels siehst, freu dich nicht zu früh! Es könnte ein Zug sein, der auf dich zukommt!
----
It said: "Install Win95 or better ..." So I installed Linux.
- Dirty Oerti
- Beiträge: 2229
- Registriert: Di Jul 08, 2008 5:05 pm
- Wohnort: Thurndorf / Würzburg
Re: Zahlen über chinesischen Restsatz
Laut diesem PDF (Englisch) [1] hat sich anscheinend schon mal ein Student mit dem Thema intensiver auseinander gesetzt.
Schade nur, dass sich seine Arbeit nicht mehr wirklich finden lässt. (D.M. Potts heißt der Mensch).
Zu dem Zweck hab ich den Author obigen PDFs mal angeschrieben....
Was aber aus dem PDF herauszulesen ist:
Vergleichen und dividieren scheint ein echtes Problem darzustellen.
Ob ich das also lösen kann wenn es nicht einmal ein Mathematikprofessor für einfach hält ist fraglich...
[1] http://www.math.tamu.edu/~fulling/chinese.pdf
Schade nur, dass sich seine Arbeit nicht mehr wirklich finden lässt. (D.M. Potts heißt der Mensch).
Zu dem Zweck hab ich den Author obigen PDFs mal angeschrieben....
Was aber aus dem PDF herauszulesen ist:
Vergleichen und dividieren scheint ein echtes Problem darzustellen.
Ob ich das also lösen kann wenn es nicht einmal ein Mathematikprofessor für einfach hält ist fraglich...
[1] http://www.math.tamu.edu/~fulling/chinese.pdf
Bei Fragen einfach an daniel[ät]proggen[Punkt]org
Ich helfe gerne!
----------
Wenn du ein Licht am Ende des Tunnels siehst, freu dich nicht zu früh! Es könnte ein Zug sein, der auf dich zukommt!
----
It said: "Install Win95 or better ..." So I installed Linux.
Ich helfe gerne!
----------
Wenn du ein Licht am Ende des Tunnels siehst, freu dich nicht zu früh! Es könnte ein Zug sein, der auf dich zukommt!
----
It said: "Install Win95 or better ..." So I installed Linux.
- cloidnerux
- Moderator
- Beiträge: 3125
- Registriert: Fr Sep 26, 2008 4:37 pm
- Wohnort: Ram (Gibts wirklich)
Re: Zahlen über chinesischen Restsatz
Ein Mathematiker schafft es vlt nicht, vlt. aber viele.Ob ich das also lösen kann wenn es nicht einmal ein Mathematikprofessor für einfach hält ist fraglich...
Gemeinsam finden wir bestimmt eine Lösung
Redundanz macht wiederholen unnötig.
quod erat expectandum
quod erat expectandum
Re: Zahlen über chinesischen Restsatz
Man merkt das du gerade wissenschaftlich arbeitest. Wer sonst zitiert Links in ForenDirty Oerti hat geschrieben:Laut diesem PDF (Englisch) [1]
Wer weiß ob es die Lösung ist, aber ich hab zumindest einmal die gesuchte Arbeit gefundencloidnerux hat geschrieben:Gemeinsam finden wir bestimmt eine Lösung
Dank der Archivierungsarbeit von web.archive.org bleibt Wissen nämlich erhalten:
http://web.archive.org/web/200308101404 ... /~dmpotts/
http://web.archive.org/web/200308102355 ... sint1.html
"Make it idiot-proof and someone will invent an even better idiot." (programmers wisdom)
OpenGL Tutorials und vieles mehr rund ums Programmieren: http://www.tomprogs.at
OpenGL Tutorials und vieles mehr rund ums Programmieren: http://www.tomprogs.at
- Dirty Oerti
- Beiträge: 2229
- Registriert: Di Jul 08, 2008 5:05 pm
- Wohnort: Thurndorf / Würzburg
Re: Zahlen über chinesischen Restsatz
Ja, vielleicht. Irgendwie war ich zu faul, den URL-Knopf am oberen Ende zu benutzen...Kerli hat geschrieben:Man merkt das du gerade wissenschaftlich arbeitest. Wer sonst zitiert Links in Foren
Oh man, du bist ein Gott Das ist auf jedenfall schonmal super. Ich hab nun auch den Quelltext der Arbeit (was mich stark voran bringt) und sogar eine Buchempfehlung...Kerli hat geschrieben:Wer weiß ob es die Lösung ist, aber ich hab zumindest einmal die gesuchte Arbeit gefundencloidnerux hat geschrieben:Gemeinsam finden wir bestimmt eine Lösung
Dank der Archivierungsarbeit von web.archive.org bleibt Wissen nämlich erhalten:
http://web.archive.org/web/200308101404 ... /~dmpotts/
http://web.archive.org/web/200308102355 ... sint1.html
Und natürlich eine Emailadresse...aber ob mich die weiterbringt...da stehen Daten wie 1994....
Jetzt schau ich mal, was mein Mathelehrer morgen dazu spricht.
Und dann versuche, zu verstehen, was genau dieser Potts da in seinem Code tut...^^
Bei Fragen einfach an daniel[ät]proggen[Punkt]org
Ich helfe gerne!
----------
Wenn du ein Licht am Ende des Tunnels siehst, freu dich nicht zu früh! Es könnte ein Zug sein, der auf dich zukommt!
----
It said: "Install Win95 or better ..." So I installed Linux.
Ich helfe gerne!
----------
Wenn du ein Licht am Ende des Tunnels siehst, freu dich nicht zu früh! Es könnte ein Zug sein, der auf dich zukommt!
----
It said: "Install Win95 or better ..." So I installed Linux.
- Dirty Oerti
- Beiträge: 2229
- Registriert: Di Jul 08, 2008 5:05 pm
- Wohnort: Thurndorf / Würzburg
Re: Zahlen über chinesischen Restsatz
So, also ich hab mal wieder etwas überlegt, hab auch neue Anregungen bekommen.
Geändert hat sich an meinem Problem leider immer noch nichts^^
Eines weiß ich nun aber: Solange ich keine negativen Zahlen darstellen kann, kann ich auch nichts vergleichen.
Denn wie soll ich sonst das Ergebnis von 14-18 darstellen/begründen...?
Anregungen, die ich nun habe:
1. (Noch nicht getestet) Mit den Zahlen kann ich theoretisch einen Zahlenbereich von 0 bis hin zu einem Maximum M-1 darstellen. M ist das Produkt aller Module. Um einen negativen Zahlenbereich zu bekommen verschieben ich den Bereich "einfach" auf -M/2 bis M/2-1. Das heißt aber, dass 0 nicht mehr durch (0,0,0,...) dargestellt wird, sondern durch die Reste der Zahl M/2. Und die muss ich iwie berechnen (am besten dynamisch und ohne M auszurechnen, da das zu groß wird)
2. (Funktioniert nicht, hab ich mir heute zumindest überlegt, und ich finde keinen Weg, es iwie beweisen zu können, ich finde eben nur Widersprüche) Nach einer Subtraktion sind manche Reste negativ. Evtl lässt sich von der Anzahl der negativen Reste darauf schließen, ob die Zahl negativ ist oder nicht.
Hier meine Überlegungen:
Anmerkung: "Reste" bezeichnet im Zitiertem Abschnitt die Module
Geändert hat sich an meinem Problem leider immer noch nichts^^
Eines weiß ich nun aber: Solange ich keine negativen Zahlen darstellen kann, kann ich auch nichts vergleichen.
Denn wie soll ich sonst das Ergebnis von 14-18 darstellen/begründen...?
Anregungen, die ich nun habe:
1. (Noch nicht getestet) Mit den Zahlen kann ich theoretisch einen Zahlenbereich von 0 bis hin zu einem Maximum M-1 darstellen. M ist das Produkt aller Module. Um einen negativen Zahlenbereich zu bekommen verschieben ich den Bereich "einfach" auf -M/2 bis M/2-1. Das heißt aber, dass 0 nicht mehr durch (0,0,0,...) dargestellt wird, sondern durch die Reste der Zahl M/2. Und die muss ich iwie berechnen (am besten dynamisch und ohne M auszurechnen, da das zu groß wird)
2. (Funktioniert nicht, hab ich mir heute zumindest überlegt, und ich finde keinen Weg, es iwie beweisen zu können, ich finde eben nur Widersprüche) Nach einer Subtraktion sind manche Reste negativ. Evtl lässt sich von der Anzahl der negativen Reste darauf schließen, ob die Zahl negativ ist oder nicht.
Hier meine Überlegungen:
Anmerkung: "Reste" bezeichnet im Zitiertem Abschnitt die Module
Anregungen wären willkommenReste 3,5,7
Zahlen 14 und 18
14 = (2,4,0)
18 = (0,3,4)
18-14 = (-2,-1,4)
14-18 = (2,1,-4)
==> Annahme: Gerade Anzahl (2 von 3) an negativen Werten heißt positives Resultat, ungerade Anzahl deutet auf ein negatives Resultat hin.
Zahlen 1 und 30
1 = (1,1,1)
30 = (0,0,2)
30-1 = (-1,-1,1) ==> OK
1-30 = (1,1,-1) ==> OK
Reste 5,7,13
Zahlen 14 und 18
14 = (4,0,1)
18 = (3,4,5)
18-14 = (-1,4,4)
14-18 = (1,-4,-4)
====> Annahme kann so nicht stimmen (hier genau andersherum). Evtl Abhängigkeit von den genauen Resten?
Reste 3,5
Zahlen 14 und x mit x aus [0;14]
14 = (2,4)
0 = (0,0)
1 = (1,1)
2 = (2,2)
3 = (0,3)
4 = (1,4)
5 = (2,0)
6 = (0,1)
7 = (1,2)
8 = (2,3)
9 = (0,4)
10 = (1,0)
11 = (2,1)
12 = (0,2)
13 = (1,3)
14 - 0 = (2,4)
0 - 14 = (-2,-4)
14 - 1 = (1,3)
1 - 14 = (-1,-3)
14 - 2 = (0,2)
2 - 14 = (0,-2)
14 - 3 = (2,1)
3 - 14 = (-2,-1)
14 - 4 = (1,0)
14 - 5 = (0,4)
14 - 6 = (2,3)
14 - 7 = (1,2)
14 - 8 = (2,3)
14 - 9 = (1,1)
etc.
6 - 5 = (-2,1)
=> Problem => Annahme: Solange nicht beide Reste negativ sind, ist die Zahl positiv
5 - 6 = (2,-1)
4 - 6 = (1,3)
(1,3) ist auch gleichzeitig 13
=> 13 = -2 (zumindest in der Darstellung)
Was logisch ist, immerhin ist
-2 + 1*15 = 13
Foglich gehören -2 und 13 der selben Restklasse an und sind somit nicht unterscheidbar.
Anders ausgedrückt: Die -2 liegt außerhalb des darstellbaren Bereichs und wird deshalb ans obere Ende des Bereichs geschoben, sozusagen ein Underflow.
Bei Fragen einfach an daniel[ät]proggen[Punkt]org
Ich helfe gerne!
----------
Wenn du ein Licht am Ende des Tunnels siehst, freu dich nicht zu früh! Es könnte ein Zug sein, der auf dich zukommt!
----
It said: "Install Win95 or better ..." So I installed Linux.
Ich helfe gerne!
----------
Wenn du ein Licht am Ende des Tunnels siehst, freu dich nicht zu früh! Es könnte ein Zug sein, der auf dich zukommt!
----
It said: "Install Win95 or better ..." So I installed Linux.