C - speichersparen/ansatz

[bleicher]

Grüße,
stehe gerade vor einer seltsamen Aufgabe -
2 Zahlen sind als char-String einzulesen und danach zu addieren oder zu multipliezieren

!!! größte zu evrarbeitende zahl sei 10^1000-1 (also 999 neuner)

Addition geht noch - Ergebniss wird höchstens 1000stellig, und es kann "von rechts nach links" wie auf einem "blatt papier" stelle für stelle addiert werden.

aber wie verfährt man mit multiplikation? mache ich das "wie auf papier" werde ich bis zu 999  "999stellige" zahlen addieren müssen, das Ergebnis kann bis zu 1998-stellen haben

es wäre extrem rechenaufwendig, zudem müsste ic hdie riesiegen arrays im voraus reservieren.

was  macht man aber in C in solchen fällen? arrays variabler-länge lassen sich ja nicht definieren, bzw - ich weiss nciht wie,
was wäre der ansatz?

paar stichwörter zum googeln wären nett^^

MFG
bleicher

[MudGuard]

Hi,

stehe gerade vor einer seltsamen Aufgabe -
2 Zahlen sind als char-String einzulesen und danach zu addieren oder zu multipliezieren

aber wie verfährt man mit multiplikation? mache ich das "wie auf papier" werde ich bis zu 999  "999stellige" zahlen addieren müssen, das Ergebnis kann bis zu 1998-stellen haben

Richtig, die maximale Stellenzahl des Ergebnisses einer Multiplikation einer n- und einer m-stelligen Zahl ist (n+m)-stellig.

