Eine Harte Nuss

hui1991 · Verfasst: Mo 13.10.08 18:54

Hallo,

ich hab mir mal gedacht schreib ich mir mal ein Programm um ein 128Byte(In Bit sind das 1024) langes Passwort zu merken. Die Aufgabe steht im Anhang drin da die schon ein bisschen groß ist. ^^
Wenn einer ein Programm schreibt für das, dann. :shock:

Weil ich kein Plan hab wie ich da Anfangen soll.
Weil alle 1,797693134862315907729305190789e+308 Möglichkeiten durchzuprobieren, das dauert find ich auch ein wenig lang. ^^

Achja und es sollte auf einem P4 in 1h laufen, aber wenns auf ein Quad so schnell ist, ist auch nicht schlimm ^^

Achja und die Länge ist bei solchen Aufgaben immer bekannt.

Mensch wo bleiben die 2048-Kern Prozessoren ^^

So und etz ran an den leckeren Kuchen.

Einloggen, um Attachments anzusehen!

Wolle92 · Verfasst: Mo 13.10.08 19:05

Interessante Aufgabe...

Ich wette, du kriegst hier Lösungen vorgelegt, wie willst du aber kontrollieren, ob es alle möglichkeiten sind?

_________________
1405006117752879898543142606244511569936384000000000.

Hidden · Verfasst: Mo 13.10.08 19:35

Hi,

Also erstmal reduzieren: Wenn '11' 161 Mal enthalten ist, wäre '1' schonmal nurnoch 496 - 161 = 335 Mal übrig. Damit hast du alle Einzelbausteine, aus denen der Code potentiell besteht.
Jetzt Rekursiv oder in Schleifenform Einzelbausteine Aneinanderreihen und beim Zusammenfügen von '1'er- und '0'er- Strings alle darin enthaltenen '01'er-Strings für diesen Schleifendurchlauf/diese Rekursion entfernen.

Damit sind wir eigentlich schon fertig( :gruebel:

).

Was mir Sorgen macht ist, auf welchen PC bezogen du die 1h normierst.. Also auf meinem Quanten-ZweitPC läuft das fertige Programm in 2 ms durch. Ist leider nicht Windows-kompatibel, kann dir also leider die Resultate nicht zuschicken

.

mfG,

_________________
Centaur spears can block many spells, but no one tries to block if they see that the spell is a certain shade of green. For this purpose it is useful to know some green stunning hexes. (HPMoR)

hui1991 · Verfasst: Mo 13.10.08 21:21

Ich weiß nicht wie viele Lösungen es gibt, aber ich weiß das es mindestens 1 Lösung gibt.
Es geht mir eigentlich darum nur um sowas zurückrechnen zu können.
Und wie viele Ergebnisse es sind.

[highlight]Quanten-ZweitPC[/hightlight]
Dachte die gibts erst in 10 Jahren oder so ^^

ne meine vllt so auf einem P4 oder QuadCore ist ziemlich egal.

Achja und die Anzahl der Möglichkeiten verringert sich weniger als bei dir.
Weil z. B.

00010010111010

hat

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

Das Beispiel ist denke ich gut, um zu verstehen wie die Werte zustande kommen.

Das spuckt zumindest mein Programm aus. ^^
Wäre nur interessant zu wissen ob es bei 1024 Zeichen schnell zurückgerechnet werden kann.
Und wie man ein Programm schreiben könnte um die Möglichkeiten aufzulisten.
Ich hab leider keine Zeit um mir darum mir gedanken zu machen.

Vllt. erstmal mit dem oberen Beispiel herausfinden wie man an das Ergebnis kommt.
Ist vllt. einfacher.
Wenn das kleine Programm, dann rechnet (nicht durchprobiert), dann müsste man das große auch schaffen.

Weil: 000111000111 <> 111000111000 <> 000111111000 <> 000000111111 <> 111000000111

