[c++] modulair machtsverheffen

[dawuss]

Ik heb even een simpel ding inelkaar geflansd om modulair machten te verheffen.

code:

double ModMacht(double a, double m, double n)
{
    double c = a;
    long int counter;
    for(counter = 1; counter < m; counter++)
    {
        c = a * c;
        c = fmod(c, n);
        cout << counter << "\n";
    }
return c;       
}

Nou wil ik de output controleren, dus heeft iemand een programma dat modulair kan machtsverheffen (source, of executable maakt niet uit) waarmee ik mijn source kan controleren?

Kan iemand mij uitleggen wat er trouwens mis is aan de onderstaande code:

code:

double ModMacht(double a, double k, double n)
{
    double t = 1;
    while (a > 0)
    {
        if(k/2==int(k/2)) //is k even?
        {
            k = k - 1;
            t = modf(t * a, n);
        }
        k = k / 2;
        a = modf(a * a, n);

    }
cout << t;
return t;
}

Deze moet effectiever zijn, doordat er minder berekeningen plaatsvinden, maar het werkt niet

[marcusk]

Kan iemand mij uitleggen wat er trouwens mis is aan de onderstaande code:

code:

...
if(k/2==int(k/2)) 
...

Ik denk dat het daaraan ligt. Doordat er vaak kleine afwijkingen zijn bij de resultaten van fp operaties zal dit niet goed werken.

[edit]hmm, hoewel... je converteert wel eerst naar int

[dawuss]

Dat controleren op even/oneven werkt vrij goed. Heb het uitgeprobeerd met hele grote getallen, en dan werkt het nog steeds.

[dawuss]

De bovenstaande code werkt ook niet

ik heb het op m'n grafische rekenmachine wel werkend gekregen.

code:

Prompt A,M,N
A -> C
For(Z,1,(M-1),1)
A*C -> C
int(((C/N)-int(C/N))*N+.5) -> C    
/* dit is een zelfgemaakte modulo functie, omdat TI-BASIC dit niet heeft */
Disp C
End
Disp "---------"
Disp C

deze werkte wel, dat heb ik gecontroleerd.
dit zou hetzelfde resultaat op moeten leveren, als bovenstaande c++ code, maar er klopt niets van

even wat uitleg:

code:

c -> a

betekent "sla de waarde van c op in a"
dus

code:

a = c;

[zork]

Urhm, ik zit eigenlijk met een zelfde soort probleem...

[JayTaph]

een casting gebruiken om even/oneven te checken werkt misschien, maar is niet echt een aanraden. Je kunt beter kijken of "k mod 2 == 0" of nog beter k&1.

[dawuss]

sorry, ik ben een beetje n00b nog op dit gebied.

dat mod is wel een goed idee, maar wat is een casting?

wat houdt k&1 in?

[JayTaph]

nou, uit k/2 komt een getal uit, bijvoorbeeld 1.5 (met als geluk dat K een double is, als het een int was, dan gaat het al niet eens).

Wat je doet is kijken of 1.5 gelijk is aan int(1.5), oftewel je typecast een float (1.5) naar een int toe. In dit geval word dat 1 en aangezien 1.5 niet gelijk is aan 1, is het getal oneven. (2/2=1 int(1)=1, dus gelijk, dus even).

Het werkt in sommige situaties, waaronder die van jou, maar zeker niet overal.


