Modulus op extreem groot nummer

[Arise]

In c# wil ik de modulus van een zeer groot nummer berekenen. Mijn probleem is dat geen enkel datatype mijn zeer groot nummer aankan. Het nummer is 30 cijfers lang en moet precies zijn.

Dus iets in de aard van

zeer_groot_nummer % 983 = resultaat.

Kent iemand een oplossing ?

[Hielko]

Er zijn ongetwijfeld allerlei standaard libraries die met bigints kunnen werkem: google eerst maar eens....

[Niemand_Anders]

Bouncy Castle heeft een BigNumber class welke een Mod(ules) methode heeft. Uit m'n hoofd kan BigNumbers werkten met 128 integers. BigInt (in C#) is 64- bits.

[mocean]

Je kan het ook oplossen door het getal te splitsen als string.

Als je bijv. de eerste 5 getallen links pakt, die mod 983 doet, dan plak je het resultaat weer links eraan. Zo schrijf je snel een functie die de mod berekend in een paar iteraties.

Voorbeeld:

PHP:

$a=1234567 % 8; // geeft 7

//Splitsen
$b=12 % 8; // geeft 4

$rest=intval($b.'34567'); //wordt 434567
$c=$rest % 8; // geeft 7

Je zal in C# nog wat moeten doen ivm type-casting, maar het werkt verder wel snel denk ik.

[Confusion]

mocean schreef op donderdag 08 mei 2008 @ 17:18:
Je kan het ook oplossen door het getal te splitsen als string.

Jij mag nooit een algoritme voor mij schrijven.

10 mod 2 = 0
1 mod 2 = 1

'nuff said?

[Bosmonster]

Confusion schreef op donderdag 08 mei 2008 @ 17:25:
[...]

Jij mag nooit een algoritme voor mij schrijven.

10 mod 2 = 0
1 mod 2 = 1

'nuff said?

Volgens zijn methode plak je toch die 1 toch weer aan de 0 en neem je daar de modulus weer van en die is weer 0.

[Voutloos]

Die methode klopt, maar het lijkt me toch niet de mooiste manier om het probleem op te lossen.

[pkuppens]

mocean schreef op donderdag 08 mei 2008 @ 17:18:
Je kan het ook oplossen door het getal te splitsen als string.

Als je bijv. de eerste 5 getallen links pakt, die mod 983 doet, dan plak je het resultaat weer links eraan. Zo schrijf je snel een functie die de mod berekend in een paar iteraties.

Voorbeeld:

PHP:

$a=1234567 % 8; // geeft 7

//Splitsen
$b=12 % 8; // geeft 4

$rest=intval($b.'34567'); //wordt 434567
$c=$rest % 8; // geeft 7

Je zal in C# nog wat moeten doen ivm type-casting, maar het werkt verder wel snel denk ik.

Het idee is best aardig, maar ik zou niet eerst iets van je string afhalen, en er dan weer wat voor plakken.

Even uitgaand van een character stream als groot getal representatie en een integer modulus, liefst ook nog een beetje beschaafde, als deler, zou ik iets doen als:

code:

m = 0; // initialiseer
while (input)
   g = getch(input); // cijfer pakken van input stream
   g0= cijfer(g); // naar cijfer 0..9 omzetten en loop afbreken als dat niet zo is
   m = (m*10 + g0) % modulus;
end
return (m);

Enige risico is dat m*10 +g0 niet mag overflowen in de int, dat gaat goed als modulus < maxint - 10.
Haakjes verder zeker goed zetten, ivm binding % operator.

[ Voor 6% gewijzigd door pkuppens op 08-05-2008 17:51 ]

[pkuppens]

Bosmonster schreef op donderdag 08 mei 2008 @ 17:33:
[...]


Volgens zijn methode plak je toch die 1 toch weer aan de 0 en neem je daar de modulus weer van en die is weer 0.

Nee, die is weer de modulus van 10, die is weer de modulus van 10, ....
hey, ik begin een patroon te herkennen...

[mithras]