Die 999 zu addierenden Zahlen sind ja nur max. 10 verschiedene Zahlen (die entsprechend verschoben auf's Ergebnis zu addieren sind) - je eine Ziffer multipliziert mit der einen Zahl.

Eine davon ist uninteressant, nämlich die 0. Für die Ziffer 1 hast Du die Zahl eh schon gespeichert. Bleiben also noch 8 zusätzlich zu speichernde Zwischenergebnisse.

Jetzt in einer Schleife über die zweite Zahl laufen, bei jeder Ziffer die Verschiebung um 1 erhöhen und falls die Ziffer nicht 0 ist, das der Ziffer entsprechende Zwischenergebnis auf das bisherige Ergebnis passend verschoben draufaddieren.

Um Speicherplatz für die Zwischenergebnisse (1 * erste Zahl, 2 * erste Zahl, ... 9 * erste Zahl) zu sparen, kann man das Kommutativgesetz ausnutzen und ggf. die Zahlen vertauschen, so daß die Zwischenergebnisse für die kürzere der beiden Zahlen berechnet werden - dafür muß dann die Schleife über die längere Zahl laufen ...

cu,
Andreas

[Alexander (HH)]

Moin Moin!

was  macht man aber in C in solchen fällen? arrays variabler-länge lassen sich ja nicht definieren, bzw - ich weiss nciht wie,

<murmel>Als ob dieser überdrehte Macro-Assembler überhaupt so etwas wie Arrays oder Strings unterstützen würde ...</murmel>

Arrays beliebiger Größe simulierst Du, inden du den benötigten Speicherplatz irgendwo reservierst (typischerweise mit malloc/calloc) und dann mit Pointer-Arithmetik in dem Speicherbereich die Daten unterbringst. Wenn Du die Arrays nicht mehr benötigst, mußt Du die Reservierung wieder aufheben (free), aber bitte nur einmal, ansonsten demoliert die sogenannte Speicherverwaltung in aller Regel ihre internen Strukturen und reißt irgendwann Dein Programm ins Nirvana, typischerweise beim nächsten impliziten oder expliziten Aufruf von malloc oder free. Verkneifst Du Dir das Aufheben der Reservierung, geht Deinem Programm irgendwann der Speicher aus ("memory leak").

Wie viele Elemente Dein Array enthält, und für wie viele Elemente Platz ist, mußt Du Dir allerdings selbst merken, C hilft Dir dabei nicht. Für die Elemente-Anzahl kannst Du alternativ wie bei der String-Karrikatur eine Endmarke benutzen, die sonst in der Array-Simulation nicht vorkommen darf. Wie viel Speicher ein einzelnes Element benötigt, kannst Du über die sizeof-Funktion herausfinden, den gesamten benötigten Speicherplatz ermittelst Du per Multiplikation mit der maximalen Elementanzahl.

Wenn Die Array-Elemente sehr unterschiedliche Größen haben, oder sich ihre Größe zur Laufzeit auch noch ändert, kannst Du stattdessen auch einfach oder doppelt verkettete Listen benutzen, oder einen  binären (Such-)baum.

Genug Suchbegriffe?

Alexander

[Tom]

Hello,

Arrays beliebiger Größe [...]

sind da bei C nicht die Segmentgrenzen zu beachten?

Liebe Grüße aus dem schönen Oberharz

Tom vom Berg

[Alexander (HH)]

Moin Moin!

sind da bei C nicht die Segmentgrenzen zu beachten?

Nö, wieso? Bei DOS und 16-Bit-Windows vielleicht, aber das hat nichts mit C zu tun, sondern ist eine Einschränkung der genannten Plattformen. Auf einem x86-64-System mit passendem OS sollten auch Terabytes am Stück kein Problem sein.

Alexander

[Christian Seiler]

Hallo Alexander,

sind da bei C nicht die Segmentgrenzen zu beachten?

Nö, wieso? Bei DOS und 16-Bit-Windows vielleicht, aber das hat nichts mit C zu tun, sondern ist eine Einschränkung der genannten Plattformen. Auf einem x86-64-System mit passendem OS sollten auch Terabytes am Stück kein Problem sein.

Und selbst unter DOS und 16-Bit-Windows sollten Segmentgrenzen kein Problem sein - der Compiler sollte normalerweise Assembler-Code generieren, der das automatisch berücksichtigt. Kann natürlich sein, dass es Compiler gibt, die zu dämlich dafür sind.

Viele Grüße,
Christian

[Der Martin]

Hi,

»» > sind da bei C nicht die Segmentgrenzen zu beachten?
»» Nö, wieso? Bei DOS und 16-Bit-Windows vielleicht, ...
Und selbst unter DOS und 16-Bit-Windows sollten Segmentgrenzen kein Problem sein - der Compiler sollte normalerweise Assembler-Code generieren, der das automatisch berücksichtigt.

der Begriff "automatisch" ist hier mit Vorsicht zu genießen: Unter DOS und 16bit-Windows hatte man immer noch die leidige Wahl des Speichermodells (tiny, small, large, huge usw.), die für viele Programmierer ein Buch mit sieben Siegeln war.
Nur im Modell "huge" konnte man den zur Verfügung stehenden Speicher wirklich nutzen, ohne dass man durch die Segmentierung eingeschränkt war. Im Speichermodell "large", das oft als Default genommen wurde, konnte man zwar den gesamten Speicher nutzen, aber keine Strukturen oder Arrays, die einzeln größer als 64kB (=16bit-Segmentgröße) waren.

Kann natürlich sein, dass es Compiler gibt, die zu dämlich dafür sind.

Das relativiert diese Aussage ein wenig: Die Compiler konnten es, man musste ihnen nur richtig sagen, was man will ...

So long,
 Martin

[Tom]

Hello,

Kann natürlich sein, dass es Compiler gibt, die zu dämlich dafür sind.

Das relativiert diese Aussage ein wenig: Die Compiler konnten es, man musste ihnen nur richtig sagen, was man will ...

das fand ich nun doch spannender, als HTML und habe noch eine Weile die Suchmaschinen gequält :-)

http://software.intel.com/en-us/articles/intel-c-compiler-array-size-limit-on-ia-32/

Es ist eine allgemein verunsichernde Frage. Kaum ein Programmierer scheint die Mechanismen im Hintergrund wirklich zu kennen. Selbst Christian schreibt ja: "der Compiler sollte normalerweise Assembler-Code generieren...", hat also vermutlich auch noch nie nachgeschaut.

Ich möchte nochmals erinnern: Es ging um C, nicht um C++.