Es gibt Maximal 80 Eigenschaften:

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:

               1
              11
             111
            1111
           11111
          111111
         1111111
        11111111
               0
              01
             011
            0111
           01111
          011111
         0111111
        01111111
       011111111
              00
             001
            0011
           00111
          001111
         0011111
        00111111
       001111111
      0011111111
             000
            0001
           00011
          000111
         0001111
        00011111
       000111111
      0001111111
     00011111111
            0000
           00001
          000011
         0000111
        00001111
       000011111
      0000111111
     00001111111
    000011111111
           00000
          000001
         0000011
        00000111
       000001111
      0000011111
     00000111111
    000001111111
   0000011111111
          000000
         0000001
        00000011
       000000111
      0000001111
     00000011111
    000000111111
   0000001111111
  00000011111111
         0000000
        00000001
       000000011
      0000000111
     00000001111
    000000011111
   0000000111111
  00000001111111
 000000011111111
        00000000
       000000001
      0000000011
     00000000111
    000000001111
   0000000011111
  00000000111111
 000000001111111
0000000011111111

Dann stopt mein Programm weitere Aufzulisten.
Wie weit es das erschwert keine Ahnung. ^^

Ich hänge mal mein Programm zum berechnen an, damit ihr selber testen könnt.

Einloggen, um Attachments anzusehen!

Thorsten83 · Beiträge: 191 Erhaltene Danke: 1

Du gehst also so durch dass du guckst wie oft z.B. 011 vorkommt, und wenn es mehr als einmal vorkommt guckst du als nächstes auch noch wie oft 0011 und 0111 vorkommen?

Ehemaliges Mitglied Erhaltene Danke: 1

@Quanten-PC:Gibs schon!Das Besondere:Er rechnet mit Atomen die im Quanten-Zustand sind,dass
heißt das alle Atome ,die in diesen Zustand versetzt wurden,keine richtige Identität haben.Das
heißt für den PC das jedes Atom eine 1 ,eine 0,oder beides gleichzeitig sein kann.

Hidden · Verfasst: Mo 13.10.08 22:21

j.klugmann hat folgendes geschrieben :

@Quanten-PC:Gibs schon!Das Besondere:Er rechnet mit Atomen die im Quanten-Zustand sind,dass
heißt das alle Atome ,die in diesen Zustand versetzt wurden,keine richtige Identität haben.Das
heißt für den PC das jedes Atom eine 1 ,eine 0,oder beides gleichzeitig sein kann.

Definitiv falsch :gruebel:

Und wenn, dann wären das afaik superpositionierte Elektronen. Aber der Rest Stimmt: Durch die Superposition sind beliebige Kombinationen aus den denkbaren Zuständen Spin Up(->1) und Spin Down(->0) möglich.

Während einer Rechnung. Zum Auslesen ist allerdings Dekoheränz unvermeidbar: Der Rückgabewert kann diese Eigenschaften nciht haben, sodnern muss eindeutig sein

mfG,

_________________
Centaur spears can block many spells, but no one tries to block if they see that the spell is a certain shade of green. For this purpose it is useful to know some green stunning hexes. (HPMoR)

Ehemaliges Mitglied Erhaltene Danke: 1

Ok,ok!Ich habe ehrlich nur geraten.Ich habe zwar schon von den PC's gehört,aber wie sie
funktionieren wusste ich nciht. :shock:

BenBE · Verfasst: Mo 13.10.08 23:24

Hab mal ne Frage zur Zählweise:

hui1991 hat folgendes geschrieben :

Weil z. B.

00010010111010

hat

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

Also für mich hat 00010010111010 immer noch 2 Mal 11:
00010010111010 und 00010010111010

Oder zählst Du anders?

_________________

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Jann1k · Verfasst: Mo 13.10.08 23:27

Off Topic:

Das es Quanten PCs schon gibt wäre mir auch neu, bisher kann man die Superposition doch kaum länger als einige (Milli)Sekunden aufrechterhalten oder ist der Stand der Technik heute schon weiter? Aufklärung pls.

Hidden · Verfasst: Mo 13.10.08 23:43

Hi,

Mit Quanten-PCs lassen sich große Zahlen in sehr kurzer Zeit(kA, was da theoretisch möglich ist? Femtosekunden?) in ihre Primfaktoren aufteilen. 1&1 zeigt mir aber momentan eine sichere Verbindung an. Qed: Es gibt noch keine Quantencomputer :mrgreen:

