Rechnen mit extrem großen Zahlen

ich würde die exponentiation schrittweise machen:

((4378%317)*4378)%317 ...... usw.

was will man mehr...

tausend dank :)

und wies wie Bayern so machen: bierchen ausgeb

Baeri B. schrieb:
> jetzt steh ich vor dem Problem, dass aber einer gewissen Zahlengröße
> "gerundet" wird oder der Überlauf zu Negativen zahlen... <- soweit so
> logisch.
>
> meine Rechung 4378^120
>
> Der Windows Taschenrechner macht das gut... WOBEI mich das Ergebnis
> nicht wirklich interessiert denn es wird weiterverarbeitet mit einen
> MODULO
> (4378^120) MOD 317 = 48
>
> und lediglich dieser KLEINE INTEGER (in diesen Fall) 48 wird benötigt!

Nur als kleine Randnotiz: Bei mir kommt da in vier verschiedenen 
Programmen (darunter der Windows-Taschenrechner) 259 raus. (Unter der 
Voraussetzung, dass mit ^ nicht wie in C das exklusive Oder, sondern das 
Potenzieren gemeint ist)

Hier eine elementare Implementation in C — die übrigens auch 259 liefert 
— welche ohne Multiplikation, Division und Modulo auskommt (mul, div und 
mod mit 2 rechne ich mal nicht mit, weil das einfachste Bitoperationen 
sind).

1

#include <stdio.h>

2

3

typedef unsigned T;

4

5

static T mod_mul (T n, T a, T b);

6

7

// Return a mod n im kleinsten, nicht-negativen Restsystem (T ist unsigned).

8

9

static T mod_norm (T n, T a)

10

{

11

    if (a < n)

12

        return a;

13

14

    if (n < 2)

15

        return 0;

16

17

    return mod_mul (n, a, 1);

18

}

19

20

// Return a*b mod n

21

22

static T mod_mul (T n, T a, T b)

23

{

24

    // Anstatt  "return (a * b) % n"  berechnen wir das Produkt von Hand,

25

    // was den Bereich erlaubter Moduli von  [sqrt (max_T)] auf

26

    // [max_T / 2] erweitert.

27

28

    // Im folgenden gehen wir davon aus, dass b normiert ist.

29

30

    b = mod_norm (n, b);

31

32

    for (T ab = 0;;)

33

    {

34

        if (a % 2 == 1)

35

        {

36

            ab += b;

37

            if (ab >= n)

38

                ab -= n;

39

        }

40

41

        if (a < 2)

42

            return ab;

43

        a = a / 2;

44

45

        b = b * 2;

46

        if (b >= n)

47

            b -= n;

48

    }

49

}

50

51

// Return a^k mod n

52

//

53

// Exponentiation mit dem gleichen Ansatz wie oben, nur dass

54

// anstatt eines Faktors der Exponent binaer expandiert wird.

55

56

static T mod_pow (T n, T a, unsigned k)

57

{

58

    if (n == 1)

59

        return 0;

60

61

    for (T a_k = 1;;)

62

    {

63

        if (k % 2 == 1)

64

            a_k = mod_mul (n, a, a_k);

65

66

        if (k < 2)

67

            return a_k;

68

        k = k / 2;

69

70

        a = mod_mul (n, a, a);

71

    }

72

}

73

74

int main (void)

75

{

76

    printf ("erg= %u\n", mod_pow (317, 4378, 120));

77

    return 0;

78

}

Negative Exponenten hab ich nicht durchexerziert, dazu nimmt man

https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Computing_multiplicative_inverses_in_modular_structures

Wer begrenzte Stellengenauigkeit nicht mag, der kann auch den guten 
alten "bc" bemühen. Gibts seit Anbeginn der Zeit auf jedem 
Unix/Linux-Maschinchen.
https://www.gnu.org/software/bc/

1

> bc

2

bc 1.06.95

3

Copyright 1991-1994, 1997, 1998, 2000, 2004, 2006 Free Software Foundation, Inc.

4

This is free software with ABSOLUTELY NO WARRANTY.

5

For details type `warranty'.

6

(4378^120)%317

7

259

Und wer es lieber umgekehrt polnisch mag, der nimmt "dc".

A. K. schrieb:
> Wer begrenzte Stellengenauigkeit nicht mag, der kann auch den guten
> alten "bc" bemühen. Gibts seit Anbeginn der Zeit auf jedem
> Unix/Linux-Maschinchen.

Das war eins der Programme, mit denen ich's ausgerechnet hab. Ein 
anderes war Python, das diese Begrenzung auch nicht hat.

sorry, aber 40000^120 ist nicht sonderlich groß

Ich empfehle die Bibliothek MPArith von Wolfgang Ehrhardt
http://www.wolfgang-ehrhardt.de/mp_intro.html für Delphi/Freepascal.

Da geht es glaube ich bis 10E1.000.063.

MaWin schrieb:
> Also für mich ist das eine recht große Zahl.

Ist endlich, also klein :-)

MaWin schrieb:
> Mike B. schrieb:
>> sorry, aber 40000^120 ist nicht sonderlich groß
>
> Also für mich ist das eine recht große Zahl.
>>>> 40000**120
> 176684706477838432958329750074291851582748389687561895812160620129261977 
600000000000000000000000000000000000000000000000000000000000000000000000 
000000000000000000000000000000000000000000000000000000000000000000000000 
000000000000000000000000000000000000000000000000000000000000000000000000 
000000000000000000000000000000000000000000000000000000000000000000000000 
000000000000000000000000000000000000000000000000000000000000000000000000 
000000000000000000000000000000000000000000000000000000000000000000000000 
0000000000000000000000000000000000000000000000000

überschaubar

eine 10^3200 braucht schon ein ganze 43*80-Seite...

SCM version 5e5, Copyright (C) 1990-2006 Free Software Foundation.
SCM comes with ABSOLUTELY NO WARRANTY; for details type `(terms)'.
This is free software, and you are welcome to redistribute it
under certain conditions; type `(terms)' for details.
;loading /usr/share/slib/require
;done loading /usr/share/slib/require.scm
;loading /usr/share/slib/require
;done loading /usr/share/slib/require.scm
;loading /usr/lib/scm/Link
;done loading /usr/lib/scm/Link.scm
;loading /usr/lib/scm/Transcen
;done loading /usr/lib/scm/Transcen.scm
> (mod (expt 4378 120) 317)
259

Mike B. schrieb:
> sorry, aber 40000^120 ist nicht sonderlich groß
>
> Ich empfehle die Bibliothek MPArith von Wolfgang Ehrhardt
> http://www.wolfgang-ehrhardt.de/mp_intro.html für Delphi/Freepascal.
>
> Da geht es glaube ich bis 10E1.000.063.

Wieso bekomm ich dafür eine negative Bewertung?

Weil ich satirisch meinte, dass die Zahl nicht besonders groß sei?
etwas überempfindlich?

Der Witz an der Sache ist doch, dass überhaupt keine "großen" Zahlen für 
die Berechnung benötigt werden:

Die größte Zahl, die in der Berechnung und in allen Zwischenschritten 
vorkommt, ist die 4378.  Nachdem diese Reduziert ist, braucht's keine 
größere Zahl mehr als 2*317 = 634; und das alles ließe sich sogar 
komfortabel mit 16-Bit int implementieren.

Und der TO hat das auch gerafft und ist glücklich damit:

Baeri B. schrieb:
> was will man mehr...
>
> tausend dank :)

Natürlich kann man mit roher Gewalt 4378^120 ausrechnen und dass dann 
mod 317 reduzieren, indem man es in Python eintippt oder wo auch immer. 
Der gewünschte Lerneffekt bzgl. des C++ Projekts des TO ist aber gleich 
Null...

Aber immerhin ist der Groschen meim TO gefallen :-))

Martin K. schrieb:
> Auch wenn der TO jetzt seine Lösung hat, bleibt aber schon die Frage,
> wie man das grundsätzlich machen würde.

Grundsätzlich würde ich mich im Bereich der "Arbitrary-precision 
arithmetic" Bibliotheken umsehen. Gibt es für viele Programmiersprachen.

https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic