Modulo von großer Zahl

Wie macht man das mit Dezimalrechnung, Bleistift und Papier?
So programmieren.

nocheinGast schrieb:

>

1

> #include <stdint.h>

2

> #include <stdio.h>

3

> #include <string.h>

4

> 

5

> int main() {

6

>   __uint128_t zahl = 0;

7

>

8

> 

9

>

>
> Das ist nur ein Proof of Concept... ;)

uint128_t habe ich noch nie von gehört. Aber mein Compiler kennt den 
Datentyp auch gar nicht. Oder wie implementiere ich den in das Programm?

Christian M. schrieb:
> willst Du durch irgendwelche Zahlen teilen, oder immer durch die
> Gleiche?

Bei 24-stelliger Ausgangszahl würde ich mal vermuten: Immer die gleiche 
B-)

Für eine einfache Implementierung brauchst du folgende Grundarithmetik:

- Rechts-Schieben mit Carry ("mod 2" und "div 2" im Pseudo-Code)
- Links-Schieben ("2 *" im Pseudo-Code)
- Vergleich auf Größergleich " >= " und Ungleichheit " != "
- Addition " + " und Subtraktion " - "

1

// Input: N, M

2

// Output R := N mod M

3

4

R := 0

5

B := 1

6

while N != 0

7

    C := N mod 2

8

    N := N div 2

9

10

    if C != 0

11

        R := R + B

12

        if R >= M

13

            R := R - M

14

15

    B := 2 * B

16

    if B >= M

17

        B := B - M

Tasi D. schrieb:
> uint128_t habe ich noch nie von gehört. Aber mein Compiler kennt den
> Datentyp auch gar nicht.
Der Datentyp heisst ja auch

1

__uint128_t

und nicht

1

uint128_t

und compiliert bei mir ohne Probleme mit dem GCC.

Tasi D. schrieb:
> Aber mein Compiler kennt den
> Datentyp auch gar nicht

biginteger oder ähnliches, große Zahlen sind erst seit 2014 bekannt.

Kaj G. schrieb:
> Der Datentyp heisst ja auch __uint128_t und nicht uint128_t
> und compiliert bei mir ohne Probleme mit dem GCC.

GCC unterstützt die 128 Bit-Typen aber nicht für jedes Target. Wenn du 
für ein 64 Bit-Zielsystem baust, sollten sie aber immer dabei sein.

Ich tippe eher auf 97
https://www.iban.de/iban-pruefsumme.html

Wenn die Zahl in einem String gespeichert ist und der Modul wirklich so 
klein ist, dann ist die Hin- und Herwandlung zu 128-Bit int bereits fast 
mehr Aufwand als den Rest zu berechnen :-)

Beispiel in C99, das mit auf einem "normalen" PC mit 32-Bit int immerhin 
für Moduln bis 429496729 taucht:
 

1

#include <stdio.h>

2

#include <stdlib.h>

3

#include <string.h>

4

#include <limits.h>

5

#include <assert.h>

6

7

unsigned mod (char *digits, unsigned mod)

8

{

9

    assert (mod <= UINT_MAX / 10);

10

11

    unsigned rest = 0;

12

    unsigned mod10 = 1;

13

    size_t n_digits = strlen (digits);

14

15

    for (size_t n = 0; n < n_digits; n++)

16

    {

17

        unsigned dig = digits[n] - '0';

18

        rest = (rest + dig * mod10) % mod;

19

        mod10 = (10 * mod10) % mod;

20

    }

21

22

    return rest;

23

}

 
Dabei steht die Zahl als little-endian in String digits[], d.h. die 
kleinste Stelle kommt zuerst.  120 ist also dargestellt durch "021". 
Und für big-endian ist's genauso einfach:
 

1

unsigned mod_big_endian (char *digits, unsigned mod)

2

{

3

    assert (mod <= UINT_MAX / 10);

4

5

    unsigned rest = 0;

6

    size_t n_digits = strlen (digits);

7

8

    for (size_t n = 0; n < n_digits; n++)

9

    {

10

        unsigned dig = digits[n] - '0';

11

        rest = (10 * rest + dig) % mod;

12

    }

13

14

    return rest;

15

}

MH schrieb:
> Hier eine Bibliothek für .Net
>
> http://www.sse-web.de/downloads/c-klassenbibliothek-uint8192/

Man kann auch die Klasse BigInteger aus der .NET-Klassenbibliothek
verwenden.

Aber auch hier gilt (erst recht) der Einwand von Johann:

Wenn der Modul im normalen Integer-Format darstellbar ist und mit der
Zahl nicht noch weitere Berechnungen ausgeführt werden müssen, ist es
wohl besser, direkt auf der ASCII-Darstellung der Zahl zu operieren.