[C#] BigInt

[Memorice]

Ik moet rekenen met getallen van 1000+ cijfers groot, met deze getallen wil ik het volgende kunnen:
- optellen
- vermenigvuldigen
- machtsverheffen
- vergelijken met elkaar

Nu weet ik dat er genoeg BigInt oplossingen te vinden zijn via Google. Een andere optie is bijvoorbeeld een BigInt lenen uit een taal als F# door het importen van een dll (zie ook: http://blogs.msdn.com/mpeck/archive/2009/04/01/solving-problems-in-c-and-f-part-2.aspx).

Voor mijn applicatie speelt performance een nogal belangrijke rol (ja ik weet dat c++ een betere keuze geweest zou zijn ;-)), daarom vroeg ik mij af of er een manier is om er achter te komen welke oplossing (welke BigInt klasse of alternatieve oplossing) het meest geschikt is, zonder ze allemaal zelf uit te proberen. Wellicht dat iemand hier ervaring heeft met het gebruik van BigInt classes?

[Woy]

Vanaf .NET 4 zal er een BigInteger class in het framework opgenomen zijn ( Zit er al in, maar die is niet public ) http://msdn.microsoft.com...s.biginteger(VS.100).aspx.

Verder zou je bijvoorbeeld naar Mono kunnen kijken, daar zit ook een BigInteger class in, en dat is open-source, dus je zou de code daarvan kunnen lenen. Ook op CodeProject vind ik een BigInteger implementatie: http://www.codeproject.com/KB/cs/biginteger.aspx

Ik denk dat al die implementaties aan je wensen voldoen. Als je echt tegen performance problemen aanloopt kun je altijd nog kijken hoe je de performance kunt verbeteren. Immers: "premature optimization is the root of all evil"

MEMORICE schreef op vrijdag 05 juni 2009 @ 09:37:
Voor mijn applicatie speelt performance een nogal belangrijke rol (ja ik weet dat c++ een betere keuze geweest zou zijn ;-)), daarom vroeg ik mij af of er een manier is om er achter te komen welke oplossing (welke BigInt klasse of alternatieve oplossing) het meest geschikt is, zonder ze allemaal zelf uit te proberen. Wellicht dat iemand hier ervaring heeft met het gebruik van BigInt classes?

Stellen dat je beter C++ had kunnen kiezen omdat je performance belangrijk is, is nogal kort door de bocht. Het lijkt me dat bij alle programma's de performance wel belangrijk is.

Maar het meeste winst valt er te halen door gewoon een slimme implementatie/algoritme te maken. Zie bijvoorbeeld de PRG Contest waar de winnaar ook een Java inzending is. Misschien dat je met C++ inderdaad op sommige fronten beter performance kunt halen, maar je zult merken dat een slimmer algoritme veel meer uit kan halen.

[ Voor 42% gewijzigd door Woy op 05-06-2009 09:47 ]

[HuHu]

Getallen van 1000+ cijfers groot . Weet je zeker dat je ook de complete precisie van al die cijfers wilt bewaren? Of is een notatie als 3,14156 * 10¹⁰⁵⁴ voldoende? Waarbij je dus de laatste 1000-nogwat cijfers gewoon wegkiepert omdat ze toch insignificant zijn.

[Memorice]

@Woy

Als ik het goed begrijp is de .NET 4 versie nog niet te gebruiken, ook niet door een dll reference.

Verder zou je bijvoorbeeld naar Mono kunnen kijken, daar zit ook een BigInteger class in, en dat is open-source, dus je zou de code daarvan kunnen lenen. Ook op CodeProject vind ik een BigInteger implementatie: http://www.codeproject.com/KB/cs/biginteger.aspx

Ik heb hier ook al naar gekeken, wat mij opviel was dat het geoptimaliseerd is voor cryptografie, zonder rekening te houden met memory efficiency (array met constante lengte). Gezien ik moeilijk kan zeggen hoeveel cijfers mijn bigint groot moet zijn, is dit niet optimaal. Wel kan ik iets zeggen over de worst case, maar de kans dat dit zich voordoet is dan weer zeer onwaarschijnlijk.