Nach der Lektüre vieler vieler Postings im Internet gehe ich jetzt davon aus, dass bei C die Grenze für ein dynamisch allokiertes Array bei 2^32 Bytes für die gesamte Struktur liegt (der Intel-Compiler macht ja sogar schon bei signed Integer schlapp), da die interne Adressierung scheinbar nur über das Displacement vorgenommen wird, das wiederum in ein Register passen muss.

Selbst für Maschinen mit 64-Bit-Architektur waren sich die Leute nicht einig. Da kann es natürlich dann auch am Compiler gelegen haben.

Ich würde mich freuen, wenn wir das Thema noch etwas vertiefen könnten.

Liebe Grüße aus dem schönen Oberharz

Tom vom Berg

[Der Martin]

Hallo Tom,

»» > Kann natürlich sein, dass es Compiler gibt, die zu dämlich dafür sind.
»» Das relativiert diese Aussage ein wenig: Die Compiler konnten es, man musste ihnen nur richtig sagen, was man will ...
das fand ich nun doch spannender, als HTML

nicht wahr ...

http://software.intel.com/en-us/articles/intel-c-compiler-array-size-limit-on-ia-32/

Was möchtest du mit diesem Artikel jetzt andeuten? Der geht von Grenzen aus, die für 32bit-Systeme gelten; eben waren wir noch in der 16bit-Welt.

Es ist eine allgemein verunsichernde Frage. Kaum ein Programmierer scheint die Mechanismen im Hintergrund wirklich zu kennen.

Ja, und das finde ich schade.

Selbst Christian schreibt ja: "der Compiler sollte normalerweise Assembler-Code generieren...", hat also vermutlich auch noch nie nachgeschaut.

Ich halte ihm angesichts seines Alters zugute, dass er möglicherweise mit 16bit-Systemen keine allzu intime Bekanntschaft mehr gemacht hat.

Ich möchte nochmals erinnern: Es ging um C, nicht um C++.

Das macht aber nichts, die Mechanismen sind dieselben.

Nach der Lektüre vieler vieler Postings im Internet gehe ich jetzt davon aus, dass bei C die Grenze für ein dynamisch allokiertes Array bei 2^32 Bytes für die gesamte Struktur liegt

Das ist keine prinzipbedingte Einschränkung von C, sondern des Compilers und der Plattform, auf der er läuft bzw. auf der die compilierte Anwendung laufen soll. By the way: Gibt es eigentlich C-Compiler, die auf Linux laufen, aber Windows-Executables erstellen?

(der Intel-Compiler macht ja sogar schon bei signed Integer schlapp), da die interne Adressierung scheinbar nur über das Displacement vorgenommen wird, das wiederum in ein Register passen muss.

Warum die Intel-Leute hier von 2GB als Grenze sprechen, kann ich nicht ganz nachvollziehen. Sicher, man kann argumentieren, dass das Displacement mit gesetztem MSB als negativ aufgefasst wird. Das wäre aber aufgrund des Wraparounds an der 4GB-Grenze des Adressraums auch egal. Vielleicht schreit die CPU dann schon "Protection Violation!"

Selbst für Maschinen mit 64-Bit-Architektur waren sich die Leute nicht einig. Da kann es natürlich dann auch am Compiler gelegen haben.

Haben die heutigen 64bit-CPUs (also IA64) einen 64bit-Adressbus, oder "nur" 64bit Datenbreite? Theoretisch müssten sie auch 64bit-Adressen haben, denn sonst könnten die ja auch wieder "nur" 4GB adressieren. Ich habe aber, ehrlich gesagt, keine Ahnung, wie die Speicherverwaltung und Segmentierung in IA64 organisiert ist. DASS es weiterhin eine Segmentierung gibt, wie auch in IA32, ist logisch, denn nur so kann man jeder Anwendung bzw. jedem Prozess seinen eigenen logischen Adressraum geben.

Ich würde mich freuen, wenn wir das Thema noch etwas vertiefen könnten.

Aber gern doch. :-)

Ciao,
 Martin

[Tom]

Hello Martin,

Selbst Christian schreibt ja: "der Compiler sollte normalerweise Assembler-Code generieren...", hat also vermutlich auch noch nie nachgeschaut.

