Modulo von großer Zahl

[Tasi D. (tasidevil)]

Ich hab ein Problem. Ich will von einer ziemlich großen Zahl den Rest 
mithilfe von Modulo berechnen.
Die Zahl ist abgespeichert in einem char string. (24-Stellen)
char[0]='1'
char[1]='4'
.
.
.

Hättet ihr einen Ansatz für mich?

[Lutz H. (luhe)]

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

[Rechenknecht (Gast)]

Lutz H. schrieb:
> So programmieren.

Eher nicht, jedenfalls wenn das nicht mal wieder irgendwelche 
Hausaufgaben sind oder man unbedingt "selber machen" will. Vernünftig 
wäre nämlich, nicht ständig das Rad neu zu erfinden und stattdessen eine 
bestehende Bibliothek für "big numbers" in der gewünschten Sprache zu 
benutzen.

Für C wäre das z.B. GMP (gmplib.org).

[nocheinGast (Gast)]

Ja, oder sich einfach auf eingebaute Typen verlassen. GCC kann 
folgendes, bei anderen Compiler funktioniert das ähnlich:

#include <stdint.h>
#include <stdio.h>
#include <string.h>

int main() {
  __uint128_t zahl = 0;
  char const* string = "123456789012345678901234";

  for (auto i = 0; i < strlen(string); ++i) {
    zahl += (string[i] - '0');
    zahl *= 10;
  }

  zahl /= 10;

  zahl %= 42;

  printf("%d\n", (uint64_t)zahl);
}

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

[Kaj (Gast)]

Restklassenring
https://de.wikipedia.org/wiki/Restklassenring

Danach kannst du die Zahl durch eine beliebige andere Zahl aus dem 
entsprechenden Restklassenring ersetzten.

Beispiel: 13 % 4
Es spielt keine Rolle, ob du nun 13 % 4 oder 5 % 4 oder -3 % 4 rechnest, 
das Ergenis ist das selbe. Bei negativen Zahlen muss man in C/C++ 
aufpassen.

Du musst also nur feststellen, in welchem Restklassenring sich deine 
Zahl befindet, und deine Zahl gegen eine andere aus dem Ring ersetzen.

[Christian M. (Gast)]

Hallo Tasi,

willst Du durch irgendwelche Zahlen teilen, oder immer durch die 
Gleiche?

Gruss Chregu

[Tasi D. (tasidevil)]

nocheinGast schrieb:

>

> #include <stdint.h>
> #include <stdio.h>
> #include <string.h>
> 
> int main() {
>   __uint128_t zahl = 0;
>
> 
>

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

[Rainer B. (katastrophenheinz)]

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

[Johann L. (gjlayde)]

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

// Input: N, M
// Output R := N mod M

R := 0
B := 1
while N != 0
    C := N mod 2
    N := N div 2

    if C != 0
        R := R + B
        if R >= M
            R := R - M

    B := 2 * B
    if B >= M
        B := B - M

[Kaj G. (Firma: RUB) (bloody)]

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

__uint128_t

und nicht

uint128_t

und compiliert bei mir ohne Probleme mit dem GCC.

[Lutz H. (luhe)]

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

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

[S. R. (svenska)]

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.

[Christian M. (Gast)]

Rainer B. schrieb:
> 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-)

wohl noch durch 10^n :-))

Gruss Chregu

[Rainer B. (katastrophenheinz)]

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

[Johann L. (gjlayde)]

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:
 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <assert.h>

unsigned mod (char *digits, unsigned mod)
{
    assert (mod <= UINT_MAX / 10);

    unsigned rest = 0;
    unsigned mod10 = 1;
    size_t n_digits = strlen (digits);
    
    for (size_t n = 0; n < n_digits; n++)
    {
        unsigned dig = digits[n] - '0';
        rest = (rest + dig * mod10) % mod;
        mod10 = (10 * mod10) % mod;
    }

    return rest;
}

 
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:
 

unsigned mod_big_endian (char *digits, unsigned mod)
{
    assert (mod <= UINT_MAX / 10);

    unsigned rest = 0;
    size_t n_digits = strlen (digits);
    
    for (size_t n = 0; n < n_digits; n++)
    {
        unsigned dig = digits[n] - '0';
        rest = (10 * rest + dig) % mod;
    }

    return rest;
}

[MH (Gast)]

Hier eine Bibliothek für .Net

http://www.sse-web.de/downloads/c-klassenbibliothek-uint8192/

[Yalu X. (yalu) (Moderator)]

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.

[Georg (Gast)]

Yalu X. schrieb:
> ist es
> wohl besser, direkt auf der ASCII-Darstellung der Zahl zu operieren

Das lernt halt heute keiner mehr, aber man kann ja nach schriftlicher 
Division googeln, so schwer zu begreifen ist das nicht.

Georg

[Christian M. (Gast)]

Rechenknecht schrieb:
> Für C wäre das z.B. GMP (gmplib.org).

Ja da bin ich auch draufgekommen durch:

https://runtimebasic.net/Projekt:BigNum

Ist ein Stand-Alone-Programm. Vielleicht was für den TO.

Gruss Chregu