Kortom de enige mogelijke optie die dan overblijft is eens naar Mono kijken.

Stellen dat je beter C++ had kunnen kiezen omdat je performance belangrijk is, is nogal kort door de bocht. Het lijkt me dat bij alle programma's de performance wel belangrijk is.

In mijn post is dat idd wat kort door de bocht, maar als je de details zou kennen niet. Het gaat namelijk om code voor mijn onderzoek, dat zich richt op een heuristiek voor een NP-Complete probleem. Bottlenecks waar ik bijv. tegenaan loop is het gemis van een goed alternatief voor memcpy.

@HuHu

Ik heb de precisie in de praktijk waarschijnlijk niet nodig (theoretisch gezien wel). Dus mocht je een oplossing hebben die werkt met een slechtere precisie, dan ben ik hier ook geinteresseerd in. Ik zelf heb zitten denken aan het gebruiken van logaritmes, echter is het volgens mij niet triviaal om een getal dat log (a) representeerd om te zetten in een getal dat log (a+b) representeerd. Dit is nogal essentieel, gezien ik het getal wil updaten zeg maar ipv volledig opnieuw te berekenen.

[Woy]

MEMORICE schreef op vrijdag 05 juni 2009 @ 10:12:
@Woy

Als ik het goed begrijp is de .NET 4 versie nog niet te gebruiken, ook niet door een dll reference.

Er is alleen een beta uit ( Die met de Beta van VS.NET 2010 meekomt ).

Ik heb hier ook al naar gekeken, wat mij opviel was dat het geoptimaliseerd is voor cryptografie, zonder rekening te houden met memory efficiency (array met constante lengte). Gezien ik moeilijk kan zeggen hoeveel cijfers mijn bigint groot moet zijn, is dit niet optimaal. Wel kan ik iets zeggen over de worst case, maar de kans dat dit zich voordoet is dan weer zeer onwaarschijnlijk.

Kortom de enige mogelijke optie die dan overblijft is eens naar Mono kijken.

Maar heb je ook daadwerkelijk geconstateerd dat het een bottleneck is, dat wil zeggen door te profilen? Je gaat er nu zomaar van uit dat het een probleem oplevert, maar misschien treed de bottleneck straks wel ergens anders op.

In mijn post is dat idd wat kort door de bocht, maar als je de details zou kennen niet. Het gaat namelijk om code voor mijn onderzoek, dat zich richt op een heuristiek voor een NP-Complete probleem. Bottlenecks waar ik bijv. tegenaan loop is het gemis van een goed alternatief voor memcpy.

http://msdn.microsoft.com...tem.buffer.blockcopy.aspx ?

En dan nog blijft mijn punt staan dat je pas kunt zeggen dat je een bottleneck hebt als je goed geprofiled hebt, en dat een beter algoritme veel meer impact kan hebben dan je hele programma omschrijven naar C++

[raptorix]

Een leraar van mij beweerde eens dat getallen van 1000 cijfers onmogelijk zijn, omdat er niet eens zoveel deeltjes in het heelal zijn

[Matis]

raptorix schreef op vrijdag 05 juni 2009 @ 10:37:
Een leraar van mij beweerde eens dat getallen van 1000 cijfers onmogelijk zijn, omdat er niet eens zoveel deeltjes in het heelal zijn

Hmm, Pi hebben ze al berekend tot zoveel miljoen biljoen decimalen.

Hier de eerste 1000. Ik weet niet wat voor leraar dat was, maar een rare sws Gaf hij toevallig geschiedenis ofzo
Edit: Hij had het nog fout ook, volgens Wikipedia zijn het aantal atomen in het heelal uit te drukken met een getal met 10.000.000.000.000 cijfers Daar komt de TS nog lang niet aan
Wikipedia: Googolplex

De eerste miljoen decimalen van π en 1/ π zijn beschikbaar door het project Gutenberg. Het huidige record (per oktober 2005) staat op 1.241.100.000.000 cijfers, die berekend werden in december 2002 aan het ITC van de Universiteit van Tokio.

[ Voor 14% gewijzigd door Matis op 05-06-2009 10:49 ]

[Memorice]

Maar heb je ook daadwerkelijk geconstateerd dat het een bottleneck is, dat wil zeggen door te profilen? Je gaat er nu zomaar van uit dat het een probleem oplevert, maar misschien treed de bottleneck straks wel ergens anders op.

Ik heb dit idd geconstateerd door te profilen. Overigens ben ik me er heel goed van bewust dat een beter algoritme vaak belangrijker is dan de programmeertaal op zichzelf. Echter stel dat je algoritme optimaal is (merk op dat ik niet beweer dat dit in mijn geval zo is). Neem tevens aan dat bepaalde functionaliteit duizenden malen uitgevoerd wordt (niet ongebruikelijk bij bijv. genetische algoritmes). Bedenk vervolgens dat het algoritme uren zo niet dagen runtime nodig heeft om tot een oplossing te komen als de input ook maar een klein beetje groot wordt (niet ongebruikelijk bij NP-Complete problemen). Dan denk ik dat er zeker winst te behalen valt door de keuze van c++.

[raptorix]

Matis schreef op vrijdag 05 juni 2009 @ 10:40:
[...]


Hmm, Pi hebben ze al berekend tot zoveel miljoen biljoen decimalen.

Hier de eerste 1000. Ik weet niet wat voor leraar dat was, maar een rare sws Gaf hij toevallig geschiedenis ofzo
Edit: Hij had het nog fout ook, volgens Wikipedia zijn het aantal atomen in het heelal uit te drukken met een getal met 10.000.000.000.000 cijfers Daar komt de TS nog lang niet aan
Wikipedia: Googolplex


[...]

Ik legde het niet helemaal goed uit, het ging om 10 tot macht 1000, en dus niet 1000 decimalen

[Matis]

raptorix schreef op vrijdag 05 juni 2009 @ 11:19:
Ik legde het niet helemaal goed uit, het ging om 10 tot macht 1000, en dus niet 1000 decimalen

Is dat niet exact hetzelfde

Hmm ik snap wat je bedoel. Je hebt het over natuurlijke getallen. Maar met decimalen doelde ik meer op de 1.helehoopdecimalen * 10^N zoals HuHu zegt.

Het maakt in zekere zin niet uit. Alleen staat er dan ergens een komma, maar dan zal het geen Int meer zijn

Enfin. Ik heb geen ervaring met BigInt's, maar wilde mezelf toch even laten horen dat deze getallen niet zo heel erg vreemd zijn

[HuHu]

MEMORICE schreef op vrijdag 05 juni 2009 @ 10:12:

@HuHu

Ik heb de precisie in de praktijk waarschijnlijk niet nodig (theoretisch gezien wel). Dus mocht je een oplossing hebben die werkt met een slechtere precisie, dan ben ik hier ook geinteresseerd in. Ik zelf heb zitten denken aan het gebruiken van logaritmes, echter is het volgens mij niet triviaal om een getal dat log (a) representeerd om te zetten in een getal dat log (a+b) representeerd. Dit is nogal essentieel, gezien ik het getal wil updaten zeg maar ipv volledig opnieuw te berekenen.

Ik weet het niet precies, maar het eerste wat in me opkomt is het (ge/mis)bruiken van complexe getallen. Die hebben een reëel en imaginair deel. Je zou in het reële gedeelte de 3.14156 kunnen opslaan en in het imaginaire gedeelte de 1054. Of zelf een datatype maken waarbij je dus twee afzonderlijke getallen opslaat.

Hoe het vervolgens met het rekenen precies gaat durf ik niet te zeggen. Optellen en aftrekken is volgens mij simpel. Gewoon de reële gedeeltes optellen/aftrekken en de imaginaire gedeeltes optellen/aftrekken. Voor vermenigvuldigen en al die dingen zou je even wat langer moeten nadenken.

[Memorice]

@HuHu

Dat zou inderdaad een optie kunnen zijn, echter geloof ik niet dat ik dit kan gebruiken binnen mijn onderzoek, gezien ik door het wegvallen van de precisie nooit meer kan bewijzen dat mijn algoritme correct is.

