Rechnen mit extrem großen Zahlen

[Baeri B. (baeri)]

Hallo ich habe ein C++ (lern) Projekt bei dem ich mit sehr großen 
"Exponenten" (ich hoffe das schreibt man so) Rechnen muss / naja eher 
WILL :) ...

ich bin noch in der "Lernphase" und möchte verstehen wie man so ein 
"Problem" angeht. Ich arbeite mit Code::Blocks und habe mir ein paar 
Grundkenntnisse angeeignet.

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!

Vermutlich komme ich nicht drumrum noch eine "Library" einzubinden!? 
Wenn ja, woher bekomme ich die und wie mache ich das...

Vielen Dank für jeden Hinweis :)

[D. I. (Gast)]

Baeri B. schrieb:
> (4378^120) MOD 317 = 48
>
> und lediglich dieser KLEINE INTEGER (in diesen Fall) 48 wird benötigt!
>
> Vermutlich komme ich nicht drumrum noch eine "Library" einzubinden!?
> Wenn ja, woher bekomme ich die und wie mache ich das...

Das ist der passende Algorithmus für das Problem:

https://en.wikipedia.org/wiki/Modular_exponentiation

und in optimierter Form kombiniert man das mit:

https://en.wikipedia.org/wiki/Exponentiation_by_squaring

[Joey5337 (Gast)]

Schau dir mal an, ob sich die Modulo-Operation schon auf die Operanden 
deiner Rechnung anwenden lässt.

Bei + -  z.B.  ist es für das Ergebnis egal, ob die Summanden vorher 
zusätzlich nochmal modulo genommen wurden. Dito Multiplikation.

[Walter S. (avatar)]

ich würde die exponentiation schrittweise machen:

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

[Baeri B. (baeri)]

was will man mehr...

tausend dank :)

und wies wie Bayern so machen: bierchen ausgeb

[Rolf M. (rmagnus)]

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)

[Johann L. (gjlayde)]

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).

#include <stdio.h>

typedef unsigned T;

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

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

static T mod_norm (T n, T a)
{
    if (a < n)
        return a;

    if (n < 2)
        return 0;

    return mod_mul (n, a, 1);
}

// Return a*b mod n

static T mod_mul (T n, T a, T b)
{
    // Anstatt  "return (a * b) % n"  berechnen wir das Produkt von Hand,
    // was den Bereich erlaubter Moduli von  [sqrt (max_T)] auf
    // [max_T / 2] erweitert.

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

    b = mod_norm (n, b);
    
    for (T ab = 0;;)
    {
        if (a % 2 == 1)
        {
            ab += b;
            if (ab >= n)
                ab -= n;
        }
        
        if (a < 2)
            return ab;
        a = a / 2;
            
        b = b * 2;
        if (b >= n)
            b -= n;
    }
}

// Return a^k mod n
//
// Exponentiation mit dem gleichen Ansatz wie oben, nur dass
// anstatt eines Faktors der Exponent binaer expandiert wird.

static T mod_pow (T n, T a, unsigned k)
{
    if (n == 1)
        return 0;
        
    for (T a_k = 1;;)
    {
        if (k % 2 == 1)
            a_k = mod_mul (n, a, a_k);
            
        if (k < 2)
            return a_k;
        k = k / 2;
            
        a = mod_mul (n, a, a);
    }
}

int main (void)
{
    printf ("erg= %u\n", mod_pow (317, 4378, 120));
    return 0;
}

Negative Exponenten hab ich nicht durchexerziert, dazu nimmt man

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

[(prx) A. K. (prx)]

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/

> bc
bc 1.06.95
Copyright 1991-1994, 1997, 1998, 2000, 2004, 2006 Free Software Foundation, Inc.
This is free software with ABSOLUTELY NO WARRANTY.
For details type `warranty'.
(4378^120)%317
259

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

[Dr. Sommer (Gast)]

Man kann die gmplib benutzen, wekche mit beliebig großen Zahlen rechnen 
kann, das erspart die selbst-Implementation:
https://gmplib.org/

[... (Gast)]

A. K. schrieb:
> Wer begrenzte Stellengenauigkeit nicht mag, der kann auch den guten
> alten "bc" bemühen. Gibts seit Anbeginn der Zeit auf jedem...
> Und wer es lieber umgekehrt polnisch mag, der nimmt "dc".

Danke für den Hinweis. Ich benutze Linux schon eine Weile, aber das war 
mir neu.

[Rolf M. (rmagnus)]

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.

[MaWin (Gast)]

Python 3.5.2+ (default, Nov 22 2016, 01:00:20)
[GCC 6.2.1 20161119] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> (4378 ** 120) % 317
259

[fritz (Gast)]

Hallo zusammen,

ich habe gerade mal ausprobiert, ob mein Rechner auch Python kann.
Er kann, und folgendes kommt heraus:

fritz@linux-ot5a:~> python
Python 2.7.12 (default, Jul 01 2016, 15:34:22) [GCC] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> (4378 ** 120) % 317
259L

Aber was bedeutet das "L" hinter der 259?

[MaWin (Gast)]

fritz schrieb:
> Aber was bedeutet das "L" hinter der 259?

Das bedeutet, dass dies ein long integer ist und somit länger als die 
native Wortlänge der Maschine ist (bedingt durch die Berechnung).
In Python 3 sind alle integers long ints und diese Unterscheidung fällt 
weg.

[Mike B. (mike_b97)]

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.

[Jemand (Gast)]

Dr. Sommer schrieb:
> Man kann die gmplib benutzen, wekche mit beliebig großen Zahlen
> rechnen
> kann, das erspart die selbst-Implementation:
> https://gmplib.org/

Oder noch besser: MPFR
http://www.mpfr.org/

[MaWin (Gast)]

Mike B. schrieb:
> sorry, aber 40000^120 ist nicht sonderlich groß

Also für mich ist das eine recht große Zahl.

>>> 40000**120
1766847064778384329583297500742918515827483896875618958121606201292619776000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

[Johann L. (gjlayde)]

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

Ist endlich, also klein :-)

[Mike B. (mike_b97)]

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...

[Alexander S. (alesi)]

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. (mike_b97)]

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?

[Johann L. (gjlayde)]

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. (mkmannheim)]

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

[Mark B. (markbrandis)]

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

[flump (Gast)]

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.

Naja, entweder schreibt man eine eigene Klasse die sowas kann oder man 
verwendet eine fertige von jemand anderem.

Ich habe vor Jahren mal eine Klasse zum rechnen mit großen Zahlen 
geschrieben, die Zahlen als Strings speichert und auf diese dann 
schriftliche Addition, Subtraktion, Multiplikation und Division 
anwendet. So wie ich es vor langer Zeit in der Grundschule gelernt habe. 
Das war natürlich unglaublich langsam, aber lustig war es trotzdem und 
funktioniert hat es auch.