Simpel regnestykke

Rent matematisk burde der jo ikke være noget i vejen, men kan det tænkes at den laver en afrundingsfejl på det meget store tal som 41^77 er???

Du kan eventuelt prøve at tildele potensværdien til en double, inden du udfører mod-beregningen.

Du skal udnytte, at 41^77 mod 221 er det samme som
((41^10 mod 221)^7*(41^7 mod 221)) mod 221
Det er muligt du skal bryde det endnu mere ned. Prøv ad.

(Her er udnyttet at (a*b) mod n er det samme som
((a mod n)*(b mod n)) mod n

41^77 er et temmelig stort tal, så almindlige int's kan ikke bruges.
Mon der er noget andet ??

import java.math.BigInteger;

public class PowMod {
    public static void main(String[] args) {
        BigInteger i1 = new BigInteger("41");
        BigInteger i2 = new BigInteger("77");
        BigInteger i3 = new BigInteger("221");
        System.out.println(i1.modPow(i2,i3));
    }
}

Output:

6

nmh -> interessant teori du har gang i, men så vidt jeg kan se så er der en fejl i algoritmen...?

arne_v -> ja det fungerer jo glimrende (som sædvanligt)

Du ved ikke tilfældigvis hvordan man laver samme trick i C#.NET vel? (sidder igen med min dobbeltprogrammering)

Der er ikke fejl i algoritmen, men man skal hele tiden passe på overløb.
Her er en omskrivning som virker:

41^77= (41^11)^7=((41^5)*(41^6))^7

Vi regner nu modulo 221, og for at det skal blive mere overskueligt indfører vi nogle variable:

a=Math.pow(41,5)%221
b=Math.pow(41,6)%221
c=(a*b)%221
d=Math.pow(c,7)%221

Nu har d værdien 6

arne v's metode virker godt nok i dette tilfælde, men hvis tallene bliver lidt større vil det gå galt.

Du var lidt for hurtig til at afvise mit svar. Se mit sidste indlæg. Sådan skal det gøres!

nmh>

Jeg vil ikke betivle dine matematiske evner.

Men læs lige lidt om BigInteger.

Det er vilkårligt store integers !!

De overflower aldrig.

nmh -> hmm faktisk ja... dit eksempel virker fint, men hvor meget større skal tallene være før at det går galt?

det er meningen at algoritmen skal kunne bruges med variabler...

I C#.net har man ikke typen BigInteger.
>Arne V: mht overflow: Maskinens lager sætter i hvertfald en øvre grænse på  disse tal, men du har da ret i, at det, at kunne arbejde med "næsten" vilkårligt lange tal, er en fordel.

Men i c# virker det ikke.

import java.math.BigInteger;

public class PowMod2 {
    public static void main(String[] args) {
        System.out.println(powmod(41, 77, 221));
    }
    public static int powmod(int a, int b, int c) {
        BigInteger i1 = new BigInteger(Integer.toString(a));
        BigInteger i2 = new BigInteger(Integer.toString(b));
        BigInteger i3 = new BigInteger(Integer.toString(c));
        return i1.modPow(i2,i3).intValue();
    }
}

(og tænk lidt grimme tanker om den person hos SUN der valgte ikke
at lave en constructor for BigInt med int som argument)

modPow regner nu ganske effektivt både i tid og plads.

Med hensyn til C# så prøv og kig på:
  http://www.codeproject.com/csharp/BigInteger.asp

arne_v >> der er måske en grund -- hvad nu hvis man vil initialisere en BigInt med en værdi, som ikke kan skrives med en literal (primitiv) int - Med String har man al plads i verden (næsten:-)

Der er jo ingen der siger at modPow først laver en pow og så en mod.

Det er nærmest sandsyneligt at den ikke gør (fordi så var der ikke nogen grund
til en selvstændig funktion (der er både pow og mod).

bearhugx>

Jeg har ikke nogen indvendinger mod constructor med String - selvfølgelig
skal den være der.

Jeg savner bare en constructor fra int ved siden af. Fordi man rimeligt
ofte har brug for at starte med en lille værdi. Og jeg synes at den
konvertering til String er meget grim.

arne_v >> right you are :-)  (ps: er igang med at skrive en mail til dig... should arrive shortly...)

Jeg prøvede lige at operationalisere nmh's algoritme og hvis man ved
at a ikke er for stor, så er den faktisk nem at kode:

public class Alt {
    public static void main(String[] args) {
        System.out.println(powmod(41, 77, 221));
    }
    public static int powmod(int a, int b, int c) {
        if(b > 3) {
            return ((powmod(a, b/2, c) * powmod(a, b- b/2, c)) % c);
        } else {
            return (int)(Math.pow(a, b) % c);
        }
    }
}

ser nemlig ud til at virke !

arne V>> En elegant løsning med brug af rekursion! Flot.

arne_v -> ja det der er rimelig meget sejt. (og så virker det sproguafhængigt uden brug af frameworks) :-D (Math.pow er standard - men ellers er den let selv at implementere)

arne_v 22:45:57 -> i min situation så bliver de enkelte tal ikke så store, det er mere når den der potensfunktion kommer ind i billedet at det gav problemer. Nu spiller det maks!