Ich halte ihm angesichts seines Alters zugute, dass er möglicherweise mit 16bit-Systemen keine allzu intime Bekanntschaft mehr gemacht hat.

Naja, dahinter dürfen wir uns ja auch nicht verstecken und werden hier ständig unter Druck gesetzt, uns mit den modernen[tm] Techniken auseinanderzusetzen ;-))
BTW: auf einigen meiner alten Möhrchen verwende ich auch noch Office 97 und bin damit zufrieden...

Haben die heutigen 64bit-CPUs (also IA64) einen 64bit-Adressbus, oder "nur" 64bit Datenbreite? Theoretisch müssten sie auch 64bit-Adressen haben, denn sonst könnten die ja auch wieder "nur" 4GB adressieren. Ich habe aber, ehrlich gesagt, keine Ahnung, wie die Speicherverwaltung und Segmentierung in IA64 organisiert ist. DASS es weiterhin eine Segmentierung gibt, wie auch in IA32, ist logisch, denn nur so kann man jeder Anwendung bzw. jedem Prozess seinen eigenen logischen Adressraum geben.

Das ging aber beim 8088 auch mit schmalem Bus. Der hatte dann eben für jede Adresse zwei Ladezyklen. Der Speichercontroller hatte dann wieder 20 (sic!) Bit Breite.

bezüglich Intel-Architektur:
Dass der erreichbare Speicherraum für eine geschlossene Struktur erstmal von der Registerbreite abhängig ist, ist logisch. Für den Segmentanteil gibt es ja im Protected Mode keine wirkliche Segmentadresse, sondern einen Deskriptor. Darüber kann man also nicht mehr durch den zugewiesenen Speicherbereich wandern, weil jeder Descriptor einen anderen Speicherbereich signiert.

Es bleibt also nur der Offset-Anteil der effektiven Adresse, um durch den zugewisenen Block zu geistern.

Wenn der Compiler nun größere Blöcke allokieren wollte, müsste er sich dafür mehrere Deskriptoren besorgen, die im einfachsten Falle nebeneinanderliegende Speicherbereiche beschreiben.

Liebe Grüße aus dem schönen Oberharz

Tom vom Berg

[Der Martin]

Hi,

»» Haben die heutigen 64bit-CPUs (also IA64) einen 64bit-Adressbus, oder "nur" 64bit Datenbreite? Theoretisch müssten sie auch 64bit-Adressen haben, ...
Das ging aber beim 8088 auch mit schmalem Bus. Der hatte dann eben für jede Adresse zwei Ladezyklen. Der Speichercontroller hatte dann wieder 20 (sic!) Bit Breite.

ja, stimmt. Trotzdem hatte diese CPU "im Prinzip" einen 20bit-Adressbus, ebenso wie ein 8051 einen 16bit-Adressbus hat (von denen das höherwertige Byte im Multiplex mit dem Datenbus "rauskommt"), und Spar-CPUs wie der 386SX einen 32bit-Adressbus, der aber auch nur auf 16 Pins herausgeführt ist. Ich spreche vom internen, "logischen" Adressbus, der mit der äußeren physikalischen Beschaltung nicht identisch sein muss.

Dass der erreichbare Speicherraum für eine geschlossene Struktur erstmal von der Registerbreite abhängig ist, ist logisch. Für den Segmentanteil gibt es ja im Protected Mode keine wirkliche Segmentadresse, sondern einen Deskriptor.

... der seinerseits die physikalische Basisadresse und die Länge des Segments enthält.

Darüber kann man also nicht mehr durch den zugewiesenen Speicherbereich wandern, weil jeder Descriptor einen anderen Speicherbereich signiert.

Ja, das stimmt natürlich. Es ist aber gängige Praxis auf 32bit-Systemen, dass der virtuelle Adressraum, der der Anwendung zur Verfügung gestellt wird, in sich nicht mehr segmentiert ist und durchgehend mit einer linearen 32bit-Adresse erreichbar ist. Die Segmentregister sind dabei tatsächlich tabu für den Programmierer - ich meine tabu in dem Sinn, dass er damit auf keinen Fall Zeiger-Berechungen anstellen kann, wie es in der segmentierten 16bit-Umgebung (Real Mode) dieser CPUs gang und gäbe war.

