C++ "Kleines" mathematisches Problem

[Chippo]

Hi. Ich versuche gerade Modulo an einer 24-stelligen Zahl einzusetzen. Als das nicht ging stellte ich fest das mir fmod auch nichts bringen würde weil ich im nach hinein erfuhr das ich selbst mit long double nicht auf so eine Zahl kommen kann^^
Jetzt frage ich mich ob es nicht doch einen Weg gibt, ein solches Zahlenmonster zu teilen und denn Rest zu ermitteln.
Da mir der Kopf brummt und ich vermutlich wieder viel zu kompliziert denke... weiß jemand Rat?


PS.: Ich könnte ja meinen Kopf abnehmen und eine Weile in einen Kühlschrank stecken. Nur wie bekomme ich ihm wieder dran?

 

[Darkko]

Libraries können dir diesbezüglich helfen: http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic#Libraries

 

[Backslash]

Es gibt diverse BigInteger Bibliotheken für C++, such dir eine aus und mach' es damit.

 

[Enigma]

http://stackoverflow.com/questions/...ate-a-128-bit-integer-modulo-a-64-bit-integer

 

[andy_0]

Das du in long double keine 24 Stellen rein bekommst halte ich für ein Gerücht. Ich habe soeben nachgesehen, es kann bis +-1,1*10^4932 adressieren. Es hat zwar nur eine Genauigkeit von 19 Nachstellen, aber das interessiert dich ja nicht.

Schon mal bei 64 Bit Datentypen nachgesehen?