k&1 wil zeggen dat er gekeken wordt of het eerste bitje van K 1 is. Als dat het geval is, dan is een getal oneven (reken maar een paar getallen om naar binair en kijk naar het eerste (meest rechtste) bitje ..

[dawuss]

ja, ik snap wat je bedoelt.
Eigenlijk een enorm slimme manier.

Kun je op een soortgelijke manier de binaire waarde van een double krijgen?

[dawuss]

code:

if(k&1)
{
...
}

geeft een compile error:

error C2296: '&' : illegal, left operand has type 'double'

[JayTaph]

Op dinsdag 28 mei 2002 00:18 schreef dawuss het volgende:
ja, ik snap wat je bedoelt.
Eigenlijk een enorm slimme manier

Kun je op een soortgelijke manier de binaire waarde van een double krijgen?

Wat versta je onder de binaire waarde? (een variabele is altijd binair, het ligt eraan in welke context je het bekijkt).

[RickN]

Die efficientere versie van je lijkt eerlijk gezegd nergens op. Je gebruikt a>0 als guard maar a wordt helemaal niet gegarandeerd kleiner, dus er is helemaal geen garantie dat je loop überhaupt eindigt, laat staan een fatsoenlijk resultaat oplevert. Ik heb in Delphi een powermod algoritme geschreven en dat staat hier

edit:
Je had het dus wel bijna goed

[JayTaph]

Op dinsdag 28 mei 2002 00:21 schreef dawuss het volgende:

code:

if(k&1)
{
...
}

geeft een compile error:
[..]

shit.. natuurlijk, logische operatoren mogen niet bij doubles... dat wist ik wel, maar het is al laat..

[dawuss]

gewoon, ik geef hem een double met waarde 100
en dan geeft hij 1100100 terug
als ik het goed begrijp geeft 255&2 dan de tweede bit terug?

[JayTaph]

Op dinsdag 28 mei 2002 00:27 schreef dawuss het volgende:
gewoon, ik geef hem een double met waarde 100
en dan geeft hij 1100100 terug
als ik het goed begrijp geeft 255&2 dan de tweede bit terug?

Ja, als voorwaarde dat je je double wel eerst cast naar een int, anders mag het namelijk niet (bitverdeling bij een float en double is anders als bij een int)

if ((int)k&1) {
// oneven
}

[dawuss]

Die efficientere versie van je lijkt eerlijk gezegd nergens op. Je gebruikt a>0 als guard maar a wordt helemaal niet gegarandeerd kleiner, dus er is helemaal geen garantie dat je loop überhaupt eindigt, laat staan een fatsoenlijk resultaat oplevert. Ik heb in Delphi een powermod algoritme geschreven en dat staat hier

ik zal even het idee achter de code uitleggen.

ik moet weten: mod(pow(x, e), n)
voor x neem ik even de waarde 128 (gewoon een random getal)
voor e neem ik 1096 (een random getal)
voor n neem ik 123

als ik dus mod(pow(128, 1997), n) doe, moet hij 128 tot de macht 1997 uit kunnen rekenen. Dit is nogal een enorm getal, dus ga ik het opdelen.

Ik ga nu steeds kwadrateren, en modulus n nemen, totdat ik op de 1096e macht zit.

ik reken dit nu uit door 10 keer te kwadrateren, en dan twee keer te vermenigvuldigen.

[dawuss]

Op dinsdag 28 mei 2002 00:25 schreef RickN het volgende:
Die efficientere versie van je lijkt eerlijk gezegd nergens op. Je gebruikt a>0 als guard maar a wordt helemaal niet gegarandeerd kleiner, dus er is helemaal geen garantie dat je loop überhaupt eindigt, laat staan een fatsoenlijk resultaat oplevert. Ik heb in Delphi een powermod algoritme geschreven en dat staat hier

edit:
Je had het dus wel bijna goed

ik zie in dit topic eigenlijk alleen een reactie op een code om pi te berekenen met perl onder jouw naam

kun je de code even posten dan?

[RickN]

Op dinsdag 28 mei 2002 00:39 schreef dawuss het volgende:

[..]

ik zal even het idee achter de code uitleggen.

ik moet weten: mod(pow(x, e), n)
voor x neem ik even de waarde 128 (gewoon een random getal)
voor e neem ik 1096 (een random getal)
voor n neem ik 123

als ik dus mod(pow(128, 1997), n) doe, moet hij 128 tot de macht 1997 uit kunnen rekenen. Dit is nogal een enorm getal, dus ga ik het opdelen.

Ik ga nu steeds kwadrateren, en modulus n nemen, totdat ik op de 1096e macht zit.

ik reken dit nu uit door 10 keer te kwadrateren, en dan twee keer te vermenigvuldigen.

Ik begrijp heel goed wat je probeert te doen, en het is bijna goed, alleen kan het met de guard die je nu gebruikt nooit werken, omdat die guard niet eens garandeerd dat het algoritme eindigt. B.v. als je voor n een priemgetal neemt eindigt het algoritme nooit, omdat er geen enkel getal x in Z/pZ (p priem) zit waarvoor geldt dat x*x mod n = 0

[RickN]

Op dinsdag 28 mei 2002 00:46 schreef dawuss het volgende:

[..]

ik zie in dit topic eigenlijk alleen een reactie op een code om pi te berekenen met perl onder jouw naam

kun je de code even posten dan?

Sorry, eerste pagina (25 posts/pagina) onder mijn oude nick Xalista.

[dawuss]

gevonden:

code:

function PowerMod(a, b, n: int64): int64;
var c: int64;
begin
  c := 1;
  while b > 1 do
  begin
    if (b mod 2) = 1 then
    begin
    c := (a * c) mod n;
    b := b - 1;
    end;
    a := (a * a) mod n;
    b := b div 2;
  end;
  result := (a * c) mod n;
end;

code:

double PowerMod(dobule a, double b, double n)
{
  double c = 1;
  while (b > 1)
  {
    if (fmod(b, 2)== 1)
    {
    c = fmod((a * c), n);
    b = b - 1;
    }
    a = fmod((a * a), n);
    b = b / 2;
  }
  return fmod((a * c), n);
}

zou hem dan moeten zijn in C++ toch?

edit:

aangepaste code met INT 64:

code:

__int64 ModMacht(__int64 a, __int64 b, __int64 n)
{
  __int64 c = 1;
  while (b > 1)
  {
    if (fmod(b, 2)== 1)
    {
    c = (a * c) % n;
    b = b - 1;
    }
    a = (a * a)% n;
    b = b / 2;
  }
  return (a * c) % n;
}

[.oisyn]

mwah, je kunt van die doubles beter een 64 bits int gebruiken (maar het type daarvoor verschilt nogal per compiler... in VC++ is het __int64, en in GCC is het long long)

bovendien kun je dan gewoon van de % operator gebruik maken ipv de fmod functie

[dawuss]

wow, dat wist ik helemaal niet. (staat weer es niet in dat boek van mij )

die aangepaste code van mij werkt trouwens niet. maar ik ga eerste ven alles veranderen in een 64 bits INT

kan ik ook een 128 bits int gebruiken?

[.oisyn]

dan zul je zelf een 128bits implementatie moeten schrijven (maw, daar zijn geen standaard typen voor )

overigens denk ik dat 32 bits ints ook wel zullen voldoen, ik weet niet hoe groot de getallen zijn waarmee je wilt rekenen...?

[dawuss]

eeh, als het kan 200 decimalen maar dat is niet per sé nodig hoor




Met de nieuwe code loop ik tegen een nieuw probleem aan:
Ik heb in mijn hele code "COUT" commands gebruikt, maar dat pikt hij niet als er in een int 64 in zit.

resultaat: een enorme hoop errors...

moet ik nou maar alles vervangen door printf() of kan het nog anders?

[dawuss]

printf(__int64)
kan ook niet hier

[Soultaker]

Op dinsdag 28 mei 2002 01:19 schreef dawuss het volgende:
printf(__int64)
kan ook niet hier

64-bits integers kun je printen met %I64d als format specifier (of %lli onder GCC, denk ik).

Wat had C++ trouwens met dit onderwerp te maken?

[.oisyn]

er staat cout in z'n code

[Soultaker]

Op dinsdag 28 mei 2002 02:06 schreef .oisyn het volgende:
er staat cout in z'n code

Oh ja! Silly me.

[dawuss]

Jah, kan het ook niet helpen dat ik een n00b ben, ik weet alleen wat ik tot nu toe geleerd heb...

[dawuss]

het enige probleem dat ik nu nog heb, is dat ik een sqrt() nodig heb die met 64 bits INT's om kan gaan...

[dawuss]

Is het mogelijk om die __int64 unsigned te krijgen? De getallen mogen namelijk nooit kleiner dan 0 zijn, dus dan heb ik die waarden beneden 0 niet nodig, en boven de 0 des te harder

[.oisyn]

unsigned __int64 blaat;

werkt hier prima hoor (je kan het natuurlijk ook gewoon zelf even proberen)

[dawuss]

Ik heb het ook geprobeerd, maar hij kan nog steeds niet groter zijn dan 9223372036854775807
gewoon een for loopje gemaakt, maar het getal wordt negatief als hij groter wordt dan 9223372036854775807.


Na het implementeren van die __int64 kwam ik nog op een probleempje uit:

hier de source van mijn inverse modulo functie:

code:

__int64 invmod(__int64 e, __int64 n)
{
    __int64 multiplier;
    __int64 x = 0;
    __int64 y = 0;
    __int64 z = 2;
    __int64 d = 0;
    __int64 invmod[2][3] = { {0,1,n}, {1,-(e/n),e-(e/n)*n} };
    while (z>1)
    {
        if (invmod[1][2] == 0) // voorkomen van een division by zero
        {
            break;
        }
        multiplier = invmod[0][2]/invmod[1][2];
        x = invmod[0][0] - multiplier * invmod[1][0];
        y = invmod[0][1] - multiplier * invmod[1][1];
        z = invmod[0][2] - multiplier * invmod[1][2];
        invmod[0][0] = invmod [1][0];
        invmod[0][1] = invmod [1][1];
        invmod[0][2] = invmod [1][2];
        invmod [1][0] = x;
        invmod [1][1] = y;
        invmod [1][2] = z;
        printf("%I64d", x);
        printf(" * ");
        printf("%I64d", e);
        printf(" + ");
        printf("%I64d", y);
        printf(" * ");
        printf("%I64d", n);
        printf(" = ");
        printf("%I64d", z);
        printf("\n");
    }
return x;
}

deze maakt gebruik van het uitgebreide euclidische algorhitme.

De variabele "multiplier" is nu ook een __int64, maar daardoor kan hij dus geen 'breuken' bevatten. Ik heb geprobeerd dit met doubles op te lossen, omdat de hele code hiervoor met doubles werkte, maar dan krijg ik allemaal compile warnings, en werkt het programma niet.
Hoe los ik dit netjes op?

[.oisyn]

Op dinsdag 28 mei 2002 15:16 schreef dawuss het volgende:
Ik heb het ook geprobeerd, maar hij kan nog steeds niet groter zijn dan 9223372036854775807
gewoon een for loopje gemaakt, maar het getal wordt negatief als hij groter wordt dan 9223372036854775807.

dat is omdat de printf er signed van maakt
print m eens als %I64u

en dit:

code:

        printf("%I64d", x);
        printf(" * ");
        printf("%I64d", e);
        printf(" + ");
        printf("%I64d", y);
        printf(" * ");
        printf("%I64d", n);
        printf(" = ");
        printf("%I64d", z);
        printf("\n");

kun je simpel herschrijven als

code:

printf ("%I64d * %I64d + %I64d * %I64d = %I64d\n", x, e, y, n, z);

[dawuss]

tuurlijk
dat met printf() is inderdaad een stuk handiger ja

Ik krijg het nog steeds niet voorelkaar die invmod() functie te laten werken met __INT64

ik ben nu bezig met de functie op_Implicit(__int64 value);
, maar dat wil nog niet helemaal lukken