unsignierter Ganzzahltyp mit unendlicher Reichweite im Plusbereich
-
Ich interessiere mich, ob es so einen Datentyp gibt. Ich könnte ihn für mein kleines Fibonacci-Programm verwenden, da ist ein long int ja schon nach ca. dem 50. Wert erschöpft. Machbar wäre so ein Datentyp ja, könnte ähnlich aussehen wie ein string (00000000 gibt Ende des Datentypes an).
-
Dein Speicher ist endlich => nix ist mit unendlichen Zahlen
Unsigniert? Du meinst vorzeichenlos?
-
manni66 hat natürlich recht.
Aber vielleicht reichen dir auch schon größere Zahlen als long long, die aber noch in deinen Speicher passen. Dann schau dir zum Beipiel mal gmp an: https://gmplib.org/ - für dich dürfte dann
mpz_classinteressant sein.Es gibt sicher noch viele viele andere Bibliotheken. Such einfach mal nach
c++ bigint!
-
manni66 schrieb:
Unsigniert? Du meinst vorzeichenlos?
Natürliche Zahlen, 0 ... unendlich.
Vielleicht gibt es eine "BigNatural" library?
-
Ja, vorzeichenlos und nur durch die Hardware limitiert. Ich habe aber keine Lust, mich in eine Library einzuarbeiten, während ich noch mein erstes Buch lese. Ich glaube, das wird nichts und ich muss dem Nutzer einfach zu große Zahlen verbieten.
-
Timon Paßlick schrieb:
Ja, vorzeichenlos und nur durch die Hardware limitiert. Ich habe aber keine Lust, mich in eine Library einzuarbeiten, während ich noch mein erstes Buch lese. Ich glaube, das wird nichts und ich muss dem Nutzer einfach zu große Zahlen verbieten.
Eine fertige Lib zu benutzen ist auf jeden Fall einfacher, als eine für beliebig große Zahlen selbst zu schreiben.
-
Ich weiß, aber so viel ist mir ein Übungsprogramm nicht wert.
-
Hier ist doch alles, was du brauchst.
Einfach BigInt::SIZE auf einen Wert setzen, der dir passt, und ab geht die Postint main() { auto a = 0_int, b = 1_int, c = 1_int; for(int i = 0; i < 5000; ++i) { std::cout << c << "\n"; c = a + b; a = b; b = c; } }
-
Hallo Timon,
ich hatte vor längerer Zeit ein BigInt geschrieben, welches im Dezimalsystem rechnet. Mit dem Fibonacci:
#include <sam/BigInt.h> // s. Code am Ende des Posting #include <iostream> #include <iomanip> template< typename T > T fibonacci( unsigned n ) { if( n < T(2) ) return T(n); auto fn_1 = T(1); auto fn = T(1); for( unsigned i = 2; i < n; ++i ) { auto fnext = fn + fn_1; fn_1 = fn; fn = fnext; } return fn; } int main() { using namespace std; for( int i=0; ; ++i ) // let it run ... { cout << "F(" << setw(4) << i << ") = "<< fibonacci< sam::BigInt >( i ) << endl; } return 0; }da bist Du ruckzuck bei F(1000) und gefühlten 200'stelligen Zahlen. Schluss ist dann, wenn Dein Speicher platzt!
Gruß
WernerDatei sam/BigInt.h; boost needed! (ohne Gewähr - ich weiß nicht mehr in welchem Zustand der Code ist - addieren funktioniert):
// -- sam.BigInt #pragma once #include <boost/operators.hpp> #include <boost/bind.hpp> #include <algorithm> // swap, equal #include <cassert> #include <cmath> #include <deque> #include <functional> #include <iostream> #include <iterator> #include <limits> #include <vector> #include <numeric> namespace sam { namespace detail { template< int BASE, typename C, typename T > void mult( C& digits, const T& fac ) { T carry = 0; for( C::iterator i = digits.begin(); i != digits.end(); ++i ) { if( ((*i *= fac) += carry) >= BASE ) { carry = *i / BASE; *i %= BASE; } else carry = 0; } for( ; carry > 0; carry /= BASE ) digits.push_back( carry % BASE ); } template< int BASE, typename C1, typename C2 > void add( C1& sum, const C2& x ) { if( sum.size() < x.size() ) sum.resize( x.size(), 0 ); C1::iterator i = sum.begin(); int carry = 0; for( C2::const_iterator j = x.begin(); j != x.end(); ++i, ++j ) { if( (*i += *j + carry) >= BASE ) { *i -= BASE; carry = 1; } else carry = 0; } for( ; i != sum.end(); ++i ) { if( (*i += carry) >= BASE ) { *i -= BASE; carry = 1; } else carry = 0; } if( carry > 0 ) sum.push_back( carry ); } template< typename I1, typename I2 > bool is_less( I1 first, I1 last, I2 first2 ) { for( ; first != last; ++first, ++first2 ) { if( *first < *first2 ) return true; if( *first2 < *first ) return false; } return false; // gleich ist !kleiner } template< typename I1, typename I2 > bool subtract( I1 first, I1 last, I2 first2 ) { int carry = 0; for( ; first != last; ++first, ++first2 ) { const int sub = *first2 + carry; if( *first < sub ) { carry = 1; *first += 10 - sub; } else { carry = 0; *first -= sub; } } return carry != 0; } template< typename I1 > void dec( I1 first, I1 last ) { for( ; first != last; ++first ) { if( *first > 0 ) { --(*first); return; } *first = 9; } assert(("dec( 0 )",0)); return; } template< typename T, typename T BASE, typename Itr, typename Itr2 > void minus_product( Itr first, Itr last, Itr2 first2, T factor ) { assert( factor >= 0 ); assert( factor < BASE ); T carry = 0; for( ; first != last; ++first, ++first2 ) { T sub = *first2 * factor + carry; // subtrahend carry = sub / BASE; // integer division sub %= BASE; if( *first < sub ) { *first += BASE; ++carry; } assert( *first >= sub ); *first -= sub; // subtraction } assert( carry == 0 ); } } // namespace detail // --- Big int class BigInt : public boost::operators< BigInt >, boost::operators2< BigInt, int > //boost::dividable< BigInt, //boost::additive< BigInt, //boost::modable< BigInt, //boost::multipliable< BigInt, int, //boost::less_than_comparable< BigInt //> > > > > { public: static int const BASE = 10; template< typename Itr > BigInt( Itr first, Itr last ) : m_digits( first, last ) { normalize(); } BigInt() : m_digits( 1, 0 ), m_sign( 1 ) {} BigInt( int i ) : m_digits( 1, 0 ), m_sign( 1 ) { if( i < 0 ) { m_sign = -1; i = -i; } else if( i > 0 ) { std::vector< int > digits; for( ; i > 0; i /= BASE ) digits.push_back( i % BASE ); std::swap( m_digits, digits ); } } BigInt& operator+=( int b ) { if( (m_sign < 0 && b >= 0) || (m_sign > 0 && b < 0 ) ) { return *this -= -b; } if( b < 0 ) b = -b; int carry = 0; m_digits.front() += b; for( std::vector< int >::iterator i = m_digits.begin(); i != m_digits.end(); ++i ) { if( (*i += carry) < BASE ) return *this; carry = *i / BASE; *i %= BASE; } for( ; carry > 0; carry /= BASE ) m_digits.push_back( carry % BASE ); return *this; } BigInt& operator+=( const BigInt& b ) { if( m_sign != b.m_sign ) { return *this -= -b; } if( m_digits.size() < b.m_digits.size() ) m_digits.resize( b.m_digits.size(), 0 ); std::vector< int >::iterator i = m_digits.begin(); int carry = 0; for( std::vector< int >::const_iterator j = b.m_digits.begin(); j != b.m_digits.end(); ++i, ++j ) { if( (*i += *j + carry) >= BASE ) { *i -= BASE; carry = 1; } else carry = 0; } for( ; i != m_digits.end(); ++i ) { if( (*i += carry) >= BASE ) { *i -= BASE; carry = 1; } else carry = 0; } if( carry > 0 ) m_digits.push_back( carry ); return *this; } BigInt& operator-=( int b ) { using std::abs; if( (m_sign < 0 && b >= 0) || (m_sign > 0 && b < 0 ) ) { return *this += -b; } if( abs( b ) > abs( *this ) ) { return *this = -(b - *this); } if( b < 0 ) b = -b; m_digits.front() -= b; int carry = 0; for( std::vector< int >::iterator i = m_digits.begin(); i != m_digits.end(); ++i ) { if( (*i -= carry) >= 0 ) return *this; for( carry = 0; *i < 0; ) { *i += BASE; ++carry; } } assert(("logischer Fehler: abs( b ) > abs( *this ) !?",0)); return *this; } BigInt& operator-=( const BigInt& b ) { if( m_sign != b.m_sign ) { return *this += -b; } if( abs( b ) > abs( *this ) ) { return *this = -(b - *this); } const std::vector< int >::iterator i = m_digits.begin() + b.m_digits.size(); if( detail::subtract( m_digits.begin(), i, b.m_digits.begin() ) ) { detail::dec( i, m_digits.end() ); } normalize(); return *this; } BigInt& operator*=( const BigInt& b ) { std::deque< int > result( 1, 0 ); for( std::vector< int >::const_reverse_iterator ib = b.m_digits.rbegin(); ; ) { std::deque< int > product( m_digits.begin(), m_digits.end() ); detail::mult< BASE >( product, *ib ); detail::add< BASE >( result, product ); if( ++ib == b.m_digits.rend() ) break; result.push_front( 0 ); } m_digits.assign( result.begin(), result.end() ); m_sign *= b.m_sign; return *this; } BigInt& operator*=( int b ) { if( m_digits.size() == 1 && m_digits.back() == 0 ) return *this; if( b == 0 ) { std::vector< int > zero( 1, 0 ); std::swap( zero, this->m_digits ); m_sign = 1; return *this; } m_sign = ((m_sign > 0 && b >= 0) || (m_sign < 0 && b < 0)? +1: -1 ); if( b < 0 ) b = -b; detail::mult< BASE >( m_digits, b ); return *this; } BigInt& operator/=( const BigInt& b ) { m_sign /= b.m_sign; if( abs( *this ) < abs( b ) ) { BigInt zero; zero.swap( *this ); return *this; } std::vector< int > res( m_digits.size() - b.m_digits.size() + 1, 0 ); typedef std::vector< int >::iterator It; It i = m_digits.begin() + res.size(); for( std::vector< int >::reverse_iterator iRes = res.rbegin() ; iRes != res.rend(); ++iRes ) { typedef std::reverse_iterator< It > RevIt; It iEnd = --i + b.m_digits.size(); for( ; (iEnd != m_digits.end() && *iEnd > 0) || !detail::is_less( RevIt( iEnd ), RevIt( i ), b.m_digits.rbegin() ); ) { if( detail::subtract( i, iEnd, b.m_digits.begin() ) ) detail::dec( iEnd, m_digits.end() ); ++(*iRes); } } std::swap( m_digits, res ); normalize(); return *this; } BigInt& operator%=( const BigInt& b ) { assert( m_sign > 0 && b > 0 ); if( *this < b ) { return *this; } std::vector< int > res( m_digits.size() - b.m_digits.size() + 1, 0 ); typedef std::vector< int >::iterator It; It i = m_digits.begin() + res.size(); for( std::vector< int >::reverse_iterator iRes = res.rbegin() ; iRes != res.rend(); ++iRes ) { typedef std::reverse_iterator< It > RevIt; It iEnd = --i + b.m_digits.size(); for( ; (iEnd != m_digits.end() && *iEnd > 0) || !detail::is_less( RevIt( iEnd ), RevIt( i ), b.m_digits.rbegin() ); ) { if( detail::subtract( i, iEnd, b.m_digits.begin() ) ) detail::dec( iEnd, m_digits.end() ); ++(*iRes); } } normalize(); return *this; } BigInt& operator++() { assert( m_sign > 0 ); for( std::vector< int >::iterator i = m_digits.begin(); i != m_digits.end(); ++i ) { if( ++*i < BASE ) return *this; *i = 0; } m_digits.push_back( 1 ); return *this; } BigInt operator-() const { BigInt ret( *this ); ret.m_sign = -ret.m_sign; return ret; } // -- compare bool operator==( const BigInt& b ) const { return m_digits.size() == b.m_digits.size() && m_sign == b.m_sign && std::equal( m_digits.begin(), m_digits.end(), b.m_digits.begin() ); } bool operator<( const BigInt& b ) const { if( m_sign < b.m_sign ) return true; if( b.m_sign < m_sign ) return false; if( m_sign > 0 ) return m_digits.size() < b.m_digits.size() || ( m_digits.size() == b.m_digits.size() && detail::is_less( m_digits.rbegin(), m_digits.rend(), b.m_digits.rbegin() ) ); return b.m_digits.size() < m_digits.size() || ( b.m_digits.size() == m_digits.size() && detail::is_less( b.m_digits.rbegin(), b.m_digits.rend(), m_digits.rbegin() ) ); } void swap( BigInt& b ) { std::swap( m_digits, b.m_digits ); std::swap( m_sign, b.m_sign ); } friend bool is_palindrom( const BigInt& b ) { if( b.m_digits.size() < 2 ) return true; return std::equal( b.m_digits.begin(), b.m_digits.begin() + b.m_digits.size()/2, b.m_digits.rbegin() ); } friend BigInt reverse( const BigInt& b ) { return BigInt( b.m_digits.rbegin(), b.m_digits.rend() ); } template< typename E, typename Traits > friend std::basic_istream< E, Traits >& operator>>( std::basic_istream< E, Traits >& in, BigInt& bi ) { if( !(in >> std::ws).good() ) { in.setstate( std::ios_base::failbit ); return in; } bi.m_sign = +1; if( E( in.peek() ) == in.widen( '-' ) ) { bi.m_sign = -1; in.get(); } std::vector< int > digits; std::basic_streambuf< E, Traits >* sb = in.rdbuf(); const std::ctype< E >& ct = std::use_facet< std::ctype< E > >( in.getloc() ); for( Traits::int_type m = sb->sgetc(); ; m = sb->snextc() ) { if( Traits::eq_int_type( m, Traits::eof() ) ) { in.setstate( std::ios_base::eofbit ); break; } const E c = Traits::to_char_type( m ); if( !ct.is( std::ctype_base::digit, c ) ) break; // Ende, da keine Ziffer mehr folgt digits.push_back( int( c - E('0') ) ); } if( digits.empty() ) // keine Zahl gefunden in.setstate( std::ios_base::failbit ); else { std::reverse( digits.begin(), digits.end() ); std::swap( digits, bi.m_digits ); } return in; } template< typename E, typename Traits > friend std::basic_ostream< E, Traits >& operator<<( std::basic_ostream< E, Traits >& out, const BigInt& bi ) { if( bi.m_sign < 0 ) out << out.widen( '-' ); std::transform( bi.m_digits.rbegin(), bi.m_digits.rend() , std::ostream_iterator< E >( out ), std::bind2nd( std::plus< E >(), out.widen('0') ) ); return out; } int toInt() const { return std::accumulate( m_digits.rbegin(), m_digits.rend(), 0, boost::bind( std::plus< int >(), boost::bind( std::multiplies< int >(), _1, BASE ), _2 ) ); } typedef std::vector< int >::const_iterator const_iterator; friend const_iterator begin( const BigInt& b ) { return b.m_digits.begin(); } friend const_iterator end( const BigInt& b ) { return b.m_digits.end(); } std::size_t size() const { return m_digits.size(); } friend BigInt abs( BigInt x ) { if( x.m_sign < 0 ) x.m_sign = -x.m_sign; return x; } private: void normalize() { std::vector< int >::reverse_iterator iGtrZero = std::find_if( m_digits.rbegin(), m_digits.rend(), std::bind2nd( std::greater< int >(), 0 ) ); if( iGtrZero == m_digits.rend() ) { // -- BigInt ist =0 std::vector< int > zero( 1, 0 ); std::swap( zero, m_digits ); m_sign = 1; } else m_digits.erase( iGtrZero.base(), m_digits.end() ); } std::vector< int > m_digits; int m_sign; // e{+1,-1} }; template< typename T > int toInt( const T& x ); template<> int toInt( const BigInt& x ) { return x.toInt(); } } // namespace sam namespace std { template<> class numeric_limits< sam::BigInt > { public: static const bool is_integer = true; static const bool is_signed = false; static const bool is_exact = true; static const bool is_bounded = false; static const bool is_specialized = true; static const int radix = sam::BigInt::BASE; static const int digits = 0; // 'unendlich' static const int digits10 = 0; // 'unendlich' }; }
-
Incocnito schrieb:
Mal abgesehen davon, dass er noch die anderen mathematischen Operationen implementieren muss - alles auf Addition zurückzuführen dürfte ein wenig ineffizient sein
-
Bin beeindruckt. Wenn ich "Accelerated C++" zuende gelesen habe und den Code verstehen kann, komme ich hierhin zurück und guck mir das an. Dann kommen auch die anderen Operatoren dazu und vielleicht sogar mehr Effizienz, poste ich dann hier rein.
Braucht noch ein bisschen, aber kommt.