Christian schaut uns aber morgen ganz bös' an, wenn er sieht, was wir hier heute Nacht fabriziert haben. Insofern jetzt lieber 'nen neuen Thread aufmachen, ehe wir morgen als Steinsäulen erwachen

mfG,

_________________
Centaur spears can block many spells, but no one tries to block if they see that the spell is a certain shade of green. For this purpose it is useful to know some green stunning hexes. (HPMoR)

Thorsten83 · Beiträge: 191 Erhaltene Danke: 1

BenBE hat folgendes geschrieben :

Hab mal ne Frage zur Zählweise:

hui1991 hat folgendes geschrieben :

Weil z. B.

00010010111010

hat

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

Also für mich hat 00010010111010 immer noch 2 Mal 11:
00010010111010 und 00010010111010

Oder zählst Du anders?

So wie ich das sehe zählt er bis 00010010111010 einen "Zweier" und fängt dann bei 00010010111010 an weiterzuzählen, so komme ich zumindest auf die Zahlen...
Wobei der erste Schritt imho sein müsste zu gucken wie oft z.B. 0111 vorkommt und daraus zu folgern welche 111 dadurch schon verbraucht werden und wegfallen, bei dem Beispiel komm ich damit auf "nur" noch ungefähr 30! Kombinationen, wenn mir einer eine Festplatte bezahlt auf der ich die alle speichern kann schreib ich ihm auch das Programm

hui1991 · Verfasst: Di 14.10.08 05:39

000111000111 <> 111000111000 <> 000111111000 <> 000000111111 <> 111000000111
//das Beispiel ist nur, das die Werte immer anders gezählt werden

gehört nicht zu dem Beispiel nur:
00010010111010

gehört zu dem Beispiel:
1: 6
11: 1
111: 1
0: 8
01: 4
011: 1
0111: 1
00: 2
001: 2
000: 1
0001: 1

Das Programm kann eigentlich alles so zählen und bei großen Zahlen kann das ein Mensch fast gar nicht mehr überprüfen müsste aber eigentlich so stimmen. ^^

Jede Eigenschaft wurde von Anfang an neu gezählt so ist:
000:
0:3
00:1
000:1

BenBE · Verfasst: Di 14.10.08 10:08

@hui: Definiere doch bitte einfach mal in einer entsprechenden Regel, wie deine Zählung funktioniert. Am Besten mit einem vollständig gezählten Beispiel UND mit Angabe, warum bestimmte Vorkommen nicht gezählt werden.

Ich zumindest würde intuitiv so zählen:

Beispiel: 0000

markieren

Quelltext

1:
2:
3:
4:

   0: 4 (0000 0000 0000 0000)
  00: 3 (0000 0000 0000)
 000: 2 (0000 0000)
0000: 1 (0000)

Beispiel: 0010

markieren

Quelltext

1:
2:
3:
4:

 0: 3 (0010 0010 0010)
00: 1 (0010)
01: 1 (0010)
 1: 1 (0010)

Bitte sagen, wenn ich welche vergessen hab, das sollten sie aber soweit sein ...

In Worten also: Ich zähle, wie häufig sich ab jeder Position X der Substring der Eigenschaft matchen lässt.

_________________

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Thorsten83 · Beiträge: 191 Erhaltene Danke: 1

Das ist fies solche eine Frage zu stellen wenn ich lernen sollte

Ich dachte ja ich hätte deine Zählweise verstanden, wenn ich deine Angaben reduzier krieg ich auch eine genaue Anzahl von Sequenzen mit einer Gesamtlänge von 1024, allerdings kommen 2 Sequenzen -1 mal vor

Edit:
A la mierda, hab's gerade gesehen...
Bei einer Folge von 10 Einsen gibt dein Programm folgendes aus:

1: 10
11: 5
111: 3
1111: 2
11111: 2
111111: 1
1111111: 1
11111111: 1

Und das passt mit meiner Art der Reduzierung nicht zusammen die davon ausgeht, dass man vollständige Informationen über diese 0/1-Sequenzen hat.

baka0815 · Verfasst: Di 14.10.08 14:55

Ich versteh's so, dass immer in x-Blöcken gesucht wird, wobei x die Länge der Zeichen ist.

Wenn ich von 1111111111 (10x1) ausgehe, ergibt sich folgendes:

