[ALG] Efficiënter opslaan range van getallen

[basvd]

Ik wil een 3-tal getallen in de range van 0-150 zo efficiënt mogelijk opslaan.
Vb.: 20-125-12 of 120-143-5

Momenteel sla ik deze getallen op als 3x verschillende ASCII characters. Dit kost mij elke keer 3 bytes.

Nu is even mijn vraag of het ook mogelijk is om deze 3 getallen op te slaan in 2 bytes?

Optellen zou een optie zijn: 120-143-5= 268. Dat zijn dan 2 ASCII characters; 256 en 12. Maar op deze manier kan ik nooit terug naar de 3 orginele getallen. Of zie ik iets nu over het hoofd?

[Verwijderd]

Ik denk het niet echt... voor 150 heb je al 7 bits nodig... Ik zie niet echt een manier om 21 bits in 1 of 2 bytes proppen. Maar wat is mis met 3 bytes? Is het voor een embedded toepassing?

[Verwijderd]

Je zou moeten gaan comprimeren, in feite net zo als programma's als WinRAR dit doen...

[ Voor 87% gewijzigd door Verwijderd op 19-06-2009 19:49 ]

[Confusion]

Moeten het perse eenheden van 8 bits zijn of ben je ook geholpen als het te reduceren is tot pakweg 22 bits gemiddeld? Moet de volgorde behouden blijven? Zijn de getallen gelijk over de range verdeeld?

Stel dat je bijvoorbeeld altijd een getal tussen de 0 en de 64 hebt en je zou dat getal altijd vooraan kunnen plaatsen: dan zou je de eerste 6 bits voor dat getal kunnen gebruiken en de volgende 16 voor de overige twee: dan reduceer je drie getallen tot 22 bits.

Interessanter is misschien de winst die te halen is doordat je meerdere combinaties van getallen op moet slaan: stel dat je altijd een paar honderd van dit soort paren hebt. Dan kan het best zijn dat een vorm van compressie al bruikbaar is om de benodigde opslagcapaciteit te verkleinen (ten koste van rekenkracht). Er zijn talloze mogelijkheden, maar daarvoor moeten meer randvoorwaarden bekend zijn.

[basvd]

@AiChan: voor 150 heb je zelfs al 8 bits nodig deze valt namelijk in de laatste bit-range 128-256. En ja het gaat over een soort embedded toeppasing waarbij de hoeveelheid data nogal van toepassing is.

@grizzlybeer: Oké, maar weet jij de precieze methode achter winRAR? En werkt dat ook voor slechts 3 bytes?

@Confusion: Nee, het hoeft niet persé in een veelvoud van bytes(17-bits zou ook al prima zijn). De volgorde moet hetzelfde blijven, en de range tussen de getallen is nooit gelijk.
Het zou bijvoorbeeld ook 1-2-149, 3-140-7, 1-2-3, 8-8-8, 140-140-140 kunnen zijn.

Je voorbeeld met het 'wegsnoepen' van bits gaat helaas in dit geval niet.

[ Voor 3% gewijzigd door basvd op 19-06-2009 20:19 ]

[farlane]

basvd schreef op vrijdag 19 juni 2009 @ 20:17:
@AiChan: voor 150 heb je zelfs al 8 bits nodig deze valt namelijk in de laatste bit-range 128-256. En ja het gaat over een soort embedded toeppasing waarbij de hoeveelheid data nogal van toepassing is.

Tenzij je honderduizenden van je embedded devices gaat verkopen is een iets uP met meer geheugen waarschijnlijk een betere oplossing.

[Henk007]

Volgens mij kom je met Huffmann coding dicht bij de entropisch dichtste pakking voor je data (~22bits per dataset) , mits n=voldoende groot.

[basvd]

farlane schreef op vrijdag 19 juni 2009 @ 20:22:
[...]

Tenzij je honderduizenden van je embedded devices gaat verkopen is een iets uP met meer geheugen waarschijnlijk een betere oplossing.

Tja klopt..., helaas is het sofware voor een bestaand device. Waarbij ik een vast aantal bytes van het opslaggeheugen mag gebruiken voor de software.

[basvd]

Henk007 schreef op vrijdag 19 juni 2009 @ 20:33:
Volgens mij kom je met Huffmann coding dicht bij de entropisch dichtste pakking voor je data (~22bits per dataset) , mits n=voldoende groot.

