[c++] Variable met 10^8 cijfers *

[Iska]

Hey allemaal,

Ik ben al een tijdje op zoek naar een manier om een getal op te slaan dat 100.000.000 losse getallen bevat (denk aan pi met 100.000.000 decimalen). Nu had ik hiervoor PHP gebruikt want die kon met strings rekenen, maar dat ging langzaam als de nete (rekenen met meer dan >10 getallen ging al 4x langzamer dan normaal)! Dus eigenlijk hoopte ik dat jullie een goede oplossing hadden.
Voor de duidelijkheid: het moet dus een variable worden met minstens 3.321928097*10^8 bits (afgerond 40MB).

Jasper

[H!GHGuY]

Er zijn talen met support voor wat een big integer heet.
Zoek maar even op google naar BigInt.

edit:
vermoedelijk is dit ook wat PHP doet.
Een CPU kan gewoon geen berekeningen doen op types groter dan X bits (met X meestal 80 voor double of 64 voor long long). Om hier omheen te werken heb je een externe lib nodig die de bewerking op je groot getal in meerdere stappen oplost. Gevolg: een stuk trager dan gewoon berekenen.

[ Voor 63% gewijzigd door H!GHGuY op 28-01-2009 19:08 ]

[NMe]

Er zijn wat BigInt oplossingen/classes te vinden, maar voor zover ik weet maken die allemaal intern ook gebruik van strings met de daarbij horende traagheid. Ik heb verder nooit met zo'n grote getallen hoeven werken dus ervaring heb ik er niet echt mee, maar je zou ernaar kunnen kijken. Het zal ongetwijfeld sneller kunnen dan wat PHP je kan leveren.

[ Voor 6% gewijzigd door NMe op 28-01-2009 19:07 ]

[Onbekend]

Wat wil je met dat getal doen? Berekeningen maken? Moet het nauwkeurig zijn (geen floating point)?

[Sebazzz]

Ik heb een keer Powercalc (Powertoy van Microsoft) Googol * pi uit laten rekenen (10¹⁰⁰) laten uitrekenen en toen liep me computer vast. Het zal inderdaad allemaal met string werken.

Waarvoor heb je zoiets groots nodig? (bezig met Fibonacci? )

[RobIII]

^^ Wat de rest zegt. Wat ben je aan 't doen waarvoor je een dusdanig achterlijk groot getal voor nodig hebt? Vaak zitten oplossingen voor wat jij zoekt namelijk in een hele andere hoek dan 'simpelweg' met zo'n 'getal' rekenen. En waarom staat er C++ in je titel

[ Voor 7% gewijzigd door RobIII op 28-01-2009 19:14 ]

[NMe]

Onbekend schreef op woensdag 28 januari 2009 @ 19:08:
Wat wil je met dat getal doen? Berekeningen maken? Moet het nauwkeurig zijn (geen floating point)?

Floating point of niet maakt niet zo op, zolang je zelf de relatieve positie van de komma onthoudt kun je gewoon met integers (nouja, BigInts) rekenen.

[Onbekend]

Ik bedoel meer met wat RobIII al aangeeft: Wat wil je er mee bereiken en is er geen eenvoudigere weg.

Als je alleen dit soort grote getallen hebt, wil je dan wel op de eenheid nauwkeurig een uitkomst weten?
En wil een gebruiker zo'n groot getal wel intypen?

[RobIII]

Onbekend schreef op woensdag 28 januari 2009 @ 19:17:
En wil een gebruiker zo'n groot getal wel intypen?

offtopic:
Zolang ze 't daarna maar op mijn rekening storten (en de bank garandeert dat er geen overflow optreedt zodat mijn saldo negatief wordt) is dat 't minste probleem Daar hebben we tiepmiepen voor

---

.oisyn schreef op woensdag 28 januari 2009 @ 19:20:
[...]

Maak daar maar cijfers van . Een getal is een waarde. Een cijfer is onderdeel van een getal in een bepaalde representatie.

offtopic:
Ah, onze huismierenneuker is ook weer aanwezig En hij heeft (alweer) gelijk overigens

[ Voor 31% gewijzigd door RobIII op 28-01-2009 19:22 ]

[.oisyn]

Variable met 10^8 getallen

Maak daar maar cijfers van . Een getal is een waarde. Een cijfer is onderdeel van een getal in een bepaalde representatie.

Ah, onze huismierenneuker is ook weer aanwezig

Ik doe m'n best

[ Voor 19% gewijzigd door .oisyn op 28-01-2009 19:24 ]