Suche nach 1: 10 mögliche Stellen: 1 1 1 1 1 1 1 1 1 1

Suche nach 11: 5 mögliche Stellen: 11 11 11 11 11

Suche nach 111: 3 mögliche Stellen: 111 111 111 1

Suche nach 1111: 2 mögliche Stellen: 1111 1111 11

Suche nach 11111: 2 mögliche Stellen: 11111 11111

Suche nach 111111 und höher: 1 mögliche Stelle: 111111 1111, 1111111 111, 11111111 11, 111111111 1, 1111111111.

Thorsten83 · Beiträge: 191 Erhaltene Danke: 1

baka0815 hat folgendes geschrieben :

Ich versteh's so, dass immer in x-Blöcken gesucht wird, wobei x die Länge der Zeichen ist.

Wenn ich von 1111111111 (10x1) ausgehe, ergibt sich folgendes:

Suche nach 1: 10 mögliche Stellen: 1 1 1 1 1 1 1 1 1 1

Suche nach 11: 5 mögliche Stellen: 11 11 11 11 11

Suche nach 111: 3 mögliche Stellen: 111 111 111 1

Suche nach 1111: 2 mögliche Stellen: 1111 1111 11

Suche nach 11111: 2 mögliche Stellen: 11111 11111

Suche nach 111111 und höher: 1 mögliche Stelle: 111111 1111, 1111111 111, 11111111 11, 111111111 1, 1111111111.

So hab ich das auch verstanden und bei letzterem feststellen müssen dass maximal nach Blöcken der Länge 8 gesucht wird, was das ganze nicht gerade vereinfacht.
Wobei ich wie gesagt denke dass Vereinfachungen die Laufzeit von grob geschätzt 1000 Jahre auf 10 Jahre verkürzen, ausreichend wird das immer noch nicht sein...

hui1991 · Verfasst: Di 14.10.08 16:17

Nochmal damit es jeder versteht:
1111111111

Um die Anzahl der 1 zu finden macht das Programm folgendes:

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

1111111111 // Vorkommen von 0 auf 1 erhöhen
X111111111 // Vorkommen von 1 auf 2 erhöhen
XX11111111 // Vorkommen von 2 auf 3 erhöhen
XXX1111111 // Vorkommen von 3 auf 4 erhöhen
XXXX111111 // Vorkommen von 4 auf 5 erhöhen
XXXXX11111 // Vorkommen von 5 auf 6 erhöhen
XXXXXX1111 // Vorkommen von 6 auf 7 erhöhen
XXXXXXX111 // Vorkommen von 7 auf 8 erhöhen
XXXXXXXX11 // Vorkommen von 8 auf 9 erhöhen
XXXXXXXXX1 // Vorkommen von 9 auf 10 erhöhen
XXXXXXXXXX // Es wurden 10 Vorkommen gefunden

Um die Anzahl der 11 zu finden macht das Programm folgendes:

markieren

Quelltext

1:
2:
3:
4:
5:
6:

1111111111 // Vorkommen von 0 auf 1 erhöhen
XX11111111 // Vorkommen von 1 auf 2 erhöhen
XXXX111111 // Vorkommen von 2 auf 3 erhöhen
XXXXXX1111 // Vorkommen von 3 auf 4 erhöhen
XXXXXXXX11 // Vorkommen von 4 auf 5 erhöhen
XXXXXXXXXX // 5 Vorkommen gefunden

Um die Anzahl der 111 zu finden macht das Programm folgendes:

markieren

Quelltext

1:
2:
3:
4:

1111111111 // Vorkommen von 0 auf 1 erhöhen
XXX1111111 // Vorkommen von 1 auf 2 erhöhen
XXXXXX1111 // Vorkommen von 2 auf 3 erhöhen
XXXXXXXXX1 // 3 Vorkommen gefunden

Um die Anzahl der 1111 zu finden macht das Programm folgendes:

markieren

Quelltext

1:
2:
3:

1111111111 // Vorkommen von 0 auf 1 erhöhen
XXXX111111 // Vorkommen von 1 auf 2 erhöhen
XXXXXXXX11 // 2 Vorkommen gefunden

Um die Anzahl der 11111 zu finden macht das Programm folgendes:

markieren

Quelltext

1:
2:
3:

1111111111 // Vorkommen von 0 auf 1 erhöhen
XXXXX11111 // Vorkommen von 1 auf 2 erhöhen
XXXXXXXXXX // 2 Vorkommen gefunden

Um die Anzahl der 111111 zu finden macht das Programm folgendes:

markieren

Quelltext

1:
2:

1111111111 // Vorkommen von 0 auf 1 erhöhen
XXXXXX1111 // 1 Vorkommen gefunden

Um die Anzahl der 1111111 zu finden macht das Programm folgendes:

markieren

Quelltext

1:
2:

1111111111 // Vorkommen von 0 auf 1 erhöhen
XXXXXXX111 // 1 Vorkommen gefunden

Um die Anzahl der 11111111 zu finden macht das Programm folgendes:

markieren

Quelltext

1:
2:

1111111111 // Vorkommen von 0 auf 1 erhöhen
XXXXXXXX11 // 1 Vorkommen gefunden

So arbeitet das Programm die Werte um.

Ist eigentlich nur eine for-schleife die pos(gesuchter_wert,s) macht und alle vorkommen mit X belegt (darf nicht 0 oder 1 sein, weil die würden wieder gefunden werden).

Wie gesagt ich habe keine Vorstellungen ob die Aufgabe überhaupt möglich ist, das ein Programm mit heutigen Rechnern das so schnell berechnen kann. Wenn er es kann, ob man überhaupt eine nicht zu große Liste hat. ^^

Anzahl vergleich:
1 > 11 >= 111 >= 1111 >= 11111 >= 111111 >= 1111111 >= 11111111

Es kann nie vorkommen das die Anzahl der 1 weniger ist als der 11! usw.

Thorsten83 · Beiträge: 191 Erhaltene Danke: 1

Hey,
ich glaub soweit war das schon klar

Das Problem ist halt dass man diese Informationen imho nicht sinnvoll verwenden kann, da man z.B. keine 9 aufeinanderfolgende Einsen angezeigt bekommt.

Zu der Geschwindigkeit: Bei dem von dir gebrachten Beispiel kann man als untere Schranke für die Anzahl der möglichen Kombinationen ungefähr 32! nehmen. (wobei das auch schon zu klein ist, aber nur um mal eine Größenordnung zu bekommen...)
Jede dieser Lösungen ist 128 Byte groß, also alle Lösungen zusammen 3,4*10^28GB.

Da ich soviel RAM habe werde ich diese Lösungen da mal reinschreiben

Der RAM schafft - grob geschätzt - 3,4GB/s.
Damit brauch ich also 10^28 Sekunden um die Lösungen in meinen Arbeitsspeicher (!) zu schreiben.

Falls ich mich irgendwo verrechnet haben sollte bitte ich darum mich zu korrigieren

Martok · Verfasst: Di 14.10.08 18:03

Also, die 128 Byte muss man wahrscheinlich doch Bruteforcen. Da die Anzahl der 1en bekannt ist, dürfte das relativ zügig gehen falsche Werte rauszukanten.
Danach immer wieder Muster Zählen, beginnend mit den längsten Patterns. user profile icon

Gausi kann da sicher viele schöne Sachen zu sagen

Sobald man zu viele vorkommen hat, ist das Muster raus.

Vermutlich wird das aber trotzdem nicht so schnell gehen... Multicore/Manycore ist hier praktisch bzw. extrem sinnvoll. Eventuell kommt man auf ein paar Tage runter...

@Thorsten: ich vermute bald dass es nur eine Hand voll solcher Zahlen gibt. Wenn überhaupt.
Beweisen kann ich das nicht, aber wer stellt bitte Aufgaben die 3170979198376458650431 Jahre dauern^^

Edit: Eine Q'n'D Implementation einer Zähl-Klasse kommt auf 8,5 Sekunden um bis 1Mrd zu zählen. Kein ASM, Pascal, Register-Calls. REKURSION(!) :shock:

Also im Grund Optimierungsbedürftig/-pflichtig. Ohne Rekursion ist der Code unlesbar, aber doppelt so schnell. Bin jetzt auf 4 Sekunden runter.

_________________
"The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme