C# schnelles BigInteger?

[DeepComputer]

Hallo,

ich hab ein Porgram geschrieben, das zeimlich schnell Primzahlen bis ulong.Maxvalue faktorisieren kann.
Jetzt wollt ich natürlich drüber gehen und hab BigInteger verwendet - aber es ist echt langsam.
Ich weiß, dass die Performance mit dem Umwandeln des strings zusammenhängt...
aber kennt ihr trotzdem eine schnellere Alternative?

lg

 

[tollertyp]

Also Primzahlen sind ziemlich leicht zu faktorisieren. Aber vermutlich meinst du Zahlen in ihre Primzahlen faktorisieren?

Würde UInt64 nicht ausreichen?

 

[DeepComputer]

Haha, ja letzteres meinte ich
Na eben nicht. Die krieg ich fix runter.

Das ist jetzt mit BigInteger. Wäre es ein ulong würde es max 50 Sekunden dauern... so dauerts 2 Minuten oder mehr...

 

[tollertyp]

https://www.geeksforgeeks.org/uint64-maxvalue-field-in-c-sharp-with-examples/

Also wie groß ist denn dein Max-Value? 18446744073709551615?

 

[DeepComputer]

Also wie groß ist denn dein Max-Value? 18446744073709551615

Ja klar... sieht man am Screenshot. 18446744073709551617 ist schon die zweite BigInteger Zahl.

 

[tollertyp]

Ach sorry, mein Fehler... ich dachte dir reicht der Zahlenbereich bis ulong.Maxvalue. Selbst etwas schlecht gelesen, ich werde halt alt oder bin es schon.

Ergänzung (12. Oktober 2021)

Evtl wäre das was? https://github.com/devoyster/IntXLib

 

[DeepComputer]

Uuuhh, thx! Habs schon installiert!

 

[gymfan]

Den letzten Abschnitt dort hast Du vermutlich auch gelesen
"I have compared IntX performance to GMP on basic arithmetic operations and it appeared that GMP is up to 8 times faster than IntX on certain operations."
und dann
"Btw, using GMP from C# is quite easy because there are GMP C#-wrappers available"

Wenn es nicht zwingend managed Code in C# sein muss, solltest Du GMP aus Performancegründen wohl auch mal testen.

 

[BeBur]

Evtl wäre das was? https://github.com/devoyster/IntXLib

Wobei der Autor in dem Link GMP empfiehlt. Davon abgesehen ist das Projekt ja schon 7 Jahre alt.

 

[DeepComputer]

Den letzten Abschnitt dort hast Du vermutlich auch gelesen

Ja, jetzt gerade. Ja macht nichts, dann nehm ich halt GMP. Ist mir auch recht

 

[Tornhoof]

Probier Mal das aktuelle rc2 von .NET 6. Afaik wurde für 6.0 biginteger optimiert. Ansonsten nen c# wrapper für gmp nutzen.
Oder deinen algo zb auf avx https://docs.microsoft.com/de-de/dotnet/api/system.runtime.intrinsics.vector256-1?view=net-5.0 entwickeln, dann kannst 256bit machen.

 

[DeepComputer]

Ansonsten nen c# wrapper für gmp nutzen.

Oja, was ist das bitte? Weil ich lese mir gerade die GMP doku durch und GMP ist für c++ geschrieben...
Wäre a bissl mühsam jetzt alles umzuschreiben ...

 

[Tornhoof]

Hmm?
Es gibt halt c# Bibliotheken die bilden die gmp API via pinvoke auf c# ab. Funktioniert unterschiedlich gut
Es ist sicherlich kein einfacher Plug&Play Ersatz für Long/bigint

Anmerkung: gmp (Gnu mp) ist in c geschrieben und hat c++ bindings, das ist nicht das gleiche wie in c++ geschrieben.

 

[DeepComputer]

stimmt stimmt, hab ich jetzt auch rausgelesen.
Nun, das ist mir alles etwas zu hoch... jetzt geht mein Code nicht mehr weil die lib nicht für .NET5.0 gemacht ist :/ jetzt versteh ich auch warum mir VS2019 .NET3.x empfohlen hat...

 

[Tornhoof]

Das ist das Problem mit alten Bibliotheken, wenn die für netfx 4.x geschrieben worden.
Du kannst versuchen ob's damit noch läuft, kann funktionieren, muss aber nicht

 

[DeepComputer]

Ne, also die lib funktioniert. Ich muss eben nur alle Felder, Methoden, Klassen, Variable, usw. GMP taulgich umschreiben. Ist ein bischen Arbeit aber ich bin schon aufs Ergebnis gespannt!