[Woy]

Maar je zegt dat je probleem is dat je geen memcpy functie hebt, dus dan zou ik eens kijken naar de functie die ik hierboven al linkte.

[bobo1on1]

Is dit niet wat? http://gnumpnet.codeplex.com/
Ik heb laatst eens met de GNU MP library in C++ gespeeld, fibonacci getal nummer 1000000 uitrekenen duurde anderhalve minuut en er kwam een getal uit van meer dan 200.000 tekens

[ Voor 13% gewijzigd door bobo1on1 op 05-06-2009 19:00 ]

[Sebazzz]

Uiteraard wel de directe formule gebruiken want als je de recursieve gebruikt

[Matis]

bobo1on1 schreef op vrijdag 05 juni 2009 @ 18:53:
Is dit niet wat? http://gnumpnet.codeplex.com/
Ik heb laatst eens met de GNU MP library in C++ gespeeld, fibonacci getal nummer 1000000 uitrekenen duurde anderhalve minuut en er kwam een getal uit van meer dan 200.000 tekens

Ik krijg hem niet aan de praat in C# onder Vista met VS2k8, blijft klagen over een DLL genaamd gmp

[Memorice]

Woy schreef op vrijdag 05 juni 2009 @ 18:40:
Maar je zegt dat je probleem is dat je geen memcpy functie hebt, dus dan zou ik eens kijken naar de functie die ik hierboven al linkte.

Dat is een van de problemen waar ik tegenaan liep, niet gerelateerd aan de BigInt overigens. Ik heb nog geen tijd gehad om uitgebreid naar deze functie te kijken, vandaar dat ik hier ook nog niet op gereageerd heb. Wel ziet het er veelbelovend uit, dus ik ben benieuwd naar de performance er van tenopzichte van mijn huidige clone functionaliteit.

[Memorice]

Ik heb een update met betrekking tot de BigInt, ik heb uiteindelijk besloten de volgende library te gebruiken:

http://www.codeproject.co...view=Quick&select=3042180

Het gevolg was dat de runtime van mijn code voor een bepaalde input van 5 minuten naar 5+ uur ging. Voor een kleinere input, die 29 seconden nodig had in de oude situatie en met het gebruik van de BigInt ineens 5-10 minuten, vertelde de profiler me het volgende:

Swensen.BigInt.Multiply: 6,743,362 calls
Swensen.BigInt.GenMultPart: 158,797,240 calls
Swensen.BigInt.AddTo: 152,053,878 calls

De totale tijd die in the methode zelf doorgebracht werd (dus niet in andere functie calls) bleek het volgende te zijn:

Swensen.BigInt.Multiply: 863,347
Swensen.BigInt.GenMultPart: 480,456
Swensen.BigInt.AddTo: 391,745

Het blijkt dus dat de BigInt klasse veruit de grootste bottleneck in mijn programma is.

[.oisyn]

raptorix schreef op vrijdag 05 juni 2009 @ 10:37:
Een leraar van mij beweerde eens dat getallen van 1000 cijfers onmogelijk zijn, omdat er niet eens zoveel deeltjes in het heelal zijn

Best een domme leraar dan . Je hebt immers slechts 1000 cijfers nodig om een getal van 1000 cijfers te vormen.

[Soultaker]

Misschien een idee om de BigInteger klasse van de Java (OpenJDK) er eens bij te pakken? Daar zal best enigzins over nagedacht zijn, en aangezien Java en C# veel op elkaar lijken zou je die makkelijk moeten kunnen porten.

Overigens denk ik niet dat de performance van een managed implementatie (t.o.v. een native implementatie) noodzakelijkerwijs heel slecht zal zijn. De data in een BigInteger wordt opgeslagen als een array van integers ofzo, en operaties als optellingen zijn vrij simpele for-loopjes. Dit soort operaties kan een JIT compiler juist uitstekend compileren en optimaliseren, en dan hoeft de managed implementatie dus geen nadeel te hebben ten opzichte van een native implementatie.

