Die Mathe-Redaktion - 19.06.2019 13:27 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte / Top 15
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
Listenpunkt? im neuen Schwätz
ListenpunktWerde Mathe-Millionär!
ListenpunktAnmeldung MPCT Sept.
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 607 Gäste und 22 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von matph
Informatik » Programmieren » Bitfeld simulieren
Druckversion
Druckversion
Antworten
Antworten
Autor
Kein bestimmter Bereich Bitfeld simulieren
pzktupel
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.09.2017
Mitteilungen: 939
Aus: Thüringen,Erfurter Raum
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2019-05-25 10:28


Vorab, vielleicht ist folgendes trivial...

Hallo MP-Freunde !
da ich in Freebasic kein echtes BitArray aufstellen kann, ist mir gestern Abend eine Lösung gekommen,
die noch eine andere Erkenntnis brachte. Die Erkenntnis war, einen vielleicht neuen Weg zur dualen Zerlegung einer Zahl.
Ich könnte nun praktisch in einem 100Mio Feld vom Typ 64Bit Integer bis zu 6.4Mrd an Daten simuliert unterbringen, ohne Boolean zu nutzen.

Angenommen der Index wäre 9.

Daten liegen vor vom Wert
9
100000009
300000009
800000009

Frage:Wie kodiere ich das im Feld 9 und wie erhalte ich die Urdaten zurück ?

Man schneidet die erste Zahl vorne ab, das sind 0,1,3,8 und addiert im Feld[9] 2^0+2^1+2^3+2^8=267
Die Frage ist nun, wie gewinne ich exakt aus der Zahl 267 die 0,1,3,8 wieder heraus ?
Und da ist mir eine Eigenschaft gekommen, die ich so noch nicht gehört habe.
Hätten wir als Bsp die Zahl 2333 und würden diese dual zerlegen, dann klappt das auch so:
Prüfe Zahl mod 2^n, ist der Rest größer 2^(n-1) dann ist die Stelle im Dualsystem besetzt.
2333 MOD 2^12=2333 ,>2^11 :1
2333 MOD 2^11=2333 ,<2^10 :0
2333 MOD 2^10=2333 ,<2^9 :0
2333 MOD 2^9=2333 ,>2^8 :1
2333 MOD 2^8=2333 ,<2^7:0
2333 MOD 2^7=2333 ,>2^6 :0
2333 MOD 2^6=2333 ,>2^5 :0
2333 MOD 2^5=2333 ,>2^4 :1
2333 MOD 2^4=2333 ,>2^3 :1
2333 MOD 2^3=2333 ,>2^2 :1
2333 MOD 2^2=2333 ,>2^1 :0
2333 MOD 2^1=2333 ,>2^0 :1
Dual:100100011101
Zum Feld[9]=267
267 MOD 512=267,>256 ja, vorhanden 256->8
267 MOD 256=11,>128 nein
267 MOD 128=11,>64 nein
267 MOD 64=11,>32 nein
267 MOD 32=11,>16 nein
267 MOD 16=11,>8 ja, vorhanden 16->3
267 MOD 8=3,>4 nein
267 MOD 4=3,>2 ja, vorhanden 4->1
267 MOD 2=1,>=2^0, ja vorhanden 2->0
0,1,3,8 sind die Inhalte, die beim Zurückrechnen
000000009
100000009
300000009
800000009
liefern.


Im allgemeinen heißt das nicht vorrangig, alle Daten zurückzuholen, sondern eine Anfrage , ob ein Wert uncodiert vorhanden war:

Wenn der Feldinhalt [9]=267 hat und man will wissen, ob 200000009 dabei war , dann genügt 267 MOD 8 =3 (3<4) NEIN, nicht dabei gewesen.

Gruß


Ergänzung: Der Unterschied ist aber zum Bitfeld, das hier auch Daten von 6.4 Mrd praktisch auf 800 MB RAM gepuffert werden können, aber im Gegensatz das Feld auf 100Mio statt 800Mio abfällt.


-----------------
Pech in der Liebe , Glück im Verlieren !!!



  Profil  Quote  Link auf diesen Beitrag Link
AnnaKath
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.12.2006
Mitteilungen: 3161
Aus: hier und dort (s. Beruf)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2019-05-25 12:11


Huhu pzktupel,
eigentlich freute mich auf eine mittägliche bitshifterei, doch beim besten Willen habe ich keine Idee, was Du hier überhaupt tun willst. Falls Du keine Diskussion erreichen möchtest, bin ich es gerne zufriedenen; solltest Du aber daran interessiert sein, könnte es sicher nicht schaden, etwas genauer zu beschreiben, was Du hier tust.
lg, AK.



  Profil  Quote  Link auf diesen Beitrag Link
pzktupel
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.09.2017
Mitteilungen: 939
Aus: Thüringen,Erfurter Raum
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2019-05-25 12:16


Ja, das werde ich tun, im Moment programmiere ich das für mein AP12 Sieb.
Mir ist es quasi gelungen, alle Zahlen bis 6.4 MRD in ein Feld von 100 Mio unterzubringen.

Wo ist jetzt , was unklar ist , damit ich ansetzen kann.

Ob boolean oder meines, wird den gleichen Spreicher benötigen, aber der Unterschied ist, das mein Feld mit 100Mio statt 800Mio (theoretisch) hinbekommen würde.

Ich bin nicht das Programmier-Ass, aber aus der Not heraus kam nach langem doch mal eine Idee.


