mikrocontroller.net

Forum: PC-Programmierung Große Ganzzahlen


Autor: Bill (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo, ich muß im Rahmen meines Studiums eine Funktion implementieren 
die eine sehr große Zahl speichern kann. Diese Zahl überschreitet die 
Größe eines Longdatentyps um ca. das 4-fache. Dies sollte in der 
Programmiersprache C geschehen.

Wäre sehr dankbar für zielführende Antworten.

Gruß Bill

Autor: Klaus Kehrer (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hi Bill,
schau mal bei
   http://gmplib.org/
vorbei.

Ich habe mit DEV-C++ und GNU MP einen RSA-Algorithmus für Primzahlen
bis 100 Stellen programmiert.

Mit welchen Compiler bzw. welcher Entwicklungsumgebung arbeites Du ?

Bye Klaus

Autor: Rolf Magnus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Diese Zahl überschreitet die Größe eines Longdatentyps um ca. das
> 4-fache.

Dann nimm long long. Damit kannst du Werte speichern, die mindestens um 
das 4294967296-fache größer sind als das, was ein long speichern kann.

Autor: noname (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Musst du mit dem Zeug auch rechnen können oder reicht das 
speichern/ausgeben? Dann würde ich das in mehreren Kaskaden aufbauen...

Autor: Bill (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Geht das mit dem long long?
Wie funktioniert das genau? Wird da einfach der Speicher multipliziert?

Es war die Rede von "aufnehmen" also nur speichern. Wäre aber schon 
sinnvoll wenn man auch damit rechnen kann. Was soll ich sonst mit so 
einer Zahl?

Das ist die Beispielzahl:

99883728765498717635278948
76266637477652673878283737
38828373723772734819324498
37593787678674732776834782
78627427387432872478347625
78342983984044092549834789
21099579378042348193244983
75937876786747327768347828
375937876786747327768347827

Autor: Bill (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Visual Studio 6.0

Autor: Christoph __ (chris)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Geht das mit dem long long?
> Wie funktioniert das genau? Wird da einfach der Speicher multipliziert?
Nein, "long long" ist auf gängigen Architekturen ein 64-Bit-Integer.

> Es war die Rede von "aufnehmen" also nur speichern. Wäre aber schon
> sinnvoll wenn man auch damit rechnen kann. Was soll ich sonst mit so
> einer Zahl?
Einlesen, speichern und wieder ausgeben. Das wäre eine mögliche 
Verwendung einer langen Zahl, ohne rechnen zu müssen.

> Das ist die Beispielzahl: [...]
Die ist aber sehr viel mehr als "4 Mal so groß wie long".
Wie der erste Poster schon geschrieben hat: Schau dir GMP an. Damit sind 
solche Zahlen kein Problem.

Allerdings würde ich dir raten auf Visual Studio 6 zu verzichten, und 
stattdessen entweder Visual Studio 2005 Express oder Code::Blocks zu 
nehmen (beides kostenlos erhältlich). Visual Studio 6 ist schon ziemlich 
alt; für C wird es vielleicht noch reichen, aber für modernen C++-Code 
ist es leider nicht brauchbar.

Bei manchen Problemstellungen kann es auch sinnvoll sein, einen Wechsel 
der Programmiersprache in Erwägung zu ziehen. Es gibt zahlreiche 
Sprachen, die mit großen Ganzzahlen rechnen können wie mit normalen 
(Python, LISP, Haskell, um nur ein paar zu nennen). Wenn es natürlich 
eine Aufgabe im Studium ist, die die Programmiersprache explizit 
vorgibt, dann ist das leider keine Option.

Autor: Bill (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Visual Studio ist Pflicht.

Das ist ein Grundlagenkurs und wir sollen keine vorgefertigte Libary 
benutzen. Wenn ich das für zu Hause bräucht wurde ich das auch nehmen.

Hat jemand eine Idee wie das mit einem Array funktioniert?

Autor: Thomas (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Programmiere es doch so, wie du es schriftlich rechnen würdest.

In C++ kannst du dir mit einer eigenen Klasse und Operatorüberladung die 
Grundrechenarten zurechtbasteln. Also die Zahl als String speichern, und 
in den Funktionen dann rechnen.

Kommt drauf an wie schnell das Ganze nachher sein soll...

Autor: Bill (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Die Geschwindigkeit ist egal.

Es sollte trotzdem in C sein.

Ich glaub ich les mit Getchar ein und speicher in einer Funktion die 
nach jedem aufruf ein neues struct erzeugt. Würde das funktionieren?

Autor: ... (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Nurmal so nebenbei: "long long" gibts bei VC6 nicht, da heißt der 
entsprechende Datentyp "__int64".

CU

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Bill wrote:
> Visual Studio ist Pflicht.
>
> Das ist ein Grundlagenkurs und wir sollen keine vorgefertigte Libary
> benutzen. Wenn ich das für zu Hause bräucht wurde ich das auch nehmen.
>
> Hat jemand eine Idee wie das mit einem Array funktioniert?


Wenns ein Grundlagenkurs ist, dann ist das sicherlich nach
folgendem Muster gemeint:

Du hast ein Array (sagen wir mal der Länge 40) von int.
In jedem Arrayelement wird eine Ziffer der Zahl gespeichert.
Und es liegt jetzt an dir darauf eine Arithmetik aufzubauen.

Sowas in der Art

int a[40];
int b[40];

mal angenommen in den Arrays befindet sich sowas

  a
  +---+---+---+---+---+---+---+---+---+- ... -+---+---+---+
  | 8 | 7 | 3 | 9 | 4 | 0 | 0 | 0 | 0 |       | 0 | 0 | 0 |
  +---+---+---+---+---+---+---+---+---+- ... -+---+---+---+

  b
  +---+---+---+---+---+---+---+---+---+- ... -+---+---+---+
  | 3 | 1 | 9 | 2 | 0 | 0 | 0 | 0 | 0 |       | 0 | 0 | 0 |
  +---+---+---+---+---+---+---+---+---+- ... -+---+---+---+

Das seien de Zahlen
  a = 49378
  b =  2913

(an Array Position 0 stehen also die Einer, an 1 die Zehener, usw.)

Deine Aufgabe ist es nun eine Addition zu machen.
Wie machst du das?
Genauso wie du es in der Grundschule gelernt hast.

  3 + 8 ergibt 11.  Da 11 größer als 9 ist kommt an diese
  Stelle im Ergebnis eine 1 und du merkst dir eine 1 als
  Übertrag in die nächste Stelle

  7 + 1 ergibt 8 PLUS der Übertrag aus der vorhergehenden Stelle
  (der da 1 war) macht 9
  9 ist kleiner als 10, also wird diese Stelle im Ergebnis zu
  9 und der Übertrag in die nächste Stelle ist 0

  9 + 3 macht 12 PLUS der Übertrag von der vorhergehenden Stelle
  (welcher 0 war) macht 12.
  12 ist wieder größer als 9, daher kommt in diese Stelle eine 2
  und du hast einen Übertrag in die nächste Stelle von 1.

  und so geht das weiter bis alle 40 Stellen abgearbeitet sind
  (in einer Schleife).


Als Ergebnis hast du dann

  a
  +---+---+---+---+---+---+---+---+---+- ... -+---+---+---+
  | 8 | 7 | 3 | 9 | 4 | 0 | 0 | 0 | 0 |       | 0 | 0 | 0 |
  +---+---+---+---+---+---+---+---+---+- ... -+---+---+---+

  b
  +---+---+---+---+---+---+---+---+---+- ... -+---+---+---+
  | 3 | 1 | 9 | 2 | 0 | 0 | 0 | 0 | 0 |       | 0 | 0 | 0 |
  +---+---+---+---+---+---+---+---+---+- ... -+---+---+---+

  Ergebnis
  +---+---+---+---+---+---+---+---+---+- ... -+---+---+---+
  | 2 | 9 | 2 | 2 | 5 | 0 | 0 | 0 | 0 |       | 0 | 0 | 0 |
  +---+---+---+---+---+---+---+---+---+- ... -+---+---+---+

Welches die Zahl  52292 repräsentiert.

Bei der Ausgabe must du nur aufpassen, dass du die Zahl
beginnend mit der Arrayposition 39 ausgibst. Dann kommt
alles richtig raus.

Bei der Eingabe musst du darauf achten, dass du die Ziffern
in der richtigen Reihenfolge in das Array schreibst. Ach
ja: Du liest eine Zahl wie 234 nicht mehr als 1 int ein, sondern
als eine Folge von Ziffern (Character) die du entsprechend
umgewandelt (einfach eine '0' von jeder Ziffer abziehen) an
die richtigen Arraypositionen schreibst.

Damit was weitergeht würde ich dir mal empfehlen die Eingabe
auf später zu verschieben und dich nur mal mit der Addition
bzw. Ausgabe von Zahlen zu beschäftigen. Die Eingabe kann
knifflig werden.

Wenn du Addition fertig hast (Subtraktion geht nach dem
gleichen Schema), dann beschäftigst du dich mal mit der
Multiplkation. Erinnere dich daran, wie ihr das in der
Grundschule gelernt habt. Dann nimmst du Papier und Bleistift
und probierst ein paar Beispiele durch wobei du dir bei jedem
Schritt die Frage stellst: Gibt es da irgendwelche Besonderheiten.
Dann sollte es nicht mehr schwer sein. (Achtung: Du wirst eine
Multiplikation mit 10 brauchen. Mit obiger Darstellung braucht
da nichts gerechnet werden, sondern das ist eine einfache
Umkopieraktion im Array. Das Ergebnis von

  a
  +---+---+---+---+---+---+---+---+---+- ... -+---+---+---+
  | 8 | 7 | 3 | 9 | 4 | 0 | 0 | 0 | 0 |       | 0 | 0 | 0 |
  +---+---+---+---+---+---+---+---+---+- ... -+---+---+---+

mal 10 lautet

  a
  +---+---+---+---+---+---+---+---+---+- ... -+---+---+---+
  | 0 | 8 | 7 | 3 | 9 | 4 | 0 | 0 | 0 | 0 |       | 0 | 0 |
  +---+---+---+---+---+---+---+---+---+- ... -+---+---+---+

also alle Stellen um 1 nach rechts verschoben und eine 0 in
die Einerstelle.


Ist eine Standardübung für das Arbeiten mit Arrays.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Oops. Hab ganz übersehen, dass es da ums Studium geht.
Ach komm: Als über 18-jähriger wirst du doch ein bischen
Fantasie haben?

Autor: Bill (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Danke Karl Heinz das du dir so viel Mühe gegeben hast, aber der Speicher 
für die Zahl soll dynamisch sein und es ist keine Übung zu Arrays :-)

Was hat das Alter mit dem Programmieren zu tun?

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Bill wrote:
> Danke Karl Heinz das du dir so viel Mühe gegeben hast, aber der Speicher
> für die Zahl soll dynamisch sein und es ist keine Übung zu Arrays :-)
>

Dann mach ihn dynamisch :-)
Was ist vorgegeben: dynamisches Array oder vielleicht
eine 'linked list'. Wenn linked list, 'single linked list'
oder 'double linked list'? Oder vielleicht eine ganz andere
Datenstruktur?
Steht in den Angaben was ob du jedes Digit einzeln speichern musst,
oder ob man auch Byteweise zusammenfassen kann (nicht das das
dadurch einfacher würde, braucht nur weniger Speicher).

> Was hat das Alter mit dem Programmieren zu tun?

Mit Programmieren nicht viel. Aber sehr viel mit:
an der Kittelfalte hängen und ja keine eigenen Ideen haben.
Und insbesondere letzteres hat wieder sehr viel mit
Programmieren zu tun: neben Handwerkszeug ist etwas
Fanatasie und 'Ideen haben' zum Programmieren absolut
notwendig.

Du bist der Programmierer: Denk dir was aus und setzte es um.
Eine grundsätzliche Idee hast du ja jetzt.

Autor: Bill (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Danke schön

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.