|(or is this behaviour unportable?)|
BigInt(int x);// for given integer valueafter your 2nd reply about it. I had no idea that c++ would use it to automatically convert an integer argument to a BigInt. I have implemented this and now have just one operator for each basic operation. They are:
newa data structure which contains all your std::vectors, etc.
intand a pointer to a structure if the int does not suffice - you gain an extra optimization. What you can do is, when asked to multiply, check whether both BigNum's are smaller than 15 bits. If both are, you can use the regular multiplication, if not, you use the elementary school multiplication algorithm that was discussed in the previous posts.
fun2code 'BigInt' class implementation notes: - dynamically allocated array of integers in 0..9999, plus boolean value for sign, and a non-synchronized string representation - no copy constructor, and many of his operators don't work right - no streams I/O -- uses member functions to dump directly to 'cout' - no direct equality operator (used available less operator to construct one) - rudimentary test suite (good job!) compilation notes: - g++ -Wall -ansi -pedantic -O2 test-fun2code.cpp - minor warnings about unused variables
hamsterman 'integer' class implementation notes: - vector of char in either 0..9 (decimal) or 0..15 (hexadecimal), plus boolean value for sign - integer assignment operator only works for single digits - must use streams to convert numbers to/from string compliation notes: - g++ -Wall -ansi -pedantic -O2 test-hamsterman-2.cpp - minor warnings about comparison of signed and unsigned values and use of assignment in boolean expression
Bazzy 'simple_decimal_bignum' class implementation notes: - std::string of signed char in 0..9, plus boolean value for sign - very complete set of constructors and assignment operators, including signed and unsigned integer methods (I learned something!) - error in addition and subtraction with bignums -- I had to implement factorial using int (and the ctor overhead probably contributed significantly to your times). Play with 99+1 and 100-1. - very clean code, implemented with both header and source files compilation notes: - g++ -Wall -ansi -pedantic -O2 test-Bazzy.cpp
m4ster r0shi 'BigInt' class implementation notes: - vector of int in 0..9 - Karatsuba algorithm not integrated into operator* (Long Multiplication) - very nice, clean use of STL - clean, easy to read code - not namespace safe (requires trivial fix) - no int ctor, only std::string - no comparison operators - no negative numbers compilation notes: - g++ -Wall -ansi -pedantic -O2 test-m4ster-r0shi.cpp
Duoas 'bignum' class implementation notes: - std::string of char in 0..9, plus boolean value for sign - error in subtraction algorithm (to be fixed) compilation notes: - g++ -Wall -ansi -pedantic -O2 test-Duoas.cpp
Points 1. Positive and negative numbers 2. Copy construction and assignment to/from normal integers and other bignums 3. Conversion to/from textual representation 4. Addition and subtraction 5. Multiplication 6. Other cool things, like division 7. Error handling Author / Point 1 2 3 4 5 6 7 TOTAL fun2code 1.0 0.52 1.0 1.0 1.0 0.53 0.01 5.0 hamsterman 1.0 0.54 1.0 1.0 1.0 0.55 0.01 5.0 Bazzy 1.0 2.06 0.57 1.0 1.0 1.05 0.01 6.5 m4ster r0shi 0.0 0.58 1.0 1.59 1.5 0.0 0.01 4.5 Duoas 1.0 1.0 1.0 1.0 1.0 1.05 0.01 6.0 Everyone's bignum class was capable of computing 100!, so no additional points will be given for it. I liked hamsterman's nice code to calculate any factorial the user desired. It was, difficult, however, to make everyone's factorial function actually work. Notes: 1. I didn't have time to do a whole lot of testing against proper error handling, so I've ignored it here. :( Sorry. 2. For some reason fun2code made a constructor that directly handles internal state instead of directly turning an integer into a BigInt. He did supply an assignment operator for it, at least. Also, a lot of his operators are broken, alas. Half a point. 3. Less-than operator. Half a point. 4. No copy constructor. Assignment from integer is limited to single-digit values (magnitude <= 9). Half a point. 5. Complete set of relational operators. Hamsterman's need debugging. 6. Bazzy's nice set of ops here gets him two points. 7. But his addition and subtraction algorithms lose him half a point. :( 8. Default copy constructor and assignment operator only. Half a point. 9. Brilliant use of STL. Our discussion on the forum and your times encouraged me to be more STL-oriented. You only get a half point extra though, because you used std::transform() with a stateful operation. :(
Times Performance is also critical. So here is a chart. Since everyone except fun2code used a simple base-ten, I've included his un-adjusted (radix 10000) results as well as his adjusted (radix 10) results. Because of his large radix, he clearly has some nice results. All values are number of operations per digit per second, except for the Factorial function, which is just the time it took to calculate n! (That means that the bigger the number, the better.) The numbers under the function name are the number of digits used for the calculation, or in the case of the Factorial function, the argument value. I've run everyone's tests several times, and for each test I've chosen the most impressive number... Nevertheless, remember that you may get different results on your system -- these are relative numbers. \ Function Addition Subtraction Multiplication Factorial Author 10000 10000 100, 1000,10000 100!,1000!,10000! fun2code (radix=10) 154798761 261780105 3125000,312500,42194 5128.21,74.07, 0.58 fun2code (r=10000) 15480 26178 313, 31, 4 hamsterman 41841004 68166326 233100, 24272, 2345 292.83, 2.43, 0.02 Bazzy 45892611 565931 120773, 14045, 1471 817.66, 5.76, 0.03 m4ster r0shi (long hand) 21473051 137362637 378788, 22883, 2449 1443.00, 6.44, 0.03 m4ster r0shi (karatsuba) 370370, 22989, 2463 809.72, 6.11, 0.03 Duoas 97943193 63775510 393701, 21277, 2141 1646.82, 8.04, 0.04 Remember, the factorial results are surely affected by the loops I had to jump to make everyone's code actually calculate the factorial. Some performance times may be improved somewhat by less gratuitous hoop-jumping. (Hey, I left the hoop jumping in my code too!)
|- no copy constructor, and many of his operators don't work right|
BigInt(const BigInt& x);
BigInt x = 99;// for exampledue to my odd BigInt(int) constructor. This would allocate enough array elements to hold a 99 digit #, not assign the value 99. My bad on the design flaw there. Initialization can't be done this way. But I don't see any initializations being done this way in your test code, so I am stumped.
|You have somehow magically overloaded signed and unsigned int ctors|
simple_decimal_bignum n = "123456";
error: conversion from ‘const char ’ to ‘simple_decimal_bignum’ is ambiguous note: candidates are: simple_decimal_bignum::simple_decimal_bignum(int) <near match> note: simple_decimal_bignum::simple_decimal_bignum(long int) <near match> note: simple_decimal_bignum::simple_decimal_bignum(long unsigned int) <near match>
-2147483648(or whatever the program printed as MIN_INT when you ran it). Now I get the message
|warning: this decimal constant is unsigned only in ISO C90|
static_cast<signed long>(-2147483648). (Note that I can use the "UL" constant modifier to force an unsigned value, but using the "L" modifier does not work to force a signed value.) I get the same stupid warning message, but at least the proper constructor/assignment operator is used.