[Iska]

Sorry dat ik nu pas reageer maar ik had niet zoveel reacties verwacht in zo'n korte tijd

Maar even samenvattend:
- Waarom zo'n groot getal: Moet een groot priemgetal uitrekenen
- Decimalen nodig: Ja, anders kan ik het niet controleren

Iig bedankt voor jullie reacties, ik ga wel ff googlen op de BinInt

[Zoijar]

Jasper91 schreef op woensdag 28 januari 2009 @ 19:37:
- Waarom zo'n groot getal: Moet een groot priemgetal uitrekenen

offtopic:
grootst bekende priem heeft ongeveer 18 miljoen digits, en jij wilt er 100 miljoen?

[Verwijderd]

offtopic:
Misschien een school-botnetwerk in elkaar gehaxored en nu op zoek naar de volgende grootste! Om zo eeuwige roem en rijkdom te vergaren!

[Onbekend]

http://www.kennislink.nl/web/show?id=106124
Het nieuwe priemgetal omvat qua omvang 63 procent van het uieindelijk doel van het Great Internet Mersenne Prime Search-project. Dat is het vinden van een priemgetal met meer dan tien miljoen cijfers. De gelukkige die daarin slaagt, ontvangt 100.000 dollar. Een voormalige deelnemer van het project ontving in 2000 al 50.000 dollar voor het vinden van het eerste priemtal met meer dan één miljoen getallen.


Misschien moet je een aangepaste versie van de zeef van Eratosthenes maken o.i.d. Het is een flink getal waarmee de controleberekeningen het zwaar mee hebben.

[Floort]

Probeer de GMP library. Ik heb de C++ bindings nog nooit gebruikt, maar de C versie werkt prima. Veel sneller is het niet te krijgen.

[Verwijderd]

Floort schreef op woensdag 28 januari 2009 @ 19:52:
Probeer de GMP library. Ik heb de C++ bindings nog nooit gebruikt, maar de C versie werkt prima. Veel sneller is het niet te krijgen.

GMP inderdaad. Linkje: http://gmplib.org/

[eamelink]

De handigste manier is om je getal om te zetten in een radix-256 representatie. Dan kan elke coëfficient namelijk opgeslagen worden in één byte en kan je n coëfficienten opslaan in een char-array van lengte n aangezien een char ook één byte groot is.

Een normaal decimal getal is radix-10. 271 betekent eigenlijk iets als 2 * 10^2 + 7 * 10^1 + 1 * 10^0, waarbij die 2, 7 en 10 coëfficienten genoemd worden.

Als je een radix-256 getal neemt, dan krijg je coëfficienten die tussen 0 en 255 liggen en die kan je dus perfect opslaan in een char. Je kan dan bijvoorbeeld een getal hebben als [17][233][191], en dat heeft dus als betekenis 17 * 256^2 + 233 * 256^1 + 191 * 256^0 (=1173951). Dat is de optimale manier om grote integers op te slaan op een computer.

Vervolgens moet je dus implementaties maken van optellen, aftrekken, vermenigvuldigen, delen, worteltrekken en wat je nog meer nodig hebt.

Optellen en aftrekken zijn simpele O(n) operaties. Vermenigvuldigen op de normale manier is een O(n^2) operatie en dat wordt dus onbruikbaar voor de getallen van het formaat waar jij mee wilt werken. Gelukkig is een vermenigvuldiging om te schrijven als een dubbele forward en een reverse fouriertransformatie en die zijn met een FFT te doen in O(n log n), waardoor je dus een vermenigvuldiging in O(n log n) kan doen.

Een deling en een wortel kan je met Newton's methode vrij snel uitrekenen.

Gelukkig hoef je dit niet meer zelf te implementeren als je een goede arbitrary precision library pakt . Die kunnen dat namelijk allemaal al

[.oisyn]

eamelink schreef op woensdag 28 januari 2009 @ 20:22:
Optellen en aftrekken zijn simpele O(n) operaties. Vermenigvuldigen op de normale manier is een O(n^2) operatie en dat wordt dus onbruikbaar voor de getallen van het formaat waar jij mee wilt werken.

Met een vrij simpele optimalisatie is een vermenigvuldiging 'maar' O(n^{2-log 3}). Als je twee getallen van twee digits vermenigvuldigd, zeg ab en cd waarbij elke letter een digit voorstelt, dan zou je dat normaal doen middels a*c*100 + (a*d+b*c)*10 + b*d. Met andere woorden, voor twee-digit getallen heb je 4 vermenigvuldigingen nodig, en dat is waar de O(n²) vandaan komt.