Als je een native library hebt zoals GMP, die intensief gebruik maakt van handmatig geoptimaliseerde assembly, dan wordt het misschien een ander verhaal, maar ik schat dat de Java implementatie prima mee kan komen met een portable C++ implementatie zonder rare trucs. Waarschijnlijk zal voor een C# port hetzelfde gelden, hoewel ik niet precies weet hoe goed de .NET JIT compiler is ten opzichte van die van Java.

[ Voor 9% gewijzigd door Soultaker op 07-06-2009 23:14 ]

[Sebazzz]

Het beste zal je waarschijnlijk GMP gebruiken ja, maar ik denk dat .NET nog net wat sneller is dan Java. Ik kan geen harde benchmarks vinden maar in de meeste gevallen lijkt C# sneller te zijn omdat het niet naar bytecode wordt omgezet maar echt wordt gecompileerd naar IL, en vooral sneller omdat als je WinForms gebruikt de native controls gebruikt. Elders lees ik dat de algoritmes met betrekking tot array's in sommige gevallen in C# slechter zijn, en Java beter presteert, onder andere met inserts. Bottomline: Ligt aan de situatie.

.oisyn schreef op zondag 07 juni 2009 @ 21:32:
[...]

Best een domme leraar dan . Je hebt immers slechts 1000 cijfers nodig om een getal van 1000 cijfers te vormen.

Ssst! Hij loopt nu strafwerk te doen omdat hij verteld heeft dat .oisyn zei dat de leraar dom was!

[ Voor 9% gewijzigd door Sebazzz op 07-06-2009 23:55 ]

[Soultaker]

Sebazzz schreef op zondag 07 juni 2009 @ 23:48:
Ik kan geen harde benchmarks vinden maar in de meeste gevallen lijkt C# sneller te zijn omdat het niet naar bytecode wordt omgezet maar echt wordt gecompileerd naar IL

Als je met IL de .NET Common Intermediate Language bedoelt, is dat gewoon de tekstuele representatie van de .NET bytecode. Natuurlijk wordt die weer gecompileerd voordat die wordt uitgevoerd, maar dat is in de Sun JVM niet anders.

.. en vooral sneller omdat als je WinForms gebruikt de native controls gebruikt.

Dat is goed mogelijk, maar daar heb je in dit geval niets aan. (Overigens kan je in Java ook gewoon native controls gebruiken met b.v. SWT.)

Elders lees ik dat de algoritmes met betrekking tot array's in sommige gevallen in C# slechter zijn, en Java beter presteert, onder andere met inserts. Bottomline: Ligt aan de situatie.

Zeker toen .NET net uit was, was de performance niet zo best. Waarschijnlijk is het verschil nu kleiner (hoewel Java ook niet stil heeft gestaan qua ontwikkelingen). Maar als jouw conclusie is dat het "aan de situatie ligt", dan kun je je eerder uitspraak dat "C# in de meeste gevallen sneller lijkt te zijn" beter intrekken denk ik.

[Phyxion]

Soultaker schreef op maandag 08 juni 2009 @ 00:21:
[...]

Als je met IL de .NET Common Intermediate Language bedoelt, is dat gewoon de tekstuele representatie van de .NET bytecode. Natuurlijk wordt die weer gecompileerd voordat die wordt uitgevoerd, maar dat is in de Sun JVM niet anders.


[...]

Dat is goed mogelijk, maar daar heb je in dit geval niets aan. (Overigens kan je in Java ook gewoon native controls gebruiken met b.v. SWT.)


[...]

Zeker toen .NET net uit was, was de performance niet zo best. Waarschijnlijk is het verschil nu kleiner (hoewel Java ook niet stil heeft gestaan qua ontwikkelingen). Maar als jouw conclusie is dat het "aan de situatie ligt", dan kun je je eerder uitspraak dat "C# in de meeste gevallen sneller lijkt te zijn" beter intrekken denk ik.

Ik denk niet dat hij dat hoeft in te trekken

Overigens kan je misschien beter of een andere library gebruiken of gewoon een die uit F# importen, ik denk dat het stukken sneller kan.