Wenn der Compiler nun größere Blöcke allokieren wollte, müsste er sich dafür mehrere Deskriptoren besorgen, die im einfachsten Falle nebeneinanderliegende Speicherbereiche beschreiben.

Das wäre aber unerheblich: Der Compiler (und auch die Anwendung) kann und darf keine Annahmen über die tatsächliche Lage von Speicherblöcken im RAM machen. Ja, es kann sein, dass zwei Descriptoren tatsächlich zwei Bereiche beschreiben, die im RAM physikalisch lückenlos hintereinander liegen. Das weiß aber nur das Betriebssystem, nicht die Anwendung, und daher kann man aus dieser Tatsache (oder Annahme) keinen Nutzen ziehen, man muss die zwei Bereiche als vollständig getrennt und unabhängig betrachten.

So long,
 Martin

[Tom]

Hello,

»» Haben die heutigen 64bit-CPUs (also IA64) einen 64bit-Adressbus, oder "nur" 64bit Datenbreite? Theoretisch müssten sie auch 64bit-Adressen haben, ...
Das ging aber beim 8088 auch mit schmalem Bus. Der hatte dann eben für jede Adresse zwei Ladezyklen. Der Speichercontroller hatte dann wieder 20 (sic!) Bit Breite.

ist auch noch interessant in diesem Zusammenhang:
http://de.wikipedia.org/wiki/X86-Prozessor#64_Bit

Liebe Grüße aus dem schönen Oberharz

Tom vom Berg

[Jens Holzkämper]

Tach,

By the way: Gibt es eigentlich C-Compiler, die auf Linux laufen, aber Windows-Executables erstellen?

GCC natürlich, im speziellen vermutlich MinGW.

Haben die heutigen 64bit-CPUs (also IA64)

Meinst du wirklich IA64 alias Itanium oder AMD64 alias x86-64 alias IA-32e alias EM64T alias Intel 64?

einen 64bit-Adressbus, oder "nur" 64bit Datenbreite?

Itanium hat 64 Bit, bei AMD64 ist das komplizierter: http://en.wikipedia.org/wiki/X86-64#Virtual_address_space_details.

mfg
Woodfighter

[Der Martin]

Hallo Jens,

»» By the way: Gibt es eigentlich C-Compiler, die auf Linux laufen, aber Windows-Executables erstellen?
GCC natürlich, im speziellen vermutlich MinGW.

danke für den Hinweis - ich wusste nicht, dass der auch als Cross-Compiler im Umlauf ist.

»» Haben die heutigen 64bit-CPUs (also IA64)
Meinst du wirklich IA64 alias Itanium oder AMD64 alias x86-64 alias IA-32e alias EM64T alias Intel 64?

Letztere Gruppe. Mir war aber nicht bekannt, dass es da Unterschiede gibt, ich hielt IA64 ebenso für ein Synonym. Man lernt nie aus. :-)

So long,
 Martin

[Jens Holzkämper]

Tach,

danke für den Hinweis - ich wusste nicht, dass der auch als Cross-Compiler im Umlauf ist.

der GCC ist immer ein Cross-Compiler allerdings im Allgemeinen nur für POSIX-kompatible Systeme.

mfg
Woodfighter

[Christoph]

Moin.

Gibt es eigentlich C-Compiler, die auf Linux laufen, aber Windows-Executables erstellen?

Zwei Links zum Thema MinGW-GCC cross-compiler:

MinGW FAQ
Gentoo Forums

Christoph

[Christian Seiler]

Hallo Martin,

By the way: Gibt es eigentlich C-Compiler, die auf Linux laufen, aber Windows-Executables erstellen?

Ja:

----------------- schnipp ---------------------------------
christian@cobalt ~/tmp/mingw $ cat test.c

#include <stdio.h>  
  
int main (int argc, char **argv) {  
  printf ("Hallo Welt!\n");  
  return 0;  
}