Effe snel gelezen. Zoals ik het nu begrijp moet ik 'gewichten' tegenover getallen gaan zetten. Iets wat niet van toepassing is, want ik weet nooit hoevaak of wanneer een getal voor gaat komen in mijn reeks getallen.

[Terror]

Ik denk dat als je alle volgorden kan verwachten in je reeksen dat comprimeren niet gaat lukken. Volgensmij maakt compressie altijd gebruik van bepaalde eigenschappen in de dataset, waardoor de dataset efficienter te noteren is. In het geval van jpeg of mp3 wordt er zelfs informatie weggegooid.

Je hebt 151^3 opties die je aangeboden kan krijgen, dus ik denk niet dat je het onder de 21 bits kan krijgen ( 151^3 < 2^22, dus 21 bits volstaat). Zijn er waarden die je kan uitsluiten? Kan je vertellen he je reeks tot stand komt?

[ Voor 23% gewijzigd door Terror op 19-06-2009 21:02 ]

[roy-t]

Comprimeren gebruikt ook vaak dictionaries waarbij 150 bijvoorbeeld gecodeerd wordt als 3 item uit rij B. Echter voor 3x getallen tussen 0 en 256 zul je toch een dict moeten hebben van 256 items dus schiet dat in dit geval niet op. Tenzij sommige getallen nooit voorkomen.

[leuk_he]

Terror schreef op vrijdag 19 juni 2009 @ 20:57:
Je hebt 151^3 opties die je aangeboden kan krijgen, dus ik denk niet dat je het onder de 21 bits kan krijgen ( 151^3 < 2^22, dus 21 bits volstaat). Zijn er waarden die je kan uitsluiten? Kan je vertellen he je reeks tot stand komt?

Je heb toch 22 bit nodig he? want 151^3 > 2^21, anders kun de laatste bits niet opslaan. om die 8,3% te besparen moet je dan nog best wat code schrijven.

compressie/huffman codering werkt alleen goed als je data niet random verdeeld zou zijn, dus je data uitsmeren over 22 bits gaat nog het beste.


3 getallen n1 n2 n3

coderen

resultaat=n1+n2*151+n3*151^2

decoderen

n1=res modules 151
n3=rounddown(res / (151^2))
n2=(res -n1 -n3)/151

en nog wat werk om dat in 22 bits te schuiven.

[Voutloos]

Nu de TS weet dat het ipv 24 bits 22 bits kan zijn: Boeit deze besparing dan nog wel?

Imo : Het is geen 1960 meer, inmiddels is een uur devtijd meer waard dan 1 bitje.

[ Voor 56% gewijzigd door Voutloos op 19-06-2009 21:58 ]

[DrClaw]

misschien met delta's gaan werken.

je getallen zijn: A-B-C. dan doe je

store A
store B-A mod 150
store C-B mod 150

en dat ga je dan encoden. het idee is dat de getallen hopelijk klein zijn, zodat je met minder bits uit kunt komen. echter, met getallen valt niet veel te doen.

zijn er combo's die niet voorkomen? wat voor data is het eigenlijk? ga je een shitload aan 3 getallen opslaan, of is dit een soort gokautomaat-score-dinges?

[Voutloos]

Als alle combinaties voorkomen, gaan delta's je niet helpen. Pigeon Hole Principle, beter dan 151³ gaat het niet worden.

[farlane]

basvd schreef op vrijdag 19 juni 2009 @ 20:35:
[...]

Tja klopt..., helaas is het sofware voor een bestaand device. Waarbij ik een vast aantal bytes van het opslaggeheugen mag gebruiken voor de software.

Andere mogelijkheden? Opslaan in flash misschien als er niet vaakgeschreven gaat worden? Extern RAM erbij aan hangen?

[Terror]

leuk_he schreef op vrijdag 19 juni 2009 @ 21:53:
[...]
Je heb toch 22 bit nodig he? want 151^3 > 2^21, anders kun de laatste bits niet opslaan. om die 8,3% te besparen moet je dan nog best wat code schrijven.

Je hebt gelijk, zat in de verkeerde kolom te tellen op mijn kladblaadje... 22 bits.

[basvd]

Thanks voor jullie reacties. Ik begrijp dat 22 bits het maximale is. Iets waar ik opzich al blij mee ben.

