[c++] modulo van twee doubles

[dawuss]

Ik ben in visual c++ een programmatje aan het schrijven waarbij getallen van 0 tot 255 tot de macht van een getal van maximaal 10 cijfers worden verheven en modulo een getal van ongeveer 200 cijfers. Deze cijfers zijn wel integer (geen getallen achter de komma) maar ik kan dus geen int of long int gebruiken. Ik heb voor het variabeletype double gekozen, maar dan mag ik niet modulo (%) gebruiken. Hoe kan ik dit oplossen?

[.oisyn]

double fmod (double x, double y)

[dawuss]

in welke header vind ik die fmod?

bedankt voor de hulp, maar dat vind ik een beetje flauw hoor, niet iedereen vindt dat vanzelfsprekend hoor

[D2k]

math.h?

[.oisyn]

Op maandag 07 januari 2002 20:33 schreef dawuss het volgende:
maar dat vind ik een beetje flauw hoor, niet iedereen vindt dat vanzelfsprekend hoor

Uhm... in de manual kijken is niet vanzelfsprekend

[Janoz]

Voor het verheffen van die macht zijn speciale algoritmes waarbij je niet eerst de macht uit hoeft te rekenen. fmod is mischien heel leuk, maar je antwoord is absoluut niet gegarandeerd het juiste. Waneer de significantie kleiner is dan de mantis weet je niet meer welk getal er als eerste voor de komma komt. Op dat moment is een modulus niet meer te berekenen.

Het algoritme is hier wel eens langsgevlogen.. In een topic over RSA encoding oid.. Zal wel ff zoeken..

Uit m'n boek 'Introduction to algorihms':
modular exponentiation
a^b mod n

mod-Exp(a,b,n)
c = 0
d = 1
let (b_k,b_k-1,.....,b₀) be the binary representation of b
for i = k downto 0
__do c = 2c
_____d = (d * d) mod n
_____if b_i = 1
_______then c = c + 1
____________d = (d*a) mod n
return d

[edit]Nog ff een klein overtiep foutje eruit gehaald (eigenlijk een CnP foutje.. zie gequote code hieronder )

[RickN]

Op maandag 07 januari 2002 22:17 schreef Janoz het volgende:
Voor het verheffen van die macht zijn speciale algoritmes waarbij je niet eerst de macht uit hoeft te rekenen. fmod is mischien heel leuk, maar je antwoord is absoluut niet gegarandeerd het juiste. Waneer de significantie kleiner is dan de mantis weet je niet meer welk getal er als eerste voor de komma komt. Op dat moment is een modulus niet meer te berekenen.

Het algoritme is hier wel eens langsgevlogen.. In een topic over RSA encoding oid.. Zal wel ff zoeken..

Uit m'n boek 'Introduction to algorihms':
modular exponentiation
a^b mod n

mod-Exp(a,b,n)
c = 0
d = 1
let (b_k,b_k,.....,b_k) be the binary representation of b
for i = k downto 0
__do c = 2c
_____d = (d * d) mod n
_____if b_i = 1
_______then c = c + 1
____________d = (d*a) mod n
return d

Ja, dat algoritme heb ik idd ooit gepost in een thread over RSA oid. Ik heb toen ook meteen naar mijn Introduction to Algoritms (2nd ed. ) gegrepen en daar staat idd dit algorime in. Ik vond het toen echter niet zo handig dat de binaire representatie van b nodig was, dus toen heb ik het ff herschreven zodat je die niet meer nodig hebt. Dat algorime heb ik ergens vooraan in de codebase thread gepost.

Aah, zie hier. Toch handig, zo'n codebase...