christian@cobalt ~/tmp/mingw $ i686-mingw32-gcc -Wall -o test.exe test.c
christian@cobalt ~/tmp/mingw $ file test.exe
test.exe: MS-DOS executable PE  for MS Windows (console) Intel 80386 32-bit
christian@cobalt ~/tmp/mingw $ wine test.exe
Hallo Welt!
----------------- schnapp ---------------------------------

Viele Grüße,
Christian

[steckl]

Hi,

aber wie verfährt man mit multiplikation? mache ich das "wie auf papier" werde ich bis zu 999  "999stellige" zahlen addieren müssen, das Ergebnis kann bis zu 1998-stellen haben

Ich weiß nicht ob es der beste Algorithmus ist, aber wir haben mal gelernt, wie man in der Digitaltechnik Multiplizierer entwerfen kann. So ähnlich würde ich es hier auch machen.

Hier mal ein Beispiel mit 3 statt 999 Stellen:

333 * 415
---------
     1665 Feld1 (max 4 Stellen)
   + 333| Feld2 (max 4 Stellen)
     ---|
     499| Feld1
  +1332|| Feld2
 --------
   138195 ErgFeld (max 6 Stellen)

Die letzte Stelle (da wo drunter | steht) kann immer direkt fürs Ergebnis übernommen werden. Du brauchst dir also immer nur 2 Summanden (Feld1 und Feld2) mit einer maximalen Länge von je 1000 und das Ergebnis (ErgFeld) mit einer maximalen Länge von 1998 merken. Macht insgesamt 3998 Byte.

Ein anderer (schlechterer) Ansatz wäre, wenn du dir immer das ganze Ergebnis merkst, dann bräuchtest du soweit ich das überblicke 2 Felder mit je 1998 Elementen.

333 * 415
---------
     1665 Feld1
   + 3330 Feld2
    -----
     4995 Feld1
  +133200 Feld2
---------
   138195 Feld1

Der Speicherbedarf hier sollte annähernd der gleiche sein (minimal weniger), aber der Rechenaufwand wird höher, da du zum Schluss 2mal 1998 Stellen bei der Addition hast.

es wäre extrem rechenaufwendig, zudem müsste ic hdie riesiegen arrays im voraus reservieren.

Das Reservieren im Voraus sollte aber schneller sein, wie wenn du jedes Byte einzeln reservierst. Am schluss müsste ja eh alles im Speicher stehen.

Ich Finde 2000 Zeichen eh nicht so schlimm, wenn du nicht gerade im Embedded-Bereich arbeitest.

was  macht man aber in C in solchen fällen? arrays variabler-länge lassen sich ja nicht definieren, bzw - ich weiss nciht wie,
was wäre der ansatz?

Meinst du sowas wie dynamische Speicherreservierung?
Mit malloc(), calloc() und realloc() kannst du je nach Bedarf Speicher reservieren. Mit free() gibst du ihn anschließend wieder frei.
In C++ geht es (wie ich finde) etwas komfortabler mit dem new/delete-Operator.
Aber ich weiß nicht, ob dir das viel bringt. Ich würde es mal versuchen, die 3 zusätzlich benötigten Felder einfach fest anzulegen.

mfG,
steckl

[Christoph]

Moin.

was  macht man aber in C in solchen fällen? arrays variabler-länge lassen sich ja nicht definieren, bzw - ich weiss nciht wie,
was wäre der ansatz?

C99 erlaubt Arrays variabler Länge für Variablen mit automatischer Lebensdauer (d.h. Variablen, die innerhalb von Funktionen ohne den Spezifizierer static deklariert werden).

Solche Arrays werden auf dem Stack abgelegt und nicht wie bei den genannten Alternativen malloc() und calloc() auf dem Heap.

Ein Beispiel:

  
void foo(size_t n)  
{  
    int bar[n]; // I'm a variable-length array  
    for(size_t i = 0; i < n; ++i)  
    {  
        // do stuff with bar[i]  
    }  
}

Damit der GCC das unterstützt, muss eventuell ein -std=c99 oder -std=gnu99 als Parameter mitgeliefert werden.

Christoph