@Voutloos: Als op 22 bits de feitelijke limiet is, dan 'is dat maar zo' En dus moet ik dat maar aannemen.

@DrClaw: Dat was inderdaad ook waar ik zelf aan dacht. Maar zoals Voutloos zei 'dit is niet mogelijk met alle soorten combinaties'

@Terror: Nee ik kan niks uitsluiten. De totstandkoming, zie hieronder.

@leuk_he: Ik heb nog niet inhoudelijk getest oid. Maar is dit de wiskundige oplossing om een 150^3 mogelijkheid te converteren naar de mogelijkheid in 2^22?

Korte toelichting over het proces:
- Reeks van waardes wordt ingelezen op een device(3*1-150) op basis van een laser. De waardes(coördinaten) van deze laser zijn volledig willekeurig voor mij.
- Device moet deze getallen opslaan. Voor later gebruik. Ik mag slechts een aantal bytes gebruiken. Vraag mij niet waarom maar dat staat zo in de documentatie.
- Dit device is weer gekoppeld aan soort PLC-achtig apparaat. Als deze PLC vraagt om data, moet ik binnen no-time willekeurige waardes weer versturen.
- Om de hele set met data te comprimeren is ook een optie, maar er zitten nog meer haken en ogen aan waardoor dat weer niet mogelijk is.
- Klinkt misschien wazig. Maar ik heb eigenlijk totaal geen invloed op de apparatuur. Alleen op de software.

Wat mij de snelste oplossing lijkt is een datamap (á 4.000.000 mogelijkheden) in het geheugen te laden om daarmee te vergelijken? Met uiteraard een aantal indexes.

[MrBucket]

Om hoeveel triples hebben we het hier eigenlijk? 100? 10 000? Een miljoen?

[Matis]

MrBucket schreef op zaterdag 20 juni 2009 @ 12:09:
Om hoeveel triples hebben we het hier eigenlijk? 100? 10 000? Een miljoen?

Dat staat er toch boven. Er zijn 4 miljoen verschillende coördinaten mogelijk.
Als je die met indexen wilt gaan opvangen heb je 32 bits nodig... Lijkt me niet efficienter dan 151^3 = 3 442 951 mogelijkheden.

Misschien kun je een verdeling maken met welke mogelijkheden het vaakst voorkomen. Ik kan me voorstellen dat de *laser* vaker door het middelpunt gaat dan door de maximale resolutie (puur een aanname).

In dat geval zul je 75 een hoger gewicht/lager getal kunnen geven...

@basvd; Dit betekend dus dat je met je datamap; 4 miljoen indexes hebt met daarachter nog een keer die 3 coëfficiënten. (x-y-z). Je zult in dat geval 1 malig alle gegevens moeten invoeren en die als een soort LUT moeten verzenden. Maar dan moet je alsnog 32 bytes versturen (het adres). De ontvanger hoeft dan alleen niet meer te rekeken, alleen maar in de LUT de bijbehorende x-y-z coördinaten op te zoeken.

[ Voor 23% gewijzigd door Matis op 20-06-2009 12:21 ]

[MrBucket]

Matis schreef op zaterdag 20 juni 2009 @ 12:19:
[...]


Dat staat er toch boven. Er zijn 4 miljoen verschillende coördinaten mogelijk.

Nee, niet hoeveel triples zijn er mogelijk, hoeveel moet je er gaan opslaan op dat beperkte opslagmedium waarbij elke byte telt.

Kijk, als je maximaal 15 triples moet opslaan, dan kunnen we het hier wel hebben over lookup tables en gzip encoding, maar dat zal je dan weinig helpen...

[ Voor 18% gewijzigd door MrBucket op 20-06-2009 12:30 ]

[Zoijar]

Matis schreef op zaterdag 20 juni 2009 @ 12:19:
Misschien kun je een verdeling maken met welke mogelijkheden het vaakst voorkomen. Ik kan me voorstellen dat de *laser* vaker door het middelpunt gaat dan door de maximale resolutie (puur een aanname).

In dat geval zul je 75 een hoger gewicht/lager getal kunnen geven...

Dat is in principe huffman coding.

Let er met het oog op grote look-up tables ook op dat een random geheugen read meestal heel duur is. Een cache miss (weet niet waar je op werkt) is een van de duurste 'operaties' in een computer. Ook worden er meestal sowieso minimaal 32bits gelezen, of je nou een of vier bytes leest.

[farlane]

basvd schreef op zaterdag 20 juni 2009 @ 11:44:
Korte toelichting over het proces: ...

Wat zijn je specs? Volgens mij is het verhaal vrij simpel;

De snelheid van de laserdata * 3 bytes / Beschikbare opslagcapaciteit = maximale tijd die je kunt loggen.

Voldoet dit niet aan de specs dan moet zul je meer opslagcapaciteit moeten regelen, of de specs aanpassen.

[leuk_he]

basvd schreef op zaterdag 20 juni 2009 @ 11:44:
@leuk_he: Ik heb nog niet inhoudelijk getest oid. Maar is dit de wiskundige oplossing om een 150^3 mogelijkheid te converteren naar de mogelijkheid in 2^22?

Ja. die van drclaw komt het hetzlefde neer.

Wat mij de snelste oplossing lijkt is een datamap (á 4.000.000 mogelijkheden) in het geheugen te laden om daarmee te vergelijken? Met uiteraard een aantal indexes.

indexes? tellers...

Je praat weer in een andere taal... Je hebt een reeks getallen toch? Heb je genoeg geheugen voor 3bytesx 4 miljoen datapunten? heb je die 8% extra nodig..als je die 8% extra geheugenhebt ga je ertijd in steken, zoniet zul je ergens anders geheugenvanaan moeten peuteren...

[Henk007]

Wat is de eis aan de resolutie?
Is het acceptabel om de waarden [0..150] te scalen naar [0..127] en op die manier uit te komen met 3*7=21 bits per triple?
Op die manier prop je 3 triples in 8 bytes.
De afrondfout die je hierdoor introduceert is maximaal 0.7% van full scale (1/150), misschien wel lager dan de meetfout.

[ Voor 3% gewijzigd door Henk007 op 20-06-2009 14:01 ]

[Voutloos]

Henk007 schreef op zaterdag 20 juni 2009 @ 13:53:
De afrondfout die je hierdoor introduceert is maximaal 0.7% van full scale (1/150), misschien wel lager dan de meetfout.

1- Dat is toch een behoorlijke extra fout voor alsnog een marginale besparing qua opslag.
2- Dat er een meetfout is, is nog geen reden om die foutmarge te vergroten.

Maar goed, het zijn allemaal trade-offs, met beperkte winst, dus het is aan de TS om daar meer over te zeggen.

[ Voor 12% gewijzigd door Voutloos op 20-06-2009 14:07 ]

[Verwijderd]

theorie:

je hebt 3 getallen (0-149), laten we zeggen 12,63 en 137

we zetten het om naar base 150:

12*150² + 63*150¹ + 137*150⁰ = 279 587₁₀ <-- dit getal sla je op

het hoogste getal dat je kan hebben is: 150³-1, en dat is 3 374 999
dat past in 22 bits (4194304 > 3374999)
dan heb je dus een efficiëntie van ₂log(3374999)/22=98.5%

als je het "gewoon in 8 bits propt" kom je uit op een efficiëntie van 90.5%

verder kan je de efficiëntie (dus het aantal bits dat daadwerkelijk word gebruikt om data op te slaan) verbeteren door meer getallen tegelijk om te zetten, met 4 tegelijk kom je bijvoorbeeld uit op ₂log(150^4)/29 = 99.7%

dit kan je goed combineren met, bijvoorbeeld, lz77, maar dat werkt slecht met willekeurige getallen... (tilemaps van een 2d spel daartegen )

[ACM]

basvd schreef op zaterdag 20 juni 2009 @ 11:44:
- Reeks van waardes wordt ingelezen op een device(3*1-150) op basis van een laser. De waardes(coördinaten) van deze laser zijn volledig willekeurig voor mij.

Weet je zeker dat het echt volstrekt willekeurig is? Bij meetwaarden lijkt me dat het doorgaans niet zo zou moeten zijn. Als je bijvoorbeeld een normaalverdeling rond 75 hebt met standaarddeviatie van 15, dan weet je dat je drie getallen in 85% (95%^3) van de gevallen alledrie binnen de 45 t/m 105 (+/- 2x stddev) liggen. In zo'n geval kan het nuttig zijn om een alternatieve codering te hanteren, waarbij je 1 bit opoffert om de gebruikte codering aan te geven met de gedachte dat die opoffering je met meerdere getallen uiteindelijk winst oplevert.
In dit geval zou je dus kunnen switchen tussen een variant met maar 60^3 waarden (wat in 18 bits past) en een met de originele 150^3 waarden. En dus switch je dan uiteindelijk tussen 19 en 23 bits, met een gemiddelde van 19,6 bits per triple.

Een alternatief is natuurlijk als de drie waarden normaliter dicht bij elkaar liggen. Dan kan je een vergelijkbare truc gebruiken waarbij je eerst de eerste waarde volledig neerzet, en daarna de verschillen tov die 1e met al dan niet een verkorte codering.

Wat mij de snelste oplossing lijkt is een datamap (á 4.000.000 mogelijkheden) in het geheugen te laden om daarmee te vergelijken? Met uiteraard een aantal indexes.

't Snelste lijkt me gewoon drie normale bytes achter elkaar verzenden, zonder speciale codering... Bij elke compressie-variant moet je of een lookup-table gebruiken, of een serie bijzondere berekeningen doen.

[DrClaw]

die tupels van 3, moeten die ook in sequence weer uit je black box device komen? of laat je je laser gewoon X keer schieten, en wil je uiteindelijk iets statistisch met die X gegevens doen?

als het dat laatste is, dan zou je kunnen overwegen om je ruimte (die cube van 150^3) op te delen in 27 kwadranten van 64^3 of beter 64 quadranten van 32^3 adhv een binary partition tree oid. dan kun je de individuele kwadranten eventueel beter comprimeren, ten eerste omdat de bits efficienter worden gebruikt, en bv in het geval van die 32^3 cubes kun je je coords weer in 2 bytes kwijt. aan het begin van je block zet je dan het aantal coords in dat block, plus een dump van al die coords, en dan weer het aantal coords in block #2, en de bijbehorende dump ..

[PiepPiep]

De compressie die door zip en rar en soortgelijken gebruikt wordt is LZW.
Wikipedia: Lempel-Ziv-Welch

Misschien kan het ook interessant zijn om een stuk simpel op te slaan door gewoon 3 bytes te gebruiken voor elke meetwaarde en als je dan een bepaalde grootte gelogt hebt dat blok comprimeren met LZW en in een ander stuk geheugen plaatsen en dit process herhalen.

Ik vraag me trouwens af of je wel genoeg CPU-tijd over hebt om de compressie te doen in een systeem waar je misschien in geheugen nood komt als je deze data niet uncompressed in het geheugen kan plaatsen.

[Janoz]

PiepPiep schreef op maandag 22 juni 2009 @ 10:04:
..verhaal over LZW...

Eerder in het topic is al naar voren gekomen dat compressie niet zomaar werkt en dat standaard compressie algoritmen geen winst op gaan leveren. Zolang er niks bekend is over de entropie van de data zul je het nooit kleiner krijgen dan 22 bits.

[KabouterSuper]

Ik ga mee met het voorstel van Darkstone. Je kunt het zo in 22 bits opslaan....beter dan dit wordt het niet.

[basvd]

Zo dan...., dit topic maar weer eens goed doorgelezen.
Bedankt voor alle antwoorden, opmerkingen en suggesties.

@Matis: Zoals je al zei; een lookup table met daarin alle mogelijke waardes. De verzendende kant stuurt dus 22 bits over. De ontvangende kant heeft een soortgelijke lookup table, en gaat kijken welke 3 bytes er matchen met de 22 bits.

@Zoijar: Cache geheugen is in dit geval niet van toepassing. Nou ja, het programma mag maximaal xx mb zijn. Voorlopig kom ik daar in ieder geval nog niet aan.

@Henk007: Het verkleinen/scalen van data of meetpunten mag in dit geval niet.

@darkstone: Dit was me al enigzins duidelijk. Maar alsnog bedankt voor je voorbeeld.

@ACM: volgens de documentatie is er geen 0-waarde, beginpunt, standaardwaarde. Dus ik moet in zekere zin wel uitgaan van willekeurige getallen. Als ik na 10000 iteraties de data uit ga lezen zie ik verder ook geen logica/verband tussen de verschillende waardes/combinaties. Op een hele minimale afwijking ná zie ik elk getal even vaak terugkomen.

@PiepPiep: Als aanvulling op mijn opmerking naar @Zoijar, CPU-cycles & CPU-time zijn ook niet van toepassing.

Voor alle duidelijkheid; ik heb dus gekozen voor zgn. lookup/datamap tables.

Thanks allemaal!

[DrClaw]

Ik denk nog steeds dat je met de methode, die ik probeerde over te brengen, iets meer dan 15 bits nodig hebt, voor grote aantallen van 3-tupels. mits je dan maar teruggaat naar meerdere subspaces van 32 bij 32 bij 32 (en wel 125 stuks)

het voordeel .. neemt weigin ruimte in beslag.
het nadeel .. je verliest de volgorde van gecreeerde 3-tupels, omdat je ze opslaat per subspace .. en je zult een flinke intermediate memory space nodig hebben.

als voorbeeldje .. (87, 31, 115) komt dan terecht in subspace (2, 0, 3) = 3 * 5^0 + 0 * 5^1 + 2 * 5^2 = 53

in die subspace is de coordinaat (23, 31, 19), herschreven als 5bits .. 10111 11111 10011

laat zeggen dat je een halfword of een word aan het aantal in een subspace opslaat .. dan zijn de kosten voor een subspace:

2 bytes ( max 65536 entries in de subspace, of 4 bytes en dan zijn het er 16 miljoen), plus
N * 15 bits


stel het totaal aantal tupels dat je wilt opslaan is 100 000 .. dan zittern er gemiddeld 800 tupels in een subspace.

het aantal bits is dan 125 * ( 16 + 800 * 15 ) = 125 * 12016 = 1502000 bits

als je 22 bits per tupel zou gebruiken, dan kost het je 2 200 000 bits. ik zou zeggen, ik win. tenzij ik ergens een rekenfout of een denkfout heb gemaakt, wat vast zo is.

en ja, het is dus een inefficient algoritme als het gaat om hele kleine aantallen tupels, en het kan dus ook momenteel niet overweg met subspaces groter dan 64k of 16m respectievelijk .. maar mocht dat nodig zijn, dan kun je zelfs 7 bits voor elke subspace plempen om een index op te slaan van desbetreffende index en dan meerdere subspaces opslaan ipv alleen maar 125 stuks ... en je kunt zelfs die index achterwege laten en gewoon controleren of je een volle subspace_x opslaat, en zo ja, dan komt er nog een achteraan voor desbetreffende index x (die size=0 kan zijn), en zo nee, dan komt daar de volgende subspace_(x+1)

[ Voor 19% gewijzigd door DrClaw op 22-06-2009 22:30 ]

[Voutloos]

Volgorde doet er bij de meeste experimenten wel toe.

[DrClaw]

dus niet, want uit een flink aantal voorgaande posts zat iedereen over statistieken te praten. en dan maakt volgorde toch echt niet uit.

[Voutloos]

Ook als volgorde relevant is kan je wel de meeste statistieken gebruiken hoor.

Go figure: In een bestand is volgorde relevant, en compressie is juist gebaseerd op een statistiek, zoals meest voorkomende patronen.

[DrClaw]

tja, hoe dan ook, ik kom uit op net iets meer dan 15 bits per tupel. en het rijtje gegooide pijltjes wat eruitkomt is hetzelfde als wat erin gaat, op volgorde na. nou is het aan TS om te bepalen of het uitmaakt of niet. niet dat hij dat gaat doen, want hij kiest voor lookup tables ??

tja, misschien neemt zn laser wel een snapshot van een ruimte vol met muggen. boeit het of mug 1 op plek A zit en mug 2 op plek B ? ik zou zeggen, nee.

ik begrijp ook jouw punt; met mijn algoritme verlies je inderdaad wat: de volgorde. dat kan inderdaad belangrijk zijn. maar niet altijd. jij nam aan van wel, ik nam aan van niet. je moet toch ergens op bezuinigen?

[ Voor 51% gewijzigd door DrClaw op 22-06-2009 22:42 ]

[Voutloos]

Ik neem het aan ja:

basvd schreef op vrijdag 19 juni 2009 @ 20:17:
De volgorde moet hetzelfde blijven

[DrClaw]

ok ok ik geef me al gewonnen

maar toch .. die regel die je aanhaalde was een antwoord op een vraag van iemand die daar direct in zijn vraag een voorbeeld gaf waar hij de volgorde van de velden in het tupel verwisselde. zo zie je maar .. volgorde is ook daar niet eenduidig gebruikt

[Verwijderd]

Ik weet niet of je op bit niveau kan werken. Maar voor 1 getal heb je maar 15 bits nodig: 1e cijfer 1 bit, 2e cijfer 5 bits en 3e cijfer 9 bits. Dit maal 3 en je hebt 45 bits < 6 bytes.

[DrClaw]

?

je bedoelt .. voor het getal '140' heb je 1 bit (voor het honderdtal) .. en 5 bits (voor het 10tal) .. en 9 bits ( voor .. de 512 mogelijke 1tallen) ?

[Confusion]

Verwijderd schreef op maandag 22 juni 2009 @ 23:45:
Ik weet niet of je op bit niveau kan werken. Maar voor 1 getal heb je maar 15 bits nodig: 1e cijfer

Hij gebruikte sowieso maar 8 bits per getal en heeft dat nu tot 7.3 gereduceerd. Wat is de toegevoegde waarde van jouw methode?

[Verwijderd]

@DrClaw: Ja, dat bedoel ik: 1 bit voor de hondertallen, 5 bits voor de tientallen en 9 bits voor het derde cijfer. Het was toch een range van 0-150 als ik mij niet vergis.

@Confusion: Vergeet het maar, ik heb niks gezegd. Ik volg het topic al sinds het begin en toch lees ik nog verkeerd.

[DataGhost]

Verwijderd schreef op dinsdag 23 juni 2009 @ 08:23:
@DrClaw: Ja, dat bedoel ik: 1 bit voor de hondertallen, 5 bits voor de tientallen en 9 bits voor het derde cijfer. Het was toch een range van 0-150 als ik mij niet vergis.

Wikipedia: Binair
Neem als voorbeeld de '9 bits voor het derde cijfer'

Decimaal	Gonazair	Binair
0	000000000	0000
1	000000001	0001
2	000000010	0010
3	000000100	0011
4	000001000	0100
5	000010000	0101
6	000100000	0110
7	001000000	0111
8	010000000	1000
9	100000000	1001
10	00001000000000	1010
100	100000000000000	1100100
150	110000000000000	10010110

Ik snap eigenlijk niet hoe je op dit idee gekomen bent. Wat je nu doet is een heleboel bitjes weggooien want je zou combinaties kunnen gebruiken.

Neem nu als voorbeeld 3 in jouw stelsel. Als je combinaties gebruik kan je een 3 opslaan als ....11, dat is namelijk 1+2. Je hoeft 3 nu niet meer op te slaan als ....100, dus pak je het volgende cijfer om een bit te besparen. Nu schrijf je 4 als ....100. 5, 6 en 7 kan je nu opslaan als 4+1, +2 of +3, nog steeds in die 3 bits. Je hebt nu ook geen 5, 6 en 7 meer nodig dus het volgende getal wat je gebruikt wordt een 8, die schrijf je als ....1000. 9, 10, 11, 12, ... oh wacht, dit lijkt op hoe binair werkt, niet?

Anyway, om nu 150 op te slaan volgens jouw methode met combinaties (ook wel bekend als Binary Coded Decimal, hetzij met 'compressie') heb je 1 bit nodig voor de honderdtallen, 3 bits voor de tientallen en 4 bits voor de eenheden, in totaal 8 bits dus, dus nog niet beter dan wat de TS nu heeft. Als je puur binair gebruikt kan je in deze 8 bits bijna 2 keer zoveel opslaan. Je kan echter geen 150 opslaan in 7 bits.

[Verwijderd]

Met BCD's was ik vertrouwd en achteraf gezien lijken ze er wel op. Maar ik ging de mist in gisterenavond (combinatie van examens & te laat op de avond).
@basvd: Je koos voor lookup/datamap tables, heb je nu geheugen genoeg of kom je nog te kort?

[PaulZ]

Ik lees dit nu al een paar dagen mee, maar mag ik ook een gokje wagen? Ben wel niet wiskundig onderlegd, maar ben voor de simpele oplossingen en tot nu toe kom ik niet lager of hoger dan 20 bits (3x dec->hex->3x plakken=dec->bin). Kan je daar wat mee?

* laat dan maar weer*

[ Voor 8% gewijzigd door PaulZ op 23-06-2009 09:59 ]

[Voutloos]

Je kletst. Een aantal mensen gaat hier weer klassiek de fout in met het stunten met getalstelsels.