Echter, (a*d+b*c) kun je ook schrijven als (a+b)*(c+d) - a*d - b*d. Die laatste twee had je sowieso al nodig, dus er komt maar 1 vermenigvuldiging bij ipv 2. Wel natuurlijk extra optellingen en aftrekkingen, maar die zijn in O(n) te doen - bij getallen met heel veel digits is dit dus wel voordeliger. Dit heet trouwens Karatsuba vermenigvuldiging.

Er zijn natuurlijk ingewikkeldere algoritmen, zoals Toom-Cook of idd de FFT methode (die overigens niet O(n log n) maar O(n∙ln(n)∙ln(ln(n))) is, maar deze is dan iig nog vrij simpel te implementeren. Mijn eigen bignum lib werkt overigens met radix-4294967296. Waarom bytes gebruiken als de CPU net zo snel met dwords kan rekenen

[ Voor 2% gewijzigd door .oisyn op 28-01-2009 22:03 . Reden: euh nee niet Thomas Cook 8)7 ]

[eamelink]

Omdat radix-4294nogwattus mijn perceptie te boven gaat . In mijn perceptie is ln(ln(n)) overigens ook gewoon O(1) voor alle n Overigens ben je daar mijn kennis van daadwerkelijke hardware (*eeks*) al aardig voorbij, maar dat is vast geen overbodige luxe in jouw vakgebied

[Jaap-Jan]

Hij rekent met 32-bits getallen en niet met 8-bits zoals jij doet. Komt weinig hardwarekennis aan te pas, hoor

[ Voor 24% gewijzigd door Jaap-Jan op 28-01-2009 21:45 ]

[Soultaker]

Ik weet trouwens niet hoe je dit in PHP gedaan hebt, maar als je gewoon de GMP extensie gebruikte, dan zal je programma in C++ net zo traag zijn als in PHP. Met zulke grote getallen zit alle verwerkingstijd toch in de GMP module en die is voor C++ en PHP hetzelfde. (Uitzondering zou kunnen zijn als je tussendoor veel conversies van/naar PHP datatypen uitvoert, maar dan kun je dat probleem beter direct oplossen ipv over te stappen naar C++.)

[Soultaker]

Jaap-Jan schreef op woensdag 28 januari 2009 @ 21:45:
Hij rekent met 32-bits getallen en niet met 8-bits zoals jij doet. Komt weinig hardwarekennis aan te pas, hoor

Weet niet hoe GMP enzo dat implementeren, maar het is altijd verdomd lastig om dingen als overflow dan goed af te handelen zonder terug te vallen op assembly. (Denk aan optellingen waarbij je de overflow flag wil hebben, en vermenigvuldigingen waarbij je eigenlijk zowel de hoge als lage dword wil benaderen maar eigenlijk geen conversie naar een 64-bit integer vooraf wil doen.)

[.oisyn]

Overflow kun je gewoon detecteren zonder gebruik te maken van grotere integers hoor . Als a+b overflowt wil dat namelijk zeggen dat a+b > 2³²-1. Oftewel, dat a > 2³²-1 - b. Nou is dat natuurlijk al gewoon met 32 bits ints uit te rekenen, maar het mooie van 2's complement is weer dat 2³²-1 - b hetzelfde is als NOT b. Met andere woorden, als a > NOT b dan krijg je een overflow. Maar het kan nog veel simpeler. Gewoon a+b berekenen. Als het antwoord kleiner is dan a (of b), dan heb je een overflow gehad

Overigens gebruik ik in mijn lib wel gewoon inline assembly. Of intrinsics, weet ik niet meer precies.

[SKiLLa]

radix 2^8 vs radix 2^32. Priemgetallen schrijf je meestal toch al als exponent (b.v: 2^1398269 - 1).
Ben ook wel benieuwd naar de performance verschillen tussen een PHP:GMP en een C++GMP implementatie

En als de TS met Linux werkt kan ie eventueel ook naar de Intel Kernel Math Library for Linux 10.1 kijken.

Off-topic: Inline assembly is niet voor iedereen weggelegd, maar het blijft inderdaad leuk & leerzaam; elke X jaar nieuwe CPU instructies en dus weer nieuwe optimalisaties, tweaken, etc Voor priemgetallen kun je dan trouwens unsigned integers en het carry-bit gebruiken, nix overflow "gezeur".