pkuppens schreef op donderdag 08 mei 2008 @ 17:44:
[...]


Nee, die is weer de modulus van 10, die is weer de modulus van 10, ....
hey, ik begin een patroon te herkennen...

Het voorbeeld is dus ook gewoon een slecht voorbeeld

Het principe is wel correct, aangezien je de modules vanaf het 10^n de deel als 10^n-de tal voor je rest plakt. Dan komt je modulus berekening goed uit.

[Soultaker]

Je kunt hier handig gebruiken dat congruentie bewaard blijft bij optelling en vermenigvuldiging. Een getal is te schrijven als som van cijfers vermenigvuldigt met de basis waarin je werkt tot een bepaalde macht verheven: getal = som(basis^k * cijfer_k)

Dus kun je ook schrijven:
getal%m = som((basis^k * cijfer_k))%m
Of:
getal%m = som((basis^k * cijfer_k)%m)%m)
Of:
getal%m = som((basis^k%m) * (cijfer_k%m))%m)%m)
(De cijfer_k%m term is natuurlijk zinloos als basis < m)

Dat principe kun je handig in code omzetten:

C:

const int cijfers[10] = { 3, 1, 4, 1, 5, 9, 2, 6, 5, 3 };
const int basis = 10, m = 983;
int k = 10, b = 1, r = 0;
while (--k >= 0)
{
    r = (r + cijfers[k]*b)%m;
    b = b*basis%m;
}
printf("%d\n", r);

Je moet nog steeds wel oppassen voor overflow, maar dat risico is alleen afhankelijk van m (in deze code moet ongeveer 2*m*m nog in een int passen, wat met een extra modulo terug te brengen is tot m*m). Als je efficiente code wil schrijven wil je het doen van de modulo-operatie liefst niet elke iteratie uitvoeren, maar dat is een optimalisatie.

pkuppens schreef op donderdag 08 mei 2008 @ 17:42:
Even uitgaand van een character stream als groot getal representatie en een integer modulus, liefst ook nog een beetje beschaafde, als deler, zou ik iets doen als:

code:

m = 0; // initialiseer
while (input)
   g = getch(input); // cijfer pakken van input stream
   g0= cijfer(g); // naar cijfer 0..9 omzetten en loop afbreken als dat niet zo is
   m = (m*10 + g0) % modulus;
end
return (m);

Dit werkt ook en is misschien nog wel beter.

Enige risico is dat m*10 +g0 niet mag overflowen in de int, dat gaat goed als modulus < maxint - 10.

Ik denk zou denken dat je modulus < (maxinit - 10)/10 moet hebben, anders gaat het nog mis als bv. m = modulus - 1.

[ Voor 34% gewijzigd door Soultaker op 08-05-2008 18:08 ]

[pedorus]

Even googelen geeft http://www.codeproject.com/KB/cs/biginteger.aspx

[mocean]

Confusion schreef op donderdag 08 mei 2008 @ 17:25:
[...]

Jij mag nooit een algoritme voor mij schrijven.

10 mod 2 = 0
1 mod 2 = 1

'nuff said?

De methode zou je in een loop moeten toepassen waarbij het getal waardoor je MOD natuurlijk niet groter wordt dan je rest, aangezien je dan je antwoord al hebt!

[Arise]

Heb ondertussen al zelf de bigint vanop codeproject gevonden, zoals ook hierboven vermeld.

Toch bedankt aan iedereen voor de commentaren.

[RemcoDelft]

Wellicht heb je iets aan (de source van) "bc":

bc - An arbitrary precision calculator language

[Confusion]

mocean schreef op donderdag 08 mei 2008 @ 18:44:
De methode zou je in een loop moeten toepassen waarbij het getal waardoor je MOD natuurlijk niet groter wordt dan je rest, aangezien je dan je antwoord al hebt!

Wat ik bedoelde is dat de modulus operator niet associatief is. 7314 mod 23 = (7300 + 14) mod 23 != 7300 mod 23 + 14 mod 23. Maar dat is ook niet wat je voorstelde, dus ik zwamde maar wat.