Sollte dir das alles nicht reichen, musst du einen eigenen Datentyp definieren (http://de.wikibooks.org/wiki/C++-Programmierung/_Eigene_Datentypen_definieren).

 

[PeterIndustries]

Ich hab schon lange nicht mehr programmiert aber das Problem gefällt mir.
Hätte da eine Idee, allerdings weiss ich nicht ob diese in C++ geht:

Long Double berechnen und in Long int umwandeln -> Nachkommastellen gehen verloren.
((Long Double - Long Int)^2)^(0,5) -> Betrag der Differenz wird ermittelt, dies ist dann der Rest.


Vllt können ja ein paar "Pro's" sagen ob sowas geht.

 

[the_nobs]

Das du in long double keine 24 Stellen rein bekommst halte ich für ein Gerücht. Ich habe soeben nachgesehen, es kann bis +-1,1*10^4932 adressieren. Es hat zwar nur eine Genauigkeit von 19 Nachstellen, aber das interessiert dich ja nicht.

Das ist schon ein Problem
wenn seine zahl 24 stellen hat, dann reichen 19 nachstellen nicht, du kommst damit nur auf eine genauigkeit von 20 Stellen in summe. D.h. die niedrigsten 4 werden dann als 0 angenommen -> Modulo funktioniert da nicht mehr genau...

 

[kuddlmuddl]

Das ist schon ein Problem
wenn seine zahl 24 stellen hat, dann reichen 19 nachstellen nicht, du kommst damit nur auf eine genauigkeit von 20 Stellen in summe. D.h. die niedrigsten 4 werden dann als 0 angenommen -> Modulo funktioniert da nicht mehr genau...

Das Problem ist deutlich gravierender da schon dezimal 0,1 nicht mit 9 Binär Nachkommastellen genau dargestellt werden kann.

Neben BigInteger Bibs wäre natürlich auch eine (andere/schlechtere aber einfachere) Möglichkeit vorher die Zahl schon klein zu kriegen zB in dem die gesamte Berechnung in einem anderen Größenbereich stattfindet.. aber das geht evtl auch kosten der Genauigkeit.

 

[andy_0]

@ kuddlmuddl, the_nobs
In diese Richtung dachte ich auch. Falls benötigt vergrößert man die Zahl einfach um einen gewissen Faktor und reduziert sie dann wieder.

Es kann aber gut sein, dass gewisse Zahlenfolgen dennoch zu ungenau dargestellt werden könnten. Über spezielle Zahlenfolgen habe ich mir keinen Gedanken gemacht.

Eventuell wäre es auch eine Möglichkeit, die Zahl zu "normalisieren" d.h. einen gewissen ungeraden Teil "abzuschneiden", den Modulo zu berechnen und dann den abgeschnittenen Rest drauf zu rechnen (natürlich mit erneuter Prüfung, ob der Modulo noch einmal angewendet werden kann). Das sollte das Ergebnis nicht verfälschen oder übersehe ich etwas wichtiges?

 

[Backslash]

Wie schon einige gesagt haben kann es sich natürlich auch lohnen sich die Berechnung anzuschauen und vielleicht eine Möglichkeit zu finden gar nicht erst eine so große Zahl zu erhalten. Je nach dem was du machst kannst du den Modulo vielleicht auch schon wesentlich früher anwenden.

 

[Chippo]

Habs mir überlegt, Kühlschrank reicht nicht. Kennt jemand ein Kühlhaus mit der Kapazität Einstein-Bose-Kondensat zu produzieren?

Mit Darkkos vorgeschlagener Lib, würde ich es damit hinkriegen? Und wie binde ich sie ein?
Ihr müsst verstehen das ich erst mit C++ angefangen habe. Allein die Klassensache muss ich erst noch begreifen...
Und meinen Dozenten, denn ich nur ein mal in der Woche habe und denn ich mir mit Admins und Kaufleute teilen muss, kann ich gerade nicht fragen. Kommt Donnerstags. Letzten Donnerstag hatte er gerade mal 5 Minuten für mich und redete davon das ich mich mit IBAN beschäftigen soll. WAS ich genau tun soll konnte ich nicht aus ihm rausbekommen. Aber die Strippenzieher... äh... ich meine Admins sagen das er irgend wann vor Jahren von ihnen wollte das sie mit php einen IBAN Generator basteln sollten...

Wieviele Jahre kriege ich für besonders grausamen Mord?

 

[andy_0]

@ Chippo
Du gehst z.B. für die CLN Library hier hin (http://www.ginac.de/CLN/), lädst sie dir, bindest sie bei dir ein (<include> oder wenn es Quellcode ist, andersweitig importieren) und verwendest die jeweiligen Funktionen/Datentypen.

Ich denke ein möglichst großer Datentyp mit ausreichend hoher Genauigkeit wäre das richtige für dich. Da musst du nicht auf irgendwelche Spezialfälle etc. Rücksicht nehmen. Im "Notfall" kannst du dir auch einfach selbst ein Datentyp erstellen.

 

[Mathematiker]

schon einmal überlegt, dass über eine manuelle division zu bewerkstelligen? also schrittweise von links nach rechts ... der Rest ist dann das Ergebnis.

 

[asdfman]

Mathematiker: Da gibt es optimierte Algorithmen für. Wir leben doch nicht mehr in der Steinzeit.

 

[Chippo]

OK, zurück ans Reißbrett...
Ich habe jetzt drei Libs ausprobiert. Allerdings war ich mit denn Ergebnissen bzw. der Handhabung nicht ganz zufrieden.
Bei einer davon habe ich denn mitgelieferten Sample-Code ausprobiert, der eigentlich dazu diente mir zu zeigen wie toll das geht. Wohl bemerkt nach dem ich versucht habe die Lib gleich in meinen eigenen Code zu integrieren. Nach dem Start war ich kurz pinkeln, als ich zurück kam spuckte er immer noch Fehlermeldungen aus...
Offensichtlich schien bei beiden Versuchen das Problem direkt in der Lib zu liegen. Zumindest sagt das Visual Studio.
Ich fürchte bei so mancher Lib hätten die Entwickler angeben sollen, für welche Entwicklungsumgebung die Lib geschrieben wurde. Technisch gesehen sollte das nicht passieren, aber irgendwie habe ich das Gefühl, als würde das von meinen Dozenten vorgeschriebene MS Visual Studio Ultimate Probleme mit dem verwendeten Dialekt zu haben.

In Anbetracht dessen, das der Dozent eh nur alle 7 Tage vorbeirauscht und mir immer noch nicht gesagt hat WARUM gerade VS Ultimate, könnte ihr mir eine gute Entwicklungsumgebung empfehlen?

@ Mathematiker
Da ich hier bin um zu lernen, warum eigentlich nicht. Das Problem ist, das ich seit 10 Jahren aus der Schule bin. Könntest du mir nicht nur sagen wie ich vorgehen sollte, sondern auch mir einen Pseudo-Code geben?

 

[kuddlmuddl]

Wenn eine Zahl für einen einfachen Datentyp zu groß ist kannst du damit weder Modulo noch ne Division rechnen... dein Problem ist ja nicht die Zeile wo du Modulo durchführen willst sondern schon vorher wenn du diese 24stellige Zahl überhaupt in einer Variable speichern willst.

Ich vermute mal, dass du das Einbinden einfach "falsch" gemacht hast - VS ist zwar von Microsoft aber besser als man denkt. Es gab eine Zeit da galt als C++ das, was VS6 akzeptiert und nich was im Standard steht.. und das hatte imho auch seine Berechtigung.

Ohne mehr Infos was und wie du einbindest ist es immer schwer zu helfen aber eine riesige Zahl von Fehlermeldungen kann oft durch falsche /fehlende Pfadsetzungen entstehen.
Stimmt deine Windows $PATH Variable?
Hast du dem Compiler und auch dem Linker die nötigen Paras hinzugefügt?
Hast du die includes korrekt gemacht?
Liegen die Files am richtigen Ort?

Allein die Tatsache, dass von den verbreiteten Libs direkt 2 bei dir nicht funktionieren sollte eigtl automatisch zu dem Schluss führen dass man selbst was falsch macht und weder dazu dass VS schuld ist noch dass die Libs scheiße sind...

Falls dir das mit dem einbinden zu kompliziert ist und die eine möglichst unkomplizierte Lösung willst könntest du mal Eclise mit Java installieren. Da gibts nen BigInteger Typ schon in der API der natürlich auch Modulo rechnen kann:
http://docs.oracle.com/javase/1.4.2/docs/api/java/math/BigInteger.html
Include-Probleme löst man dort "alle" mit Strg+Shift+O (oder? is schon paar Jahre her...) da Eclipse das dann automatisch für Klassen aus der JAVA-Api durchführt.

 

[Chippo]

@ kuddlmuddl
Ne, falsch verstanden.

Ich habe jetzt drei Libs ausprobiert. Allerdings war ich mit denn Ergebnissen bzw. der Handhabung nicht ganz zufrieden.

Von daher das Handling und der Umfang waren nicht so wie ich es gern hätte.
Ergo, bis auf Matt McCutchen's (https://mattmccutchen.net/bigint/) waren die Libs sehr aufgebläht, omnipotent und letzten Endes für einen Anfänger (siehe Beiträge oben) weniger geeignet. Siehst du, da mein Dozent selbst wenn er mal neben mir steht, eigentlich woanders ist (Scheiß Quantenphysik) kann ich mir eigentlich nicht nur jeden Tag das besuchen der DAA sparen und zuhause lernen, sondern mir alles selbst beibringen.
Quasi die beiden anderen Libs schießen mehr mit Nukes auf Spatzen, als mir in schön kleinen Häppchen beizubringen was ich eigentlich will <-- Moment....
Matt McCutchen's BigInts Sample-Code ist schön ausdokumentiert und ich fühle mich auch nicht so erschlagen.

Allein die Tatsache, dass von den verbreiteten Libs direkt 2 bei dir nicht funktionieren sollte eigtl automatisch zu dem Schluss führen dass man selbst was falsch macht

Ich habe nie geschrieben das sie nicht funktionieren. Was BigInt angeht, war nun mal ein Sample mitgeliefert. Nachdem sich VC darüber aufgeregt hat das vieles im Sample noch nicht inkludiert ist und ich seinen Wunsch entsprach, spuckte er statt dessen Fehlermeldungen aus, aus dem ich nicht schlau werden konnte.

Oder ergibt <Error:453$!_libNme4c_Iso?Machmahalblang$Echo5> irgendeinen Sinn für dich
Normalweise kommt eine Fehlermeldung mit englischen oder deutschen Begriffen, aus dem man heraus orakeln kann, was er von einem will. In dem Fall waren es mehr Sonderzeichen, von denen einige nicht auf der Tastatur zu finden sind.

und weder dazu dass VS schuld ist noch dass die Libs scheiße sind...

Nie behauptet
Und was VS angeht, aufgrund dessen das mein Dozent letztens rumgemosert hat VS Ultimate es offensichtlich nicht mag wenn man Klassen per Hand erstellt, scheint es ebend nicht das gelbe vom Ei zu sein. Insbesonders für Leute die noch lernen und die Finger vom Wizard lassen sollten.

Sekunde, die Reihe nach...
Er sitzt mit seinem Laptop neben mir. Hat MS VS irgendwas 2008 auf der Platte. Code auf dem Schirm, mir Vorgaben machend was ich tun soll. Irgendwann fing mein VS U 2010 an Fehler auszuspucken. Mein Dozent verstand nicht warum. Setzt sich um und schaut nach was nicht stimmt. Am Ende (10 Minuten später) meinte er das mein VS - wovon er sagte ich es "so" eben bräuchte ( also kein Express) - es nicht mag wenn Klassen per Hand generiert werden. Er führte mir das auch vor.
Per Hand Fehlermeldung. Per Wizard keine.
Wenn du jetzt fragst: Warum, um Gottes Willen? Keine Ahnung! Wie gesagt, das ist passiert als er mir noch versuchte beizubringen wie man Klassen generiert.

Falls dir das mit dem einbinden zu kompliziert ist und die eine möglichst unkomplizierte Lösung willst könntest du mal Eclipse mit Java installieren.

Ich soll es doch mit C++ machen Ergo kein Java.
Allerdings, kennst du einen Weg die GUI von Eclipse wie VC aussehen zu lassen? Vielleicht merkt mein Dozent dann nicht das ich Java lerne anstatt C++



Jedenfalls brauche ich meine 24-stellige Zahl wegen IBAN (http://www.iban.de/iban-pruefsumme.html). Da ich nicht drum komme, dieses... Ding durch 97 zu teilen und denn Restwert zu ermitteln, brauch ich einen besseren Plan.

 

[Backslash]

Du kannst ja auch auf einem String arbeiten und die Rechnung selbst bauen, ist ja nicht so schwierig.

/edit: übrigens gibt es auch javascript quellcode für die validierung: http://www.tbg5-finance.org/?ibandocs.shtml

außerdem ist zu beachten:

Die ECBS weist ausdrücklich darauf hin, dass nur die Banken selbst korrekte IBANs herausgeben.[13] Benutzt man eine selbsterrechnete IBAN, so riskiert man im schlimmsten Fall den Verlust seiner Überweisung. Bereits die ISO 13616 legt fest, dass ausschließlich die Finanzinstitute eine IBAN generieren dürfen. Hintergrund ist, dass die bisherige Kontonummer nicht immer rechtsbündig in die IBAN eingesetzt wird, sondern gelegentlich um zwei Stellen versetzt - die letzten beiden Ziffern entsprechen dann dem bisherigen Unterkonto.

 

[BigNum]

Hallo,

die einfachste Lösung ist die 24-stellige Zahl in mehrere kleinere Teile zu zerlegen und den Modulo-Wert wie in einer "schriftlichen Division" zu berechen:
Ich habe dazu das Beispiel von der von Dir verlinkten Seite http://www.iban.de/iban-pruefsumme.html genommen:

700901001234567890131400
700825
------
    76001234
    76001149
    --------
          85567890
          85567871
          --------
                19131400
                19131310
                --------
                      90

Als erstes berechnest Du 700901%97=76, dann multiplizierst Du dieses Ergebnis "76" mit 1000000, addierst 001234 was 76001234 ergibt. 76001234%97=85. Mal 1000000 plus 567890 ergibt 85567890, 85567890%97=19. Mal 1000000 plus 131400 ergibt 19131400, 19131400%97=90. Fertig!

 

[The Insane]

Ich hab das mal in C++ versucht zu implementieren. Die Zahl speicher ich einfach als ein N-dimensionales array und teile dann wie in der Schule. Also die erste Stelle drunterschreiben, wenn die zu klein ist die nächste nehmen und dann den Übertrag beim nächsten weiterverwenden. Das Ergebnis wird hierbei nicht gespeichert, nur der Übertrag. Das kannst du ja dann machen, braucht man halt noch ein zweites Array

Die Zahl wird hierbei zufällig erstmal initialisiert, N ist die Anzahl der Stellen und div ist das, durchwas geteilt wird. Damit kannst du beliebig große Zahlen nehmen, bzw soviel wie das OS/der RAM hergibt

Edit: Bzw. N und div dürfen hier bis 2,147,483,647 gehen, sind ja auch nur int's.

#include <stdio.h>
#include <iostream>
#include <time.h>

int main(int argc, char **argv)
{
    srand(time(0));

    int N=24;           //Wieviel Stellen hat die Zahl
    int div = 97;       //Durch was wird geteilt

    int *mynumber = new int[N];

    std::cout<<"Meine "<<N<<" stellige Zahl:"<<std::endl;

    //Initialisiere Zahl mit zufälligen Ziffern, erste Stelle !=0
    mynumber[0] = rand()%9 + 1;
    std::cout<<mynumber[0];
    for (int i=1; i<N; i++)
    {
        mynumber[i] = rand()%10;
        std::cout<<mynumber[i];
    }
    std::cout<<std::endl;

    //Teile nun, die Variable temp enthält immer den aktuellen Übertrag
    int temp = mynumber[0];
    int i=0;
    while (i<N-1)
    {
        while (temp<div && i<N-1)
        {
            i++;
            temp = 10*temp + mynumber[i];
        }
        temp = temp%div;
    }

    //Fertig
    std::cout<<"Rest bei Teilung durch "<<div<<": "<<std::endl;
    std::cout<<temp<<std::endl;

    delete[] mynumber;

    return 0;
}

Ausgabe z.B:

Meine 24 stellige Zahl:
315175783980021881282882
Rest bei Teilung durch 97: 
47