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?
Wie macht man das mit Dezimalrechnung, Bleistift und Papier? So programmieren.
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).
Ja, oder sich einfach auf eingebaute Typen verlassen. GCC kann folgendes, bei anderen Compiler funktioniert das ähnlich:
1 | #include <stdint.h> |
2 | #include <stdio.h> |
3 | #include <string.h> |
4 | |
5 | int main() { |
6 | __uint128_t zahl = 0; |
7 | char const* string = "123456789012345678901234"; |
8 | |
9 | for (auto i = 0; i < strlen(string); ++i) { |
10 | zahl += (string[i] - '0'); |
11 | zahl *= 10; |
12 | }
|
13 | |
14 | zahl /= 10; |
15 | |
16 | zahl %= 42; |
17 | |
18 | printf("%d\n", (uint64_t)zahl); |
19 | }
|
Das ist nur ein Proof of Concept... ;)
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.
Hallo Tasi, willst Du durch irgendwelche Zahlen teilen, oder immer durch die Gleiche? Gruss Chregu
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 |
:
Bearbeitet durch User
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.
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
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 | }
|
:
Bearbeitet durch User
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.
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
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
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.