Schachbrett / long double

Stromberg

Kenn ihr auch die Story mit dem Schachbrett, wenn man ein Reiskorn auf das 1. Feld legt und man es dann auf jedem weiteren Feld verdoppelt.... kommt was ganz großes Raus. Wenn man dass als C++ Programm schreibt ist die letzte Zahl auf Feld 64: "9.22337e+18" Was ist dass jetzt in einer echten Zahl? Wie lese ich dass? Der Typ welchen ich genutzt habe, war "long double" (bei in gibt er nach so 25 Feldern auf).

MfG
Stromberg

Dravere

http://en.wikipedia.org/wiki/Scientific_notation#E_notation

Grüssli

Firefighter

Das bedeutet das nach der 9 noch weitere 18 Stellen kommen.
Das sind dann 9 Trillionen
http://de.wikipedia.org/wiki/Zahlennamen#Billion.2C_Billiarde_und_dar.C3.BCber_hinaus

Stromberg

Hardcore, also wären dass dann auf Feld 64: 922337000000000000000000 Reiskörner?

MfG
Stromberg

Firefighter

müssen nicht unbedingt 0en sein, können auch andere Zahlen sein, heißt ja nur das weitere 18 stellen folgen.

Dravere

Mach mal bei der Ausgabe das folgende hin:

long double value; // <- dein Wert, welcher du ausgeben willst.
std::cout.precision(15); // <- 15 Stellen genau ausgeben.
                         // Auf MSVC ist long double gleich einem double.
                         // Ein double ist 15 Stellen genau.

std::cout << std::fixed << value << std::endl;
// std::fixed == verwende keine E-Notation.

Grüssli

Erhard Henkes

#include <iostream>
using namespace std;

int main()
{
    unsigned long long value = 1;
    for (int i=1; i<64; ++i)
    {
        value *= 2;
        cout << "Feld Nr. " << i+1 << ": " << value << endl;
    }
}

Nexus

Vielleicht noch angemerkt, dass der Datentyp long long int nicht im C++-Standard vorgesehen ist.

Stromberg

Wenn ich cout << std::fixed << value << endl; mache, dann kommt folgende Zahl raus: 9223372036854775808.000000

Kann dass stimmen? Und was soll das Komma?

MfG
Stromberg

Dravere

Stromberg schrieb:

Kann dass stimmen?

Kommt drauf an, welchen Kompiler du nutzt und was long double dort ist.

Stromberg schrieb:

Und was soll das Komma?

long double ist eine Gleitkommazahl. Also eine Zahl mit Dezimalstellen.
Im std::fixed Modus gibt precision die Anzahl Ziffern nach dem Komma an, und füllt sie allenfalls auch mit Nullen. Per Default ist precision auf 6. Also wenn du das Komma weghaben willst, dann mach dies:

std::cout << std::setprecision(0) << std::fixed << value << std::endl;

Das war von mir vorhin wohl ein wenig unklar erklärt ...
Zum selber nachschauen:
http://www.cplusplus.com/reference/iostream/manipulators/

Grüssli

Werner Salomon

Stromberg schrieb:

Hardcore, also wären dass dann auf Feld 64: 922337000000000000000000 Reiskörner?

Nein, das E+18 in '9.22337e+18' heißt nicht, dass 18 0'en folgen, sondern dass das Komma (bzw. der Dezimaltrenner) um 18 Stellen nach rechts zu verschieben ist. Also etwa 9223370000000000000, genau sind es: 9223372036854775808.

Nexus schrieb:

Vielleicht noch angemerkt, dass der Datentyp long long int nicht im C++-Standard vorgesehen ist.

Stimmt, da hier aber nur die Multiplikation mit einer ganzen Zahl (immer 2) gefordert ist, kann man sich schnell eine eigene Big-Integer-Klasse bauen, die es 'ganz genau' ausrechnet.

#include <algorithm>    // copy
#include <cassert>
#include <iostream>
#include <iterator>     // ostream_iterator
#include <vector>

class BigInt
{
public:
    BigInt()
        : m_digits( 1, 0 )  // == 0; eine Dezimalstelle
    {}
    BigInt( int i )
        : m_digits()
    {
        assert( i >= 0 );   // negative Zahlen sind nicht vorgesehen
        if( i == 0 )
            m_digits.push_back( 0 );
        else
            push( i );
    }
    BigInt& operator*=( int faktor )
    {
        assert( faktor >= 0 );
        if( faktor == 0 )   // Sonderbehandlung für Multiplikation mit 0
        {
            m_digits = std::vector< int >( 1, 0 );
            return *this;
        }
        int uebertrag = 0;
        for( std::vector< int >::iterator i = m_digits.begin(); i != m_digits.end(); ++i )
        {
            (*i *= faktor) += uebertrag;
            uebertrag = *i / 10;
            *i %= 10;
        }
        push( uebertrag );
        return *this;
    }
    friend std::ostream& operator<<( std::ostream& out, const BigInt& bi )
    {
        std::copy( bi.m_digits.rbegin(), bi.m_digits.rend(), std::ostream_iterator< int >( out ) );
        return out;
    }

private:
    void push( int i )
    {
        for( ; i > 0; i /= 10 )
            m_digits.push_back( i % 10 );
    }
    std::vector< int > m_digits; // Dezimalziffern
};

int main()
{
    using namespace std;

    BigInt value = 1;
    for( int i=1; i<=64; ++i, value *= 2 )
    {
        cout << "Feld Nr. " << i << ": " << value << endl;
    }
    cout << "Summe aller Felder + 1 = " << value << endl;
    return 0;
}

:xmas2: Werner

unskilled

das *=2 könnte man auch durch nen << 1 machen - hätte dann den Vorteil, dass es schneller wäre aber den Nachteil, dass right-shift eben nur bei der Multiplikation von 2er Potenzen als Multiplikations-Ersatz gilt ^^ außerdem müsste man es ja trotzdem noch implementieren:

an Werners Beispiel anknüpfend:

class BigInt
{
public:
  BigInt& operator << (size_t i) //this *= 2^i
  {
    m_digits.resize(i + m_digits.size()); //sicherstellen, dass das Array groß genug ist
    m_digits << i; //verschiebung um i Elemente nach rechts - entspricht einer Multiplikation mit 2^i
    return *this; //man soll ja bequem mit dem Wert weiterrechnen können - auch in der selben Zeile
  }
};

Anwendung:

int main()
{
    using namespace std;

    BigInt value = 1;
    for (size_t i = 0; i != 64; ++i, value << 1)
    {
        cout << "Feld Nr. " << i << ": " << value << endl;
    }
    value << 1; //das _imaginäre_ 65. Feld wäre die Summe +1, würde ich in der schleife nicht mit ausgeben ^^
    cout << "Summe aller Felder + 1 = " << value << endl;
//die beiden zeilen könnte man auch so zusammenfassen, find ich aber hässlich und unübersichtlich - außerdem trennt es ausgabe nun mal nicht von berechnung, was ich immer sehr unschön finde ^^
/*
    cout << "Summe aller Felder + 1 = " << value << 1 << endl;
*/
}

bb

Werner Salomon

unskilled schrieb:

das *=2 könnte man auch durch nen << 1 machen - hätte dann den Vorteil, dass es schneller wäre aber den Nachteil, dass right-shift eben nur bei der Multiplikation von 2er Potenzen als Multiplikations-Ersatz gilt ^^ außerdem müsste man es ja trotzdem noch implementieren:

an Werners Beispiel anknüpfend:
class BigInt
{
public:
  BigInt& operator << (size_t i) //this *= 2^i
  {
    m_digits.resize(i + m_digits.size()); //sicherstellen, dass das Array groß genug ist
    m_digits << i; //verschiebung um i Elemente nach rechts - entspricht einer Multiplikation mit 2^i
    return *this; //man soll ja bequem mit dem Wert weiterrechnen können - auch in der selben Zeile
  }
};

gute Idee, leider ist die Implementierung so schlicht falsch bzw. gar nicht möglich.

Das Ziel von dem von mir vorgestellten BigInt ist es, die Zahl am Ende in ihrer Dezimalform darzustellen. Um dies ganz einfach zu machen, speichere ich auch gleich die Dezimalziffern im Member 'm_digits' ab. Also die Elemente in diesem vector<int> enthalten immer (!) Integer-Werte im Interval [0..9] (siehe auch Zeile 35 im Listing oben).
Mit der von Dir vorgeschlagenen Methode kann man BigInt also nur mit 10^i 'multiplizieren'.

:xmas2: Werner

unskilled

Werner Salomon schrieb:

Das Ziel von dem von mir vorgestellten BigInt ist es, die Zahl am Ende in ihrer Dezimalform darzustellen. Um dies ganz einfach zu machen, speichere ich auch gleich die Dezimalziffern im Member 'm_digits' ab. Also die Elemente in diesem vector<int> enthalten immer (!) Integer-Werte im Interval [0..9] (siehe auch Zeile 35 im Listing oben).
Mit der von Dir vorgeschlagenen Methode kann man BigInt also nur mit 10^i 'multiplizieren'.

Ach mist - hab ich nat. mal wieder nicht weiter drüber nachgedacht - falls du std::vector <bool> bzw std::dynamic_bitset nehmen würdest oder wie das heißt, würde es gehen (dafür wäre alles andere ein ganz klein wenig umständlicher ;D) ^^ aber so ists natürlich schwachsinn (zumindest für 2^i - für 10^i wärs vrmtl nich die allerschlechteste lösung ^^)

bb

Nexus

unskilled schrieb:

das *=2 könnte man auch durch nen << 1 machen - hätte dann den Vorteil, dass es schneller wäre

Kaum. Der Compiler wird Multiplikationen mit Zweierpotenzen schon optimieren können.

unskilled

Nexus schrieb:

unskilled schrieb:

das *=2 könnte man auch durch nen << 1 machen - hätte dann den Vorteil, dass es schneller wäre

Kaum. Der Compiler wird Multiplikationen mit Zweierpotenzen schon optimieren können.

Bei PODs hab ich da keinen Zweifel, dass er das kann - aber bei Werners operator (oder allg. wenn man ihm explizit sagt, wie er zu multiplizieren hat) glaube ich das kaum...

btw: (MSVC 2008 Prof, Release, 32bit)

to_multiply *= 2;
//wird zu:
00391020  add         eax,eax

also ist ein addieren besser als nen simpler shift (SAL eax, 1)?

versteh ich nicht ^^ da ich aber von geburt an neugierig bin: kanns wer erklären? ^^ (iwie hab ich au nirgendwo gefunden, wie viele taktzyklen der befehl braucht ^^)

bb