Grundidee ist:

Es gibt viele Möglichkeiten, eine Dezimalzahl in Dual umzurechnen und stellte nebenbei fest (was mathematisch klar ist):

Berechnet man von einer Zahl N: N MOD 2^a und ist dieser > 2^(a-1), dann
hat die Zahl N an der Stelle a-1 eine 1 in der Dualdarstellung.

Das könnte man Nutzen, um aus einer Summe aus unterschiedlichen 2^a (oben die 267) herauszubekommen, ob ein Element in der Reduzierten Abspeicherung vorher vorhanden war.


Bsp: Hat 9817498141941 in der Dualdarstellung die Position 17 von rechts gesehen nun eine 1 oder eine 0 ?

Antwort: 9817498141941 MOD 2^17 = 83189 , 83189>2^16. Also ja, die 17. Position hat eine 1.

Was ist mit der 18. oder 16. ?
9817498141941 MOD 2^18 = 83189 , 83189<2^17 , hat eine NULL
9817498141941 MOD 2^16 = 17653 , 17653<2^15 , hat eine NULL

Ist umgesetzt, klappt auch, aber zu langsam..



-----------------
Pech in der Liebe , Glück im Verlieren !!!



  Profil  Quote  Link auf diesen Beitrag Link
darkhelmet
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 05.03.2007
Mitteilungen: 2610
Aus: Bayern
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2019-05-25 13:59


Ich kenne mich mit Basic nicht aus, aber hier sieht es so aus, als würde es das schon geben:
www.freebasic-portal.de/befehlsreferenz/bit-56.html

Ansonsten ist in Maschinencode wahrscheinlich am schnellsten:
1. ein bitweises AND mit der Zahl, deren Dualdarstellung eine Eins beim gesuchten Bit und sonst lauter Nullen hat
2. eine Abfrage, ob das Ergebnis ungleich 0 ist.

Wenn du bitweise Operatoren zur Verfügung hast, ist das wahrscheinlich schneller als deine Lösung, es sei denn, dein Compiler ist so schlau, dass er aus deiner Lösung das gleiche macht.



  Profil  Quote  Link auf diesen Beitrag Link
darkhelmet
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 05.03.2007
Mitteilungen: 2610
Aus: Bayern
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2019-05-25 14:28


Wenn du keinen 64-Bit Integer verwendest, sondern was kleineres, wird es wahrscheinlich auch schneller.



  Profil  Quote  Link auf diesen Beitrag Link
pzktupel
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.09.2017
Mitteilungen: 939
Aus: Thüringen,Erfurter Raum
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2019-05-25 15:31


Bin mit dem SHL etwas weiter.

> Wenn du keinen 64-Bit Integer verwendest, sondern was kleineres, wird es wahrscheinlich auch schneller.

Darum geht es primär nicht.

Folgendes Problen. (Bsp)

Du hast 100 Millionen Zahlen auf 1 Mrd willkürlich verstreut.

Jetzt könnte man ein Feld 1 Mrd aufspannen und den Inhalt auf 1 setzen, wie die Zahl eben lautet F[9]=1, Da 9 vorhanden.
Nun sind dann aber 1GB RAM weg und man hat mehr als ein Kern.

Die Idee ist nun, ein Feld bis 100 Mio = 100MB RAM derart zu füllen, dass alle 100 Mio Platz haben und diese auch wieder zurückzugewinnen.

Also wenn ich darunter hätte: 7, 100000017,8000000017 sind so zu kodieren, das dies im Feldinhalt eindeutig verschlüsselt sind.


-----------------
Pech in der Liebe , Glück im Verlieren !!!



  Profil  Quote  Link auf diesen Beitrag Link
pzktupel
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.09.2017
Mitteilungen: 939
Aus: Thüringen,Erfurter Raum
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2019-05-25 16:01


2019-05-25 13:59 - darkhelmet in Beitrag No. 3 schreibt:
Ich kenne mich mit Basic nicht aus, aber hier sieht es so aus, als würde es das schon geben:
www.freebasic-portal.de/befehlsreferenz/bit-56.html

Ansonsten ist in Maschinencode wahrscheinlich am schnellsten:
1. ein bitweises AND mit der Zahl, deren Dualdarstellung eine Eins beim gesuchten Bit und sonst lauter Nullen hat
2. eine Abfrage, ob das Ergebnis ungleich 0 ist.

Wenn du bitweise Operatoren zur Verfügung hast, ist das wahrscheinlich schneller als deine Lösung, es sei denn, dein Compiler ist so schlau, dass er aus deiner Lösung das gleiche macht.

SUPER ! Habs hinbekommen mit SHL, ist etwa so schnell wie ein BYTE Feld :-)


Der RAM fällt von 1GB auf erwartete 200MB

Die Schlüsselzeilen sind:

X=NX+VS:Y=X MOD 10:
IF (F(X\10) AND (1 SHL Y))=0 THEN k+=1:GOTO S

Wobei X zwischen 0 und 10^9 irgendwas ist und (1 SHL Y) prüft, ob die 2er Potenz [0..9]  im Feldinhalt zu finden ist.


Thx !

Update: Programm läuft sogar schneller als mit BYTE Array über 1 Mrd.



-----------------
Pech in der Liebe , Glück im Verlieren !!!



  Profil  Quote  Link auf diesen Beitrag Link
pzktupel hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2019 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]