DIG Digital Corner
Alles wat je altijd al over computers, hardware, software, internet en elektronische gadgets had willen weten, maar niet op Tweakers.net durft te vragen.
Daar ga ik een keer naar kijken. Bedankt!
Op zich heb ik wel veel geleerd van vectors ondertussen (ook de beperkingen ervan), dus ik zie het niet als verspilde tijd.
Mijn doel is gewoon om een beetje handig met C++ te worden, totdat ik genoeg vertrouwen in mezelf heb om een wat groter project te starten. Uiteindelijk wil ik een app maken die de kortste route tussen een paar punten vindt, daar een plaatje van maakt, en dat alles in een mooie GUI die ik gemaakt heb met Qt. Dat plaatje zal ook nog erg lastig worden denk ik.
Op zich heb ik wel veel geleerd van vectors ondertussen (ook de beperkingen ervan), dus ik zie het niet als verspilde tijd.
Mijn doel is gewoon om een beetje handig met C++ te worden, totdat ik genoeg vertrouwen in mezelf heb om een wat groter project te starten. Uiteindelijk wil ik een app maken die de kortste route tussen een paar punten vindt, daar een plaatje van maakt, en dat alles in een mooie GUI die ik gemaakt heb met Qt. Dat plaatje zal ook nog erg lastig worden denk ik.
Ik heb altijd een class willen maken voor grote integers.quote:Op woensdag 8 augustus 2012 22:58 schreef thenxero het volgende:
Dat is vast niet zo leerzaam als dit geklooi
Wil je mee helpen?
Heb je git?
Weet iemand hoe de overflow kan opvangen met C++?
In amd64 kan je gewoon 2 registers gebruiken op resultaat op te slaan.
Je kan het natuurlijk met een int en long int doen, maar long int hoeft niet groter te zijn dan int.
(long long ook niet)
In amd64 kan je gewoon 2 registers gebruiken op resultaat op te slaan.
Je kan het natuurlijk met een int en long int doen, maar long int hoeft niet groter te zijn dan int.
(long long ook niet)
Overflow kan je niet opvangen in C++ en is ook moeilijk te detecteren. Je enige optie is zorgen dat het niet gebeurt.quote:
Weet iemand hoe de overflow kan opvangen met C++?
In amd64 kan je gewoon 2 registers gebruiken op resultaat op te slaan.
Je kan het natuurlijk met een int en long int doen, maar long int hoeft niet groter te zijn dan int.
(long long ook niet)
"Slechts diegene mag slopen die iets beters kan bouwen."
Maar is er ook zo iets als RDX:RAX <- RAX * r/m64?quote:
[..]
Overflow kan je niet opvangen in C++ en is ook moeilijk te detecteren. Je enige optie is zorgen dat het niet gebeurt.
Dat is natuurlijk heel erg processor-afhankelijk, dus het lijkt me sterk dat zoiets native in een taal als C++ zit. Als je een echt efficiënte library voor grote getallen wilt maken, zul je sowieso veel assembly code erbij moeten doen.quote:
[..]
Maar is er ook zo iets als RDX:RAX <- RAX * r/m64?
Wat als je vectoren niet even lang zijn?quote:while(!(k==a.rend()) && !(l==b.rend()))
Kan k==b.rend() uberhaupt op dit punt?quote:if(*k>9 && !(k==b.rend()))
Cute, maar nu lopen je iterators niet gelijk en dus..?quote:*(++k)++;
b?quote:b.insert(b.begin(),1);
Ook is t waar dat dit de iterator invalideert, maar is dat erg in deze toepassing? Afhankelijk van je while conditie wel (in de huidige ook), maar bedenk i.h.a. ook dat insert weer een (valide) iterator teruggeeft.
More oneness, less categories
Open hearts, no strategies
Decisions based upon faith and not fear
People who live right now and right here
Open hearts, no strategies
Decisions based upon faith and not fear
People who live right now and right here
Ja dacht ik al. Nouja kan wel inline asm gebruiken.quote:
[..]
Dat is natuurlijk heel erg processor-afhankelijk, dus het lijkt me sterk dat zoiets native in een taal als C++ zit. Als je een echt efficiënte library voor grote getallen wilt maken, zul je sowieso veel assembly code erbij moeten doen.
Alleen als een gewone int al 64-bits is. Het is een beetje vreemd dat je richting intrinsics/assembler gaat omdat je rekening wilt houden met zo'n (currently) outlandish mogelijkheid.quote:
Weet iemand hoe de overflow kan opvangen met C++?
In amd64 kan je gewoon 2 registers gebruiken op resultaat op te slaan.
Je kan het natuurlijk met een int en long int doen, maar long int hoeft niet groter te zijn dan int.
(long long ook niet)
More oneness, less categories
Open hearts, no strategies
Decisions based upon faith and not fear
People who live right now and right here
Open hearts, no strategies
Decisions based upon faith and not fear
People who live right now and right here
Ik zou de vector::resize method gebruiken om de vectoren groot genoeg te maken. Dat scheelt je weer wat if statements waardoor je code eenvoudiger wordt en je minder snel bugs krijgt.quote:
Een nieuwe poging vectors bij elkaar op te tellen alsof het getallen zijn. Dus bijvoorbeeld, als
a = {9, 8, 6, 4}
b = {9, 6, 7}
Dan wil ik dat de functie add(a,b) ervoor zorgt dat b = {1, 0, 8, 3, 1}. De functie moet in ieder geval werken voor vectors b die minstens even lang zijn als a. De moeilijkheid zit hem in de verschillende lengtes van de vector. Volgens mij is dit de beste methode om daarmee om te gaan, alleen krijg ik nog wat errors waar ik geen touw aan vast kan knopen.
Ik kan natuurlijk ook gewoon u_int64, u_int32 gebruiken etc.quote:Op donderdag 9 augustus 2012 20:10 schreef trancethrust het volgende:
[..]
Alleen als een gewone int al 64-bits is. Het is een beetje vreemd dat je richting intrinsics/assembler gaat omdat je rekening wilt houden met zo'n (currently) outlandish mogelijkheid.
Maar met asm kan ik 128 bit als opslag gebruiken...
Net even gechecked en int is 32bit, long en long long zijn 64bit.quote:
[..]
Alleen als een gewone int al 64-bits is. Het is een beetje vreemd dat je richting intrinsics/assembler gaat omdat je rekening wilt houden met zo'n (currently) outlandish mogelijkheid.
size_t is ook 64bit.
Dat hangt helemaal van je architectuur af. Zou je dit soort dingen ook echt aannemen in je code, dan kunnen andere mensen het dus niet gebruiken.quote:
[..]
Net even gechecked en int is 32bit, long en long long zijn 64bit.
size_t is ook 64bit.
Klinkt wel leuk, maar ik weet niet of je veel aan me hebtquote:
[..]
Ik heb altijd een class willen maken voor grote integers.
Wil je mee helpen?
Heb je git?
Ja daar zit het probleem dus...quote:
[..]
Dat hangt helemaal van je architectuur af. Zou je dit soort dingen ook echt aannemen in je code, dan kunnen andere mensen het dus niet gebruiken.
Het punt is dat assembler ook compleet van je architectuur afhangt; dat is als zodanig ook niet echt een oplossing.quote:
[..]
Ja daar zit het probleem dus...
Ook is een truc om toch maar 128-bits precisie te gebruiken voor detectie eigenlijk uitstel van executie; wat als je dan toch ook maar met 128-bits waarden wilt gaan werken, als het toch kan? Je blijft bezig.
Ik zou dan ook per applicatie bekijken of overflows daadwerkelijk problemen geven; als je enige operatie een telkens 1 optellen is, dan is een i == static_cast< unsigned int >( -1 ) genoeg om overflow te detecteren. Als het twee ints optellen is, dan hoef je alleen iets speciaals te doen als een van de getallen de 32e meest significante bit heeft gezet. Als je RNGs aan het maken bent en je hebt elk stukje performance nodig, dan kijk je naar Schrage's truc; enzovoorts.
More oneness, less categories
Open hearts, no strategies
Decisions based upon faith and not fear
People who live right now and right here
Open hearts, no strategies
Decisions based upon faith and not fear
People who live right now and right here
edit:
Het werkt
Het werkt
| 1 2 3 4 5 | uint64_t x, y; unsigned __int128 z; x = y = 0xffffffffffffffff; z = static_cast<unsigned __int128>(x) * y; |
Sure, maar het is niet ANSI en het blijft uitstel van executie in de zin van hierboven.
More oneness, less categories
Open hearts, no strategies
Decisions based upon faith and not fear
People who live right now and right here
Open hearts, no strategies
Decisions based upon faith and not fear
People who live right now and right here
Ja ik weet dat het geen ISO is.quote:Op vrijdag 10 augustus 2012 19:41 schreef trancethrust het volgende:
Sure, maar het is niet ANSI en het blijft uitstel van executie in de zin van hierboven.
Dus dan moet ik maar uint32_t en uint64_t gebruiken.
En dan met ifdef gaan werken.
Of is er een andere mogelijk om de grootste integer te krijgen en een integer die 2 keer zo klein is.
Voor mijn arbitrary precision integer implementatie heb ik een willekeurig unsigned integer-datatype genomen en daar alleen de onderste helft van de bits van gebruikt. Dat betekent dat de gebruiker vrij is de snelste int voor zijn compiler/platform te gebruiken en dat het automatisch meegroeit als de ints ook groter worden.quote:
Of is er een andere mogelijk om de grootste integer te krijgen en een integer die 2 keer zo klein is.
Het is zonde om je zo vast te zetten op een bepaalde grootte int.
"Slechts diegene mag slopen die iets beters kan bouwen."
Ja ik wil ook niet vast zitten op een bepaalde grootte.quote:
[..]
Voor mijn arbitrary precision integer implementatie heb ik een willekeurig unsigned integer-datatype genomen en daar alleen de onderste helft van de bits van gebruikt. Dat betekent dat de gebruiker vrij is de snelste int voor zijn compiler/platform te gebruiken en dat het automatisch meegroeit als de ints ook groter worden.
Het is zonde om je zo vast te zetten op een bepaalde grootte int.
Jij zegt zelf dat je een willekeurige gebruikt, maar hoe weet je dat je dat onderste helft van de bits gebruikt?
Dat werkt, maar dan moet je dus wel voor een nieuw type een nieuwe template-specificatie maken etc.quote:
De onderste helft is sizeof(Type) * 4 bits en de maximale waarde is dus 2^(sizeof(Type) * 4). Zolang je daaronder zit, zit je veilig. Als je daar overheen gaat (of het raakt), schuif je de overflow naar het volgende getal.quote:Jij zegt zelf dat je een willekeurige gebruikt, maar hoe weet je dat je dat onderste helft van de bits gebruikt?
"Slechts diegene mag slopen die iets beters kan bouwen."
Heb net PE probleem 67 opgelost, met die triangle met 100 rijen aan getallen, waar je de maximale som moet berekenen van boven naar beneden. Binnen 40ms is mijn algoritme klaar .
.
Hoe gebruik je eigenlijk een non-standard library? Ik probeer deze nu te gebruiken, maar het lukt me niet eens om het te laden. Op google en in de manual kom ik alleen maar dingen tegen die ik niet snap of die ik niet wil.quote:
Voor grote getallen zijn er libraries zoals MPIR.
Ik heb nu de library gedownload... en dan twee keer iets uitgepakt. Nu heb ik dus een hele berg aan bestandjes, waarvan ik geen idee heb wat ik er precies mee moet doen.
Op wat voor systeem zit je? Als je op Linux zit, dan zit zulke software wel in software manager (zoek bijvoorbeeld op GMP, de The GNU Multiple Precision Arithmetic Library; verreweg de snelste). Dan wordt alles goed voor je geinstalleerd.quote:
Hoe gebruik je eigenlijk een non-standard library? Ik probeer deze nu te gebruiken, maar het lukt me niet eens om het te laden. Op google en in de manual kom ik alleen maar dingen tegen die ik niet snap of die ik niet wil.
Ik heb nu de library gedownload... en dan twee keer iets uitgepakt. Nu heb ik dus een hele berg aan bestandjes, waarvan ik geen idee heb wat ik er precies mee moet doen.
Als je op Windows zit, is het installeren van zulke software meestal veel lastiger omdat je het veelal zelf moet compileren en installeren. Als je wilt, kan je ook mijn eigen verzameling van klassen proberen voor rekenen met grote getallen. Die is bijna klaar voor algemeen gebruik en hoeft niet geinstalleerd te worden.
"Slechts diegene mag slopen die iets beters kan bouwen."
Ja, maar die instructies kan ik niet volgen. Het is net alsof je ergens commando's moet invoeren, zoals:quote:
Ga eerst op zoek naar een file genaamd README of INSTALL of iets dergelijks, en lees die.
| 1 2 3 | ./configure make make check |
Leuk dit soort codetaal maar dit zegt me niksquote:Op zaterdag 11 augustus 2012 22:49 schreef t4rt4rus het volgende:
Aptitude install libgpm-dev
En succes
Laat me raden: je hebt Windows?quote:
[..]
Ja, maar die instructies kan ik niet volgen. Het is net alsof je ergens commando's moet invoeren, zoals:
[ code verwijderd ]
Maar hoe en waar is me een raadsel.
Op
Maar in een andere post zei je dat je gcc had. Hoe doe je dat dan met Windows?
Misschien zeg ik iets heel doms nu, ik ben een absolute Windows-n00b.
Misschien zeg ik iets heel doms nu, ik ben een absolute Windows-n00b.
Bijvoorbeeld met MinGW of Cygwin, allebei een port van GCC naar Windows.quote:
Maar in een andere post zei je dat je gcc had. Hoe doe je dat dan met Windows?
Misschien zeg ik iets heel doms nu, ik ben een absolute Windows-n00b.
"Slechts diegene mag slopen die iets beters kan bouwen."
GNU GCC is de compiler die ik standaard krijg in code::blocks. Ik heb daar niks speciaals voor gedaanquote:
Maar in een andere post zei je dat je gcc had. Hoe doe je dat dan met Windows?
Misschien zeg ik iets heel doms nu, ik ben een absolute Windows-n00b.
MinGW ken ik niet, wel Cygwin. Cygwin heeft bij mijn weten geen 64-bits-ondersteuning. Heeft MinGW dat wel?quote:
[..]
Bijvoorbeeld met MinGW of Cygwin, allebei een port van GCC naar Windows.
Volgens mij zijn er experimentele ports van de 64-bits compiler, maar het is niet gemakkelijk aan de praat te krijgen en je wordt er niet gelukkig van. Verder is het wel een mooi systeem en installeert het nu al standaard gcc4.7 (zonder std::thread though).quote:
MinGW ken ik niet, wel Cygwin. Cygwin heeft bij mijn weten geen 64-bits-ondersteuning. Heeft MinGW dat wel?
"Slechts diegene mag slopen die iets beters kan bouwen."
Maar wat heeft dit voor een consequenties voor mij?
Of is er een andere vrij eenvoudige manier om met grote getallen om te gaan? Ik moet PE probleem 13 en 20 toch ook wel zonder non-standaard libraries kunnen oplossen?
Of is er een andere vrij eenvoudige manier om met grote getallen om te gaan? Ik moet PE probleem 13 en 20 toch ook wel zonder non-standaard libraries kunnen oplossen?
In PE komen natuurlijk vaak grote getallen voor, dus het is wel handig om er libraries voor te hebben. Niet alleen om te rekenen, maar ook voor factorisatie en zo. Aan de website van MPIR te zien, ondersteunt het wel Windows. Zijn er geen voorgecompileerde versies?
Misschien ben je wel een goede testpersoon voor mijn klasses, je lijkt wel in de doelgroep te vallen.quote:
Maar wat heeft dit voor een consequenties voor mij?
Of is er een andere vrij eenvoudige manier om met grote getallen om te gaan? Ik moet PE probleem 13 en 20 toch ook wel zonder non-standaard libraries kunnen oplossen?
Als je wilt, kan je ze via http://code.google.com/p/unlimited-int/ downloaden. De code is klaar, de documentatie nog niet. Via 'downloads' kan je unlimited_int.h downloaden en dat is eigenlijk alles dat je nodig hebt. Een voorbeeldje van gebruik:
| 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 | #include <iostream> #include "unlimited_int.h" // Print all primes below 2000 very inefficiently. bool is_prime(Unlimited::Int const &n) { if (n < 2) return false; Unlimited::Int sqrt_n = n.sqrtc(); for (Unlimited::Int i = 2; i <= sqrt_n; ++i) { if (n % i == 0) return false; } return true; } int main() { for (Unlimited::Int n(1); n < 2000; ++n) { if (is_prime(n)) std::cout << "Prime: " << n << '\n'; } } |
(Compileer met -std=c++11.)
Je kunt Unlimited::Int gewoon als int gebruiken. Als je het wilt proberen en er iets onduidelijk is, moet je mij maar even vragen want de documentatie is dus nog niet af.
(Trouwens, als jullie commentaar op de broncode willen leveren, is dat natuurlijk ook gewenst. Kijk dan alleen niet in unlimited_int.h maar bekijk de code via 'Source' -> 'Browse' want van die header file word je gek.)
"Slechts diegene mag slopen die iets beters kan bouwen."
Heb het geprobeerd, maar ik krijg een overflow aan errors. Meer dan 50 wil ie niet weergevenquote:
[..]
Misschien ben je wel een goede testpersoon voor mijn klasses, je lijkt wel in de doelgroep te vallen.
Als je wilt, kan je ze via http://code.google.com/p/unlimited-int/ downloaden. De code is klaar, de documentatie nog niet. Via 'downloads' kan je unlimited_int.h downloaden en dat is eigenlijk alles dat je nodig hebt. Een voorbeeldje van gebruik:
[ code verwijderd ]
(Compileer met -std=c++11.)
Je kunt Unlimited::Int gewoon als int gebruiken. Als je het wilt proberen en er iets onduidelijk is, moet je mij maar even vragen want de documentatie is dus nog niet af.
(Trouwens, als jullie commentaar op de broncode willen leveren, is dat natuurlijk ook gewenst. Kijk dan alleen niet in unlimited_int.h maar bekijk de code via 'Source' -> 'Browse' want van die header file word je gek.)
. Ik heb gewoon jouw code van die priemgetallen geplakt, en de instructies gevolgd.Bijna alle errors hebben trouwens met elkaar gemeen dat er d_number instaat. Steeds een herhaling van dat ie niet in de scope zit, of geen member is van de class Unlimited::Uint.
Maar het kan toch niet zo moeilijk zijn, >70 000 mensen hebben die opgelost. Er zitten problemen bij die veel minder mensen hebben opgelost waar ik geen moeite mee heb.
Wat ze bij 20 doen is:quote:Op zondag 12 augustus 2012 00:20 schreef thenxero het volgende:
Maar het kan toch niet zo moeilijk zijn, >70 000 mensen hebben die opgelost. Er zitten problemen bij die veel minder mensen hebben opgelost waar ik geen moeite mee heb.
http://www.wolframalpha.com/input/?i=100!
En dan string copieren en alles optellen.
En voor dertien heb je alleen maar de eerste 13-15 cijfers nodig van alle 100 nummers.
Maar dan wel op een 64bit PC.
Op 32bit lukt dat niet echt...
Dank je wel voor het uitproberen. Ik zal zelf eens Code::Blocks installeren en kijken of ik kan vinden wat er mis gaat.quote:
[..]
Heb het geprobeerd, maar ik krijg een overflow aan errors. Meer dan 50 wil ie niet weergeven
Bijna alle errors hebben trouwens met elkaar gemeen dat er d_number instaat. Steeds een herhaling van dat ie niet in de scope zit, of geen member is van de class Unlimited::Uint.
Edit: Haha, ja, ik heb de fout gevonden: Code::Blocks levert gcc version 4.4.1.
Als je C++11 wilt gebruiken, zal je minimaal 4.6 moeten hebben. Je kunt gaan googlen op dingen als "GMP for code blocks", daarmee vind ik wat hoopvolle resultaten. Als je het aandurft, mag je mijn ding ook nog eens proberen. Omdat ik denk dat dit wel vaker voor zal komen, heb ik ook een niet-11 versie tussen de downloads gezet.Ietwat nutteloos om hier neer te zetten, niet? Het is niet alsof het antwoord gecontroleerd moet worden: je weet wanneer het goed is. Alleen om te laten zien dat je het kan? Beetje flauw.quote:
Dit is trouwens het antwoord van vraag 13
[...]
Over de OP:
Ik ben maar begonnen met een herschrijving die je hier kunt vinden. Mijn inspiratie is echter op. Als jullie nog wijzigingen/toevoegingen hebben voor de FAQ of links, ga gerust jullie gang.
[ Bericht 11% gewijzigd door GS42 op 12-08-2012 04:36:15 ]
"Slechts diegene mag slopen die iets beters kan bouwen."
Was om te laten zien hoe groot het getal word. (Het antwoord staat er niet in...)quote:
[..]
Ietwat nutteloos om hier neer te zetten, niet? Het is niet alsof het antwoord gecontroleerd moet worden: je weet wanneer het goed is. Alleen om te laten zien dat je het kan? Beetje flauw.
xero GMP gebruiken of zelf een class maken...
Je kan trouwens makkelijk een nieuwe gcc toevoegen aan code::blocks btw
Some people should be around your entire life; others should just make an appearance.
Dat is misschien het beste, misschien heb ik dat in de toekomst ook nog voor andere dingen nodig. Hoe installeer die nieuwe gcc?quote:
Je kan trouwens makkelijk een nieuwe gcc toevoegen aan code::blocks btw
Haha, wolfram alpha gebruiken is wel heel flauw. Maar dat verklaart wel waarom zoveel mensen het hebben opgelostquote:
[..]
Wat ze bij 20 doen is:
http://www.wolframalpha.com/input/?i=100!
En dan string copieren en alles optellen.
En voor dertien heb je alleen maar de eerste 13-15 cijfers nodig van alle 100 nummers.
Maar dan wel op een 64bit PC.
Op 32bit lukt dat niet echt...
