Boost-Commit :

Date view	Thread view	Subject view	Author view

From: zeux_at_[hidden]
Date: 2007-07-15 18:37:22

Next message: zeux_at_[hidden]: "[Boost-commit] svn:boost r7440"
Previous message: jakevoytko_at_[hidden]: "[Boost-commit] svn:boost r7438"

Author: zeux
Date: 2007-07-15 18:37:20 EDT (Sun, 15 Jul 2007)
New Revision: 7439
URL: http://svn.boost.org/trac/boost/changeset/7439

Log:
Small header fix, todo update, documentation uploaded, example uploaded

Added:
   sandbox/SOC/2007/bigint/boost.png (contents, props changed)
   sandbox/SOC/2007/bigint/libs/bigint/example.cpp
   sandbox/SOC/2007/bigint/libs/bigint/index.html
Text files modified:
   sandbox/SOC/2007/bigint/boost/bigint/bigint.hpp | 2 +-
   sandbox/SOC/2007/bigint/libs/bigint/todo.txt | 9 +++++----
   2 files changed, 6 insertions(+), 5 deletions(-)

Added: sandbox/SOC/2007/bigint/boost.png
==============================================================================
Binary file. No diff available.

Modified: sandbox/SOC/2007/bigint/boost/bigint/bigint.hpp
==============================================================================
--- sandbox/SOC/2007/bigint/boost/bigint/bigint.hpp (original)
+++ sandbox/SOC/2007/bigint/boost/bigint/bigint.hpp 2007-07-15 18:37:20 EDT (Sun, 15 Jul 2007)
@@ -126,7 +126,7 @@
                 return *this;
         }

- const bigint_base& operator>>=(boost::uint64_t other)
+ const bigint_base& operator>>=(uint64_t other)
         {
                 impl.rshift(impl, other);
                 return *this;

Added: sandbox/SOC/2007/bigint/libs/bigint/example.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/bigint/libs/bigint/example.cpp 2007-07-15 18:37:20 EDT (Sun, 15 Jul 2007)
@@ -0,0 +1,111 @@
+/* Boost bigint example.cpp test file
+ *
+ * Copyright 2007 Arseny Kapoulkine
+ *
+ * Distributed under the Boost Software License, Version 1.0.
+ * (See accompanying file LICENSE_1_0.txt or
+ * copy at http://www.boost.org/LICENSE_1_0.txt)
+ */
+
+#include <boost/bigint/bigint.hpp>
+
+#include <iostream>
+
+using boost::bigint;
+
+// Raise a to the power n for log(n)
+template <typename T> inline const T power_logN(const T& a, unsigned int n)
+{
+ if (n <= 0) return 1;
+
+ T result(1);
+
+ unsigned int power_of_two = 1;
+
+ // Find largest power of two that is > n
+ while (power_of_two < n && (power_of_two << 1) != 0)
+ power_of_two <<= 1;
+
+ if (power_of_two > n)
+ power_of_two >>= 1;
+ else if (power_of_two == n) // handle large n
+ {
+ power_of_two >>= 1;
+ result = a;
+ }
+
+ while (power_of_two > 0)
+ {
+ if ((n & power_of_two) != 0)
+ {
+ result *= result;
+ result *= a;
+ }
+ else
+ result *= result;
+
+ power_of_two >>= 1;
+ }
+
+ return result;
+}
+
+struct mat22
+{
+ bigint m00, m01;
+ bigint m10, m11;
+
+ mat22()
+ {
+ }
+
+ mat22(int): m00(1), m01(0),
+ m10(0), m11(1)
+ {
+ }
+
+ const mat22& operator*=(const mat22& m)
+ {
+ mat22 result;
+
+ result.m00 = m00 * m.m00 + m01 * m.m10;
+ result.m01 = m00 * m.m01 + m01 * m.m11;
+
+ result.m10 = m10 * m.m00 + m11 * m.m10;
+ result.m11 = m10 * m.m01 + m11 * m.m11;
+
+ *this = result;
+
+ return *this;
+ }
+};
+
+const bigint fibonacci(unsigned int n)
+{
+ if (n == 0) return 0;
+ else if (n < 3) return 1;
+
+ mat22 base;
+ base.m00 = 0; base.m01 = 1;
+ base.m10 = 1; base.m11 = 1;
+
+ // (base^n).m11 == (N+1)-th fibonacci number
+ return power_logN(base, n - 1).m11;
+}
+
+int main()
+{
+ while (true)
+ {
+ std::cout << "Enter number (negative number to exit): ";
+
+ int n;
+ std::cin >> n;
+
+ if (n < 0) break;
+
+ std::cout << n << "-th fibonacci number: " << fibonacci(static_cast<unsigned int>(n)) << std::endl;
+ }
+
+ return 0;
+}

Added: sandbox/SOC/2007/bigint/libs/bigint/index.html
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/bigint/libs/bigint/index.html 2007-07-15 18:37:20 EDT (Sun, 15 Jul 2007)
@@ -0,0 +1,526 @@
+<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
+<html>
+<head>
+<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
+<title>Big Integer Library</title>
+</head>
+<body>
+<h1><img src="../../boost.png" alt="boost.png (6897 bytes)"
+ align="middle" width="277" height="86">
+Big Integers</h1>
+
+<h2><a name="Contents">Contents</a></h2>
+
+<ol>
+ <li>Class bigint synopsis</li>
+ <li>Rationale</li>
+ <li>Background</li>
+ <li>Interface
+ <ul>
+ <li>Choosing the implementation</li>
+ <li>Constructors</li>
+ <li>Arithmetic operations</li>
+ <li>Bitwise operations</li>
+ <li>Input and Output</li>
+ <li>Conversions</li>
+ <li>Other functions</li>
+ <li>Serialization</li>
+ </ul></li>
+ <li>Performance</li>
+ <li>Exceptions</li>
+ <li>Internal representation</li>
+ <li>Design notes
+ <ul>
+ <li>Minimal Implementation</li>
+ <li>Limited-range integer types</li>
+ <li>Conversion from floating point</li>
+ <li>Absolute Value</li>
+ </ul></li>
+ <li>References</li>
+ <li>History and Acknowledgements</li>
+</ol>
+
+<h2><a name="Class_bigint_synopsis">Class bigint synopsis</a></h2>
+<pre>
+#include <boost/bigint/bigint.hpp>
+
+namespace boost {
+template <typename I> class bigint_base
+{
+ typedef implementation-defined bool_type;
+
+public:
+ // Constructors
+ bigint_base(); // Zero
+ bigint_base(int number);
+ bigint_base(unsigned int number);
+ bigint_base(int64_t number);
+ bigint_base(uint64_t number);
+
+ // String constructors for variable digit base; default is decimal
+ explicit bigint_base(const char* str, int base = 10);
+ explicit bigint_base(const wchar_t* str, int base = 10);
+ explicit bigint_base(const std::string& str, int base = 10);
+ explicit bigint_base(const std::wstring& str, int base = 10);
+
+ // Arithmetic operators
+ const bigint_base& operator+=(const bigint_base& other);
+ const bigint_base& operator-=(const bigint_base& other);
+ const bigint_base& operator*=(const bigint_base& other);
+ const bigint_base& operator/=(const bigint_base& other);
+ const bigint_base& operator%=(const bigint_base& other);
+
+ // Arithmetic operators
+ friend bigint_base operator+(const bigint_base& lhs, const bigint_base& rhs);
+ friend bigint_base operator-(const bigint_base& lhs, const bigint_base& rhs);
+ friend bigint_base operator*(const bigint_base& lhs, const bigint_base& rhs);
+ friend bigint_base operator/(const bigint_base& lhs, const bigint_base& rhs);
+ friend bigint_base operator%(const bigint_base& lhs, const bigint_base& rhs);
+
+ // Bitwise logical operators
+ const bigint_base& operator|=(const bigint_base& other);
+ const bigint_base& operator&=(const bigint_base& other);
+ const bigint_base& operator^=(const bigint_base& other);
+
+ // Bitwise logical operators
+ friend bigint_base operator|(const bigint_base& lhs, const bigint_base& rhs);
+ friend bigint_base operator&(const bigint_base& lhs, const bigint_base& rhs);
+ friend bigint_base operator^(const bigint_base& lhs, const bigint_base& rhs);
+
+ // Shift operators
+ const bigint_base& operator<<=(uint64_t other);
+ const bigint_base& operator>>=(uint64_t other);
+
+ // Shift operators
+ friend bigint_base operator<<(const bigint_base& lhs, boost::uint64_t rhs);
+ friend bigint_base operator>>(const bigint_base& lhs, boost::uint64_t rhs);
+
+ // Increment and decrement; both prefix and postfix forms are supported
+ const bigint_base& operator++();
+ bigint_base operator++(int);
+ const bigint_base& operator--();
+ bigint_base operator--(int);
+
+ // Unary operators
+ bigint_base operator+() const;
+ bigint_base operator-() const;
+ bigint_base operator~() const;
+
+ // Bool conversions
+ operator bool_type() const;
+ bool operator!() const;
+
+ // String conversion for variable digit base; default is decimal
+ std::string str(int base = 10) const;
+ std::wstring wstr(int base = 10) const;
+
+ // Converting from bigint to any primitive integer type, including 64-bit ones
+ template <typename T> bool can_convert_to() const;
+ template <typename T> T to_number() const;
+
+ // Comparison operators
+ friend bool operator<(const bigint_base& lhs, const bigint_base& rhs);
+ friend bool operator<=(const bigint_base& lhs, const bigint_base& rhs);
+ friend bool operator>(const bigint_base& lhs, const bigint_base& rhs);
+ friend bool operator>=(const bigint_base& lhs, const bigint_base& rhs);
+ friend bool operator==(const bigint_base& lhs, const bigint_base& rhs);
+ friend bool operator!=(const bigint_base& lhs, const bigint_base& rhs);
+
+ // Free functions
+ friend bigint_base abs(const bigint_base& value);
+ friend bigint_base pow(const bigint_base& lhs, boost::uint64_t rhs);
+ friend bigint_base div(const bigint_base& lhs, const bigint_base& rhs, bigint_base& remainder);
+ friend bigint_base sqrt(const bigint_base& lhs);
+
+ // Stream input/output
+ template <typename T, typename Tr> friend std::basic_ostream<T, Tr>& operator<<(std::basic_ostream<T, Tr>& lhs, const bigint_base& rhs);
+ template <typename T, typename Tr> friend std::basic_istream<T, Tr>& operator>>(std::basic_istream<T, Tr>& lhs, bigint_base& rhs);
+};
+
+} // namespace boost
+
+typedef bigint_base<implementation-defined> bigint;
+</pre>
+
+<h2><a name="Rationale">Rationale</a></h2>
+
+Standard C++ without third-party libraries offers support for several integer
+types, though all of them have limited range of values. This range is enough
+for majority of applications, but in some cases, which include scientific and
+cryptography-related applications, there is a need for so called "arbitrary
+precision numbers" - those are the numbers which have precision limited only by
+amount of available memory.
+
+Note that due to the lack of hardware support for abitrary precision integers,
+any operations that can be performed with them are slower than the corresponding
+operations for native (C++ built-in) types; therefore they should not be treated
+as a complete replacement for existing types, but rather as a possibility to trade
+performance for precision.
+
+There are several different third-party libraries available, they have different
+performance/portability characteristics; this library provides a numeric type
+bigint, strictly defines the set of operations that can be performed and their
+behavior, provides a portable (albeit slow) implementation of said operations; and
+also provides a implementation which uses the fastest available arbitrary precision
+library, GNU MP.
+
+The library is intended to be highly extensible and encourages developers to create
+their own implementation that would close the gap between 'portable' and 'gmp' implementations
+in terms of performance; a set of correctness and performance tests is provided to
+easen the development of such implementations.
+
+<h2><a name="Background">Background</a></h2>
+
+The bigint number class provides an implementation of integer concept. The representation
+is always exact, and there are no overflows/underflows; all operations except division by zero,
+evaluating remainder from the division by zero or evaluating square root of negative number are
+perfectly defined, and give the value that does not depend on implementation. Everything except
+the visible behavior - including in-memory representation, operations performance/memory complexity -
+depends on the implementations. Implementation authors are encouraged to provide information about
+memory requirements and performance complexities (the table for two existing implementations is
+present in this documentation) to help the user of the library choose the implementation that will
+suite his or her needs best of all.
+
+bigint class is designed so that it is compatible with the built-in integer types in the
+largest extent possible; this means that all arithmetical and logical types available are available
+for bigint class; bigint is implicitly constructible from integer types so that integer
+types can be used where compiler is expecting bigint - both in operators and functions; some
+of integer functions present in C++ standard are also redefined for bigint.
+
+<h2><a name="Interface">Interface</a></h2>
+
+<h3><a name="Choosing_implementation">Choosing the implementation</a></h3>
+
+The bigint library consists of two distinct parts - the interface class bigint_base, and a set
+of implementation classes. bigint_base is a templated class with a single template parameter - the
+actual implementation. There is a convenience typedef, bigint, which equals to bigint_base,
+parametrized by the most advanced implementation available. As library provides only two implementations
+by default, bigint is equal to GMP-based implementation if the define BOOST_BIGINT_HAS_GMP_SUPPORT
+is set in boost_config.hpp file; otherwise bigint uses the portable implementation.
+
+In most cases users should just use bigint, but if they have a need to use the specific implementation,
+they can use it like this:
+
+<pre>
+ #include "header_with_specific_implementation_class.hpp"
+
+ typedef boost::bigint_base<specific_implementation_class> bigint_special;
+
+ bigint_special a = 1, b = a * (a - 4);
+</pre>
+
+As this can change and bigint_base can be parametrized by both implementation and storage class
+in future, this section has to be revised before the project ends
+
+
+<h3><a name="Constructors">Constructors</a></h3>
+
+bigint class has three types of constructors: default constructor, constructors from built-in integer types, and
+constructors from strings.
+
+Default constructor initializes bigint class instance to zero; note that as bigint class is an implementation
+of integer concept, there is no such distinction between positive and negative zero.
+
+Integer constructors initialize bigint from build-in integer types; the result of constructor is that bigint
+instance contains the exact representation of the passed value. Note that these constructors are not declared as explicit;
+this means that you can freely use values of build-in integer types where you have to use bigint; for example, this is
+correct:
+
+<pre>
+ int a = 10;
+ boost::bigint b = 3;
+ boost::bigint c = b + a;
+ boost::bigint d = c / 49;
+</pre>
+
+bigint relies on the presence of 64-bit integer support, but this may change in the future
+
+
+String constructors initialize bigint from string in the certain format. Strings can be wide, and you can pass either
+a std::string/std::wstring or the pointer to the null-terminated character sequence. The accepted number format
+is as follows:
+
+<pre>
+[spaces][sign][digits]
+</pre>
+
+'spaces' is a group of whitespace symbols (as detected by ::isspace/::iswspace CRT functions), there can be zero or more symbols
+in it.
+
+'sign' is either an empty string, '+' or '-' symbol. '+' sign is ignored, '-' sets the number to the negative one (string "-3" will
+initialize bigint instance to -3, string "+3" will initialize it to 3).
+
+'digits' is a group of digits belonging to the character set of the base that is passed to the constructor; base is a number
+that is greater or equal to 2 and less or equal to 36; bases outside of allowed range lead to undefined results 
+perhaps we should change that and initialize number to 0 if base is < 2 or > 36?. For bases less or equal than 10,
+the character set of digits from 0 to (base-1) is used. For bases greater than 10, the character set consists of digits from 0
+to 9, and then the letters from 'A' (ASCII character 'A') to the last needed letter for the set to reach the needed size. Letters are not case sensitive.
+Letter 'A' corresponds to digit 10, letter 'B' corresponds to digit 11 and so on. Letter 'Z' (if applicable - this is an allowed
+letter only for base = 36) corresponds to digit 35.
+
+The group of digits is interpreted as a number that is written from the most significant digit to the least significant one;
+there can be an arbitrary number of zero digits ('0') preceding the group.
+
+Examples:
+<ul>
+<li>For base 2, only characters '0' and '1' can be used. String "1100" in base 2 corresponds to the number 12 (decimal).</li>
+<li>For base 10, any digit characters can be used. String "1234" in base 10 corresponds to the number 1234 (decimal).</li>
+<li>For base 16, any digit characters can be used. Additionally characters 'A'-'F' and 'a'-'f' can be used. String "Ff4a" in base 16 corresponds to the number 65354 (decimal). Note that letter case is irrelevant.</li>
+<li>For base 36, any digit characters can be used. Additionally characters 'A'-'Z' and 'a'-'z' can be used. String "ZZ" in base 36 corresponds to the number 1295 (decimal).</li>
+</ul>
+
+
+If the input string has characters that are not allowed in the input string, the first such character
+and all consecutive characters (including allowed ones) are ignored.
+If there are no digit characters before the first discarded characters, the number is initialized to 0 (for example,
+passing "-A23" as an input string and 10 as base will initialize the number to 0, as it will ignore all characters
+from 'A' onward, including 'A').
+
+<h3><a name="Arithmetic_operations">Arithmetic operations</a></h3>
+
+All of the standard numeric operators are defined for the bigint class. These include:
+
+<pre>
+ + +=
+ - -=
+ * *=
+ / /=
+ % %=
+ ++ -- (both prefix and postfix)
+ == !=
+ < >
+ <= >=
+ + (unary)
+ - (unary)
+</pre>
+
+They have the same semantics as the standard ones.
+
+Some things that have to be noted:
+
+<ul>
+<li>Division by zero (and taking remainder from the division by zero, i.e. i % 0) generates division by zero for the built-in
+int type; therefore, division by zero results in undefined behavior.</li>
+<li>Operations never produce an overflow/underflow and the result is perfectly accurate.</li>
+<li>The result of +, +=, -, -=, *, *=, ++, --, <, <=, >, >=, ==, !=, unary + and unary - operators is exactly the
+same as the result of corresponding operations for the mathematical integer concept.</li>
+<li>Division operation (/ and /=) results in so called truncated division; this means that if the dividend is not exactly
+divisible by the divisor, the result is equal to the result of real number division which is later truncated to the integer
+number which has the absolute value which is less than that of the real number quotient. Such truncation is also called rounding
+towards zero. Here are some examples to clarify the concept:
+ <ul>
+ <li>60 / 15 == 4. 60 is exactly divisible by 15, no truncation takes place.</li>
+ <li>-60 / 15 == -4. -60 is exactly divisible by 15, no truncation takes place.</li>
+ <li>60 / -15 == -4. 60 is exactly divisible by -15, no truncation takes place.</li>
+ <li>3 / 2 == 1. 3 is not exatly divisible by 2; the quotient of real number division is 1.5, it is truncated to 1.</li>
+ <li>-3 / 2 == -1. -3 is not exatly divisible by 2; the quotient of real number division is -1.5, it is truncated to -1.</li>
+ <li>3 / -2 == -1. 3 is not exatly divisible by -2; the quotient of real number division is -1.5, it is truncated to -1.</li>
+ <li>-3 / -2 == 1. -3 is not exatly divisible by -2; the quotient of real number division is 1.5, it is truncated to 1.</li>
+ </ul>
+</li>
+<li>Modulo operation (% and %=) is implemented in terms of truncated division; this means, that if a / b == c, then a % b == a - b * c. This means that:
+ <ul>
+ <li>Modulo by zero results in undefined behavior</li>
+ <li>If a is exactly divisible by b, a % b == 0</li>
+ <li>Otherwise, the sign of a % b is always equal to the sign of a.
+ </ul>
+Here are some examples to clarify the concept:
+ <ul>
+ <li>34 % 5 == 4. 34 / 5 == 6 (see above for the description of truncating division), 34 % 5 == 34 - (6 * 5) == 4.</li>
+ <li>34 % -5 == 4. 34 / -5 == -6, 34 % -5 == 34 - (-6 * -5) == 4.</li>
+ <li>-34 % 5 == -4. -34 / 5 == -6, -34 % 5 == -34 - (-6 * 5) == -4.</li>
+ <li>-34 % -5 == -4. -34 / -5 == 6, -34 % -5 == -34 - (6 * -5) == -4.</li>
+ </ul>
+</li>
+</ul>
+
+<h3><a name="Bitwise_operations">Bitwise operations</a></h3>
+
+All of the standard bitwise operators are defined for the bigint class. These include:
+
+<pre>
+ & &=
+ | |=
+ ^ ^=
+ ~ (unary)
+ << <<=
+ >> >>=
+</pre>
+
+These function operate with a bit representation of numbers. Note that though there are no strict requirements for
+storage of bigint implementations, bitwise operators are guaranteed to operate with the following representation:
+positive numbers are represented as a sequence of bits, most significant bit is first, least significant bit is last, the
+sequence of bits is equal to the representation of the number in binary number system; zero is represented as a single bit 0;
+negative numbers are represented as 2-complement of their absolute value (note that this means that negative number have an
+infinite number of 1s at the beginning; for the purpose of bitwise operations we assume that positive numbers have an infinite
+number of 0s at the beginning).
+
+Given such representation, the result of each bit operation is defined as the number representation of a bit sequence, which
+is constructed from two bit sequences of operands (to be precise, of two bit sequences, which are bit representation of the operands),
+or of a bit sequence of a single operand in case of unary operator, by applying the bitwise operator to those sequences.
+
+Examples to clarify the concept:
+<ul>
+<li>3 & 6 == 11b & 110b == 10b == 2</li>
+<li>3 | 6 == 11b | 110b == 111b == 7</li>
+<li>3 ^ 6 == 11b ^ 110b == 101b == 5</li>
+<li>-3 & 6 == -(11b) & 110b == 1....1101b & 0....0110b == 0....0100b == 100b == 4</li>
+<li>-3 | 6 == -(11b) & 110b == 1....1101b | 0....0110b == 1....1111b == -(1b) == -1</li>
+<li>-3 ^ 6 == -(11b) & 110b == 1....1101b ^ 0....0110b == 1....1011b == -(101b) == -5</li>
+<li>~(-3) == ~(-(11b)) == ~1....1101b == 0....0010b == 2</li>
+<li>-3 << 2 == -(11b) << 2 == 1....1101b << 2 == 1....110100b == -(1100b) == -12</li>
+<li>-3 >> 2 == -(11b) >> 2 == 1....1101b >> 2 == 1....11b == -(1b) == -1</li>
+</ul>
+
+
+Note that shift operators can't shift more than for 2^64 digits; this is beyond the limit of memory anyway (2^64 bits means
+2^61 bytes for storage, which is equal to 2^31 Gb of data) and is not going to change.
+
+<h3><a name="Input_and_Output">Input and Output</a></h3>
+
+Input and output operators <tt><<</tt> and <tt>>></tt>
+are provided. They meet all flags and locale requirements (that is, you
+can use <code>showpos, oct, hex</code> and other flags, decimal separators
+are also supported. Input operator stops at the first unrecognized character.
+In short, input and output operators behave exactly as you would expect them to
+behave for build-in integer types.
+
+<h3><a name="Conversions">Conversions</a></h3>
+
+There is a conversion operator to an unspecified Boolean type (most likely a
+member pointer). This operator converts a bigint to <code>false</code> if it
+represents zero, and <code>true</code> otherwise. This conversion allows a
+rational for use as the first argument of operator <code>?:</code>; as either
+argument of operators <code>&&</code> or <code>||</code> without
+forfeiting short-circuit evaluation; as a condition for a <code>do</code>,
+<code>if</code>, <code>while</code>, or <code>for</code> statement; and as a
+conditional declaration for <code>if</code>, <code>while</code>, or
+<code>for</code> statements. The nature of the type used, and that any names
+for that nature are kept private, should prevent any inappropriate non-boolean
+use like numeric or pointer operations or as a <code>switch</code> condition.
+
+Note: the provided <code>operator!</code> is not strictly necessary from the point of C++ standard,
+and is a workaround for some compilers.
+
+bigint values can be converted to strings of arbitrary base (provided it
+meets the conditions 2 <= base <= 36). The output string consists of sign
+(a symbol '-' present only if the value is negative) and of a sequence of characters
+that represent digits. This sequence consists of the same characters that can
+occur in the string passed to the string constructors of bigint; the description
+of the values and their meaning can be seen in the Constructors
+section. No unnecessary zeroes or whitespace characters are added to the output string
+(if the value is equal to 0, the string "0" is returned); all letter symbols are
+lowercase. Generally, the following always holds true:
+
+<pre>
+ bigint(value.str()) == value
+</pre>
+
+
+While bigint provides storage and operations for numbers of arbitrary precision,
+sometimes the stored values fit into C++ built-in integer types, and sometimes there's a need
+to convert from bigint to one of those types. You can check whether such conversion is
+possible via <code>can_convert_to</code> function, and convert bigint to a value of built-in
+integer type via <code>to_number</code> function. Note that if <code>value.can_convert_to<T>()</code>
+is <code>false</code>, the result of <code>value.convert_to<T>()</code> is undefined. If <code>value.can_convert_to<T>()</code>
+is <code>true</code>, the following always holds true:
+
+<pre>
+ bigint(value.convert_to<T>()) == value
+</pre>
+
+These functions work only for types which have traits in <code>std::numeric_limits</code>, and do not have to work for types
+which are longer than 64 bit even if such types are natively supported.
+
+<h3><a name="Other_functions">Other functions</a></h3>
+
+<code>abs</code> function returns an absolute value of passed parameter.
+
+<code>pow</code> function returns the passed parameter raised to the specified power. Negative powers are naturally not supported. pow(0, 0) == 1.
+
+<code>div</code> function returns both quotient and remainder for the division. The division is a truncated one; for further reference, see section Arithmetic operations.
+This function is similar to standard <code>div</code> function for integers.
+
+<code>sqrt</code> function computes a square root of the passed parameter. Passing a negative value to <code>sqrt</code> results in undefined behavior.
+
+<h3><a name="Serialization">Serialization</a></h3>
+
+bigint has built-in support for serialization via Boost.Serialization library. You need to include a separate header,
+<boost/bigint/bigint_serialize.hpp>, then you can use bigint values. The storage format is the decimal string
+representation, though this is an implementation detail and may change in future.
+
+<h2><a name="Performance">Performance</a></h2>
+
+While different bigint implementations have different performance characteristics, developers are encouraged to
+provide a table with summary performance of implemented methods. Such table for existing implementations exists here.
+N means the length of the value itself (applicable only for methods), A1, A2, etc. mean length of the function
+arguments, and M means maximum of the lengths of both value and function arguments (M = max(N, A1, A2, ...)).
+
+'Length' means number of bits for integer arguments and number of characters for strings.
+
+<table><tr><th>Function(s)</th><th>'gmp' implementation</th></tr>
+<tr><td>default ctor</td><td>O(1)</td></tr>
+<tr><td>integer ctors</td><td>O(1)</td></tr>
+<tr><td>string ctors</td><td>O(A1) check</td></tr>
+<tr><td>+, -, +=, -=</td><td>O(M)</td></tr>
+<tr><td>*, *=</td><td><= O(M2) provide more precise info</td></tr>
+<tr><td>/, /=</td><td><= O(M2) provide more precise info</td></tr>
+<tr><td>%, %=</td><td><= O(M2) provide more precise info</td></tr>
+<tr><td>&, &=, |, |=, ^, ^=</td><td>O(M)</td></tr>
+<tr><td><<, >></td><td>O(max(A1, 2A2)) NB. O(2A2) is equal to O(shift amount)</td></tr>
+<tr><td><<=, >>=</td><td>O(max(N, 2A1)) NB. O(2A1) is equal to O(shift amount)</td></tr>
+<tr><td>++, --</td><td>O(N)</td></tr>
+<tr><td>+, -</td><td>O(1)</td></tr>
+<tr><td>~</td><td>O(N)</td></tr>
+<tr><td>bool conversions</td><td>O(1)</td></tr>
+<tr><td>string conversions</td><td>O(N) check</td></tr>
+<tr><td>can_convert_to</td><td>O(1)</td></tr>
+<tr><td>to_number</td><td>O(N)</td></tr>
+<tr><td>comparison operators</td><td>O(M)</td></tr>
+<tr><td>abs</td><td>O(M)</td></tr>
+<tr><td>pow</td><td>O(A1 * A2) check</td></tr>
+<tr><td>div</td><td><= O(M2) provide more precise info</td></tr>
+<tr><td>sqrt</td><td><= O(M2) provide more precise info</td></tr>
+</table>
+
+<h2><a name="Exceptions">Exceptions</a></h2>
+
+Most implementations of bigint allocate memory for various uses (both temporary
+memory and memory for value storage); therefore any bigint function (except bigint
+destructor) may throw a <code>std::bad_alloc</code> exceptions. There are no other possible
+exceptions.
+
+<h2><a name="References">References</a></h2>
+<ul>
+<li>The bigint header itself: bigint.hpp</li>
+<li>Some example code: example.cpp</li>
+<li>The regression tests: test/</li>
+</ul>
+
+<h2><a name="History_and_Acknowledgements">History and Acknowledgements</a></h2>
+
+The library was implemented by me (Arseny Kapoulkine) as a Boost project for
+Google Summer of Code.
+
+Jeff Garland helped with different design and implementation-related things
+during the project.
+
+Jarrad Waterloo reminded me of some issues in the initial design that were
+overlooked (64-bit integer support, various bases for string conversion
+
+Phil Endecott reminded me to take special care of negative numbers in implementation
+and documentation of bitwise operators.
+
+I shamelessly stole small parts of Boost.Rational documentation (and based
+the whole structure of this file on it), which was written by Paul Moore and
+Daryle Walker.
+
+Revised June 16, 2007
+
+© Copyright Arseny Kapoulkine 2007. Permission to
+copy, use, modify, sell and distribute this document is granted provided this
+copyright notice appears in all copies. This document is provided "as
+is" without express or implied warranty, and with no claim as to its
+suitability for any purpose.
+</body>
+</html>

Modified: sandbox/SOC/2007/bigint/libs/bigint/todo.txt
==============================================================================
--- sandbox/SOC/2007/bigint/libs/bigint/todo.txt (original)
+++ sandbox/SOC/2007/bigint/libs/bigint/todo.txt 2007-07-15 18:37:20 EDT (Sun, 15 Jul 2007)
@@ -13,8 +13,8 @@
1. Bigint interface (header) 21 May Awaiting resolution
2. GMP implementation 21 May Awaiting resolution
3. Correctness tests 7 June In progress
-4. Documentation 21 June N/A
-5. Performance tests 7 July N/A
+4. Documentation 21 June In progress
+5. Performance tests 7 July In progress
4. Interface for storage 14 July N/A
5. Storage implementation 14 July N/A
6. Default implementation 30 July N/A
@@ -175,8 +175,8 @@
functions to GMP and having them throw an exception is not a generic solution, because GMP is not exception safe. However, it
may be a solution IF own allocation is performed - depends on where allocations are done - needs further investigation.

-Alternatively, only parts of GMP that actually are thread safe may be rewritten (if they do not include system layer (mpn), of
-course).
+Alternatively, only parts of GMP that actually are not exception safe may be rewritten (if they do not include system layer
+(mpn), of course).

-----------------------------------------------
Extra features:
@@ -187,3 +187,4 @@
- getting several bits from an integer (say, 7 bits from 4859-th one). Perhaps, assigning several bits.
- conversion from/to floating point (float, double, long double)
- other styles of division (for now there's only truncating; floor and/or ceil perhaps?) & modulo
+- bigint relies on the presence of boost::uint64_t and therefore will not compile if there's no 64-bit integer support

Next message: zeux_at_[hidden]: "[Boost-commit] svn:boost r7440"
Previous message: jakevoytko_at_[hidden]: "[Boost-commit] svn:boost r7438"

Date view	Thread view	Subject view	Author view

Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk