Programmeringstävling

2009-11-27, 23:49 #61

Medlem

Reg: Sep 2007

Inlägg: 419

Citat:

Ursprungligen postat av Weeblie

Heh, koden är inte skriven på det sättet av optimeringsskäl utan är en direkt reflektion på hur jag tänker mig att algoritmen fungerar.

Något i stil med:

1. Ta exponenten och skriv om den i basen 2.
2. Kika på vilka bitar som är satta. Det är de som vi är intresserad av.
3. "Summera" (i detta fall egentligen "multiplicera") ihop resultatet för dem bitarna.

Bitvisa operatorer känns då (IMO) mycket mer naturliga än motsvarande division/modulos-operatorer.

ok. Dåså. Läste inte igenom koden men fick uppfattningen av ditt förklarande inlägg att du tänkt division.

Citera

2009-11-28, 18:58 #62

Medlem

Reg: Nov 2007

Inlägg: 655

Citat:

Ursprungligen postat av Weeblie

Kod:


int pow_mod(int a, int b, int mod)

{

    int res = 1;

    

    a %= mod;

    while(b > 0)

    {

        if(b & 1)

            res = (res * a) % mod;



        b >>= 1;

        a = (a * a) % mod;

    }



    return res;

}



int

main()

{

    printf("%d\n", pow_mod(1234567898, 1234567898, 1000));



    return 0;

}

Intressant problem. Har nog aldrig använt bitwise operationer om jag ska vara helt ärligt. Något som jag velat lärt mig mer om, men aldrig fått tiden. Men nu blev jag sugen efter att läst AquaRegia och din kodsnutt.

Jag funderade på en sak ang. outputen. Jag testa och körde din kod och fick ut 709, medans AquaRegia output var 944. Får du samma output eller är det jag som har skrivit något fel någonstans. Skulle vara kul att veta vilken output som är rätt så jag kan analysera lite mer på djupet

Citera

2009-11-28, 19:29 #63

Medlem

Reg: Sep 2009

Inlägg: 3 395

Citat:

Ursprungligen postat av ancide

Intressant problem. Har nog aldrig använt bitwise operationer om jag ska vara helt ärligt. Något som jag velat lärt mig mer om, men aldrig fått tiden. Men nu blev jag sugen efter att läst AquaRegia och din kodsnutt.

Jag funderade på en sak ang. outputen. Jag testa och körde din kod och fick ut 709, medans AquaRegia output var 944. Får du samma output eller är det jag som har skrivit något fel någonstans. Skulle vara kul att veta vilken output som är rätt så jag kan analysera lite mer på djupet

Båda ger samma output, 944.

http://codepad.org/gsKU41dI
http://codepad.org/gklyds8I

Vill också tillägga att jag inte kom på lösningen själv, jag fick se algoritmen på en matematiklektion, skrev ner en kod för den och formulerade en fråga efteråt.

EDIT: http://i50.tinypic.com/fxmo5.jpg, http://i47.tinypic.com/2isjh2f.jpg

__________________
Senast redigerad av AquaRegia 2009-11-28 kl. 19:34.

Citera

2009-11-28, 19:40 #64

Medlem

Reg: Nov 2007

Inlägg: 655

Citat:

Ursprungligen postat av AquaRegia

Båda ger samma output, 944.

http://codepad.org/gsKU41dI
http://codepad.org/gklyds8I

Vill också tillägga att jag inte kom på lösningen själv, jag fick se algoritmen på en matematiklektion, skrev ner en kod för den och formulerade en fråga efteråt.

Okej, tack. Då hade jag skrivit fel någonstans bara

Citera

Programmeringstävling

Stöd Flashback