Bignum Challange

[Duthomhas]

(or is this behaviour unportable?)

Yes, that is the problem -- not all hardware is two's complement.

That said, AFAIK C++ practically requires you to be using two's complement hardware... so it may be a moot point after all.

Fooey.

[edit] Foo, I just reread this and realized that my brain broke and that's some circular reasoning there...

The real reason is that it is not portable because it is a variable response across two's complement platforms to negate the maximally negative value... (I think I've already said this.)

Sorry! :-\

[D80DSL3A]

@hamsterman. I got what you meant about the more important reason for the constructor
BigInt(int x);// for given integer value after 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:

friend BigInt operator+(const BigInt& x, const BigInt& y);
friend BigInt operator-(const BigInt& x, const BigInt& y);	
friend BigInt operator*(const BigInt& x, const BigInt& y);	
friend BigInt operator/(const BigInt& x, const BigInt& y);
friend BigInt operator%(const BigInt& x, const BigInt& y);

After some experimenting I realized that the friend functions give me the greatest flexibility in combining operands as either BigInt and BigInt or as int and BigInt or as BigInt and int.
Thank you very much for the tip!

[tition]

Hey guys,

I have also been using (for a year and a half now) Large-Integer and Large-Rational classes of my own. (sorry for not joining this topic earlier :)

Here are a couple of things I noticed about my classes after I had already written the main functionality.

1. It is a very good idea to make your BigInt class as small as possible. The best option to me was 8 bytes (on a 32 bit machine) - 4 bytes for the int value, and 4 bytes for a pointer to a structure. The pointer has value zero if the BigNum fits in 4 bytes. If it doesn't, you create using new a data structure which contains all your std::vectors, etc.

The reason for this optimization: I have to store several hundred millions of Large-Rationals, however almost all numbers are relatively small (99.9% of my LargeInts fit into 4 bytes).

2. When you separate your BigNum into two - an int and 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.

[Bazzy]

Now I'm trying to implement a bignum class in which the base on which digits are represented is arbitrary as well.
It will be fun!

[chrisname]

That sounds hard. I'm not really the maths type, so I'm abstaining from this competition. I don't know that I could do it anyway.

[Duthomhas]

Just so you all know, I haven't forgotten this topic. I've been compiling results for you all to see.
It is late for me now and I still have to do some more benchmarking (I've only done a preliminary pass), but by tomorrow evening (about 2010 Dec 15 03:00 GMT) I'll have some stuff for you all.

(For speed, it looks like m4ster r0shi and fun2code blow everyone else out of the water.)

Until then!

[z05DSL3A]

Duoas

Can you post the test/benchmark harness when you are done? I have not had the time to finish my code but would like to run it against your benchmarks when I do.

[Duthomhas]

Finally! Sorry for the late response -- I've been rushing to get it to you all.

The challengers in this contest were:

  Bazzy
  Duoas
  fun2code
  hamsterman
  m4ster r0shi

The final report and all the code can be found here:
http://home.comcast.net/~mlyn7576/bignum-challenge/

Some additional notes about the entries, in no particular order:

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

I expect to move that page I created someday, so here are the final report tables in text:

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!) 

Thanks

I'd like to thank everyone who participated. I learned a lot of stuff, and had fun.

I was surprised that everyone provided a regular multiplication algorithm. When I devised the contest, I expected to have to write some 'multiplication by repeated adding' stuff to use the entry codes. Perhaps I'll revisit this real soon and we can play with optimized multiplications and work towards more advanced bignum systems.

Also, don't consider this the end of it all. Even if you did not participate in this challenge, you should try to make your own bignum anyway. It really is not that hard! Post back here as you go to ask questions or make suggestions, and have fun!

--Michael Thomas Greer

[Bazzy]

I realised the bugs in addition subtraction just yesterday :^)
When trying to get division working on arbitrary-base bignum
- That shows how much I tested my code ;^P -

[hamsterman]

a little update - decimal input/output.
http://pastebin.com/7NdegbD8

few notes about your notes. In one variant I used vector of chars for digits 0...9, in another I a vector of unsigned ints for digits 0...2³²-1. Now that I have decimal io, my unsigned int version is usable (I haven't tested it a lot though. there may be some errors..) The decimal version was somewhat more of an attempt than a submission. Hence that constructor fail.

[z05DSL3A]

Thanks Duoas, this has been very interesting.

Although I have not finished my code, reading around the subject has lead me to to a renewed interest in Cryptology, more precisely Cryptanalysis. Back in the day this subject was a lot harder to get information on.

For months I have been trying to think of something to do in my down time that would give me opportunities to learn new/practice old skills (including areas of maths and parallel processing [possibly with CUDA or MPI]) and be something that can last a long time.

[D80DSL3A]

Thank you Duoas for hosting this fun competition!
May I ask a couple of questions about my results?

Quote from above:

- no copy constructor, and many of his operators don't work right

1) Isn't this a copy constructor (prototype only given here) ?
BigInt(const BigInt& x);
I have that in my class.

2) Could you please supply an example where an operator of mine didn't work right?
I haven't found any cases myself yet. Aside from operator< all of mine are for arithmetic functions. It looks like you didn't do any testing of division operators so that leaves just +, - and *. ( actually, I found a bug in my / operator - it was failing for numerators < 10000. Now fixed. )
I ran every test case from your TestAddition(), TestSubtraction(), TestMultiplication() and TestFactorial() functions found in your test harness and I get all of them correct. Were there other tests done that I maybe didn't see there? Did the failures occur during the time tests?

I can think of one explanation. Were you getting some incorrect result = 0 cases? This would happen if a BigInt were Instantiated as BigInt x = 99;// for example due 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.

Thanks again for the contest!

[Duthomhas]

Oops! Yes, you have a copy ctor, and I knew it. It was late and I think I just put that in the wrong spot or I jumped the gun. You are correct: I did not test division. Your arithmetic operators all work fine -- as you see from the test harnass. The problem is with one or more of your assignment operators -- I had an extremely difficult time working with the factorial function. As you can see, I eventually went to using a machine int for the loop variable. (I had to do this with a number of entries.)

Keep in mind that the test code was designed so that your class works. If all the classes worked exactly right all the time (even mine has a bug I need to figure out), then the factorial function would look like this:

Number FactorialFunction( const Number& n )
  {
  Number result = 1;
  while (n)
    {
    result *= n--;
    }
  return result;
  }

I only messed with the entry classes enough to satisfy the contest results... and my comments were only directed in the difficulties I had accomplishing that task. Your code was one of the more difficult to work with, alas. I really don't have much time to mess with them further. Keep in mind, though, that it is small things that make such a big difference. I didn't analyze exactly what small things were affecting your code so badly. (Sorry!)

You did a very good job, so don't be offended by my mistake. :-\

[D80DSL3A]

No worries! Thank you for the very considerate reply.

I just wanted to find out what's broke so I can fix it. I'll look into my assignment operators. Sorry that my class was difficult to use. The FactorialFunction() you gave above gives me a direction to go in for further development.

For further fun (in the hunt for ways to apply a BigNum class) I found a recent thread dealing with Fibonnaci numbers, which grow quite large fast. The poster was trying to find the 10,000th fibonnaci number, which is 2,090 digits long. Here is the function I wrote for finding them:

BigInt Fibonacci( int N )
{
	BigInt fibs[3];
	fibs[0] = 0;
	fibs[1] = 1;
	for(int j=2; j<=N; j++)
		fibs[j%3] = fibs[(j-1)%3] + fibs[(j-2)%3];// so the elements are cycled as needed
	return fibs[N%3];
}

see you on the boards! -fun2code

[Bazzy]

BTW what's so special about my constructors/assignment to get 2.0 points?
My design guideline was the easiest thing to code, I didn't expect that much.

[Duthomhas]

You have somehow magically overloaded signed and unsigned int ctors. I still can't get that to work, and it drives me nuts! That's what the 2 points is about.

Technically, you don't need a const char* constructor, since you've got a const std::string& ctor.

[chrisname]

Duoas wrote:

You have somehow magically overloaded signed and unsigned int ctors

Burn the witch!

[Bazzy]

I thought that the std::string one would handle char* but the line
simple_decimal_bignum n = "123456";
gives an error without const char* ctor

error: conversion from ‘const char [7]’ 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>

I was quite surprised when that error appeared so I added the last constructor
Further experimenting showed that with a function-like call of the ctor this doesn't give problems but I badly needed the = one :^)

[Duthomhas]

I've really been bothered by this issue for a while now, and so I finally took the time to figure it out.

The reason for statements like "conversion from 'foo' to 'baz' is ambiguous" is that the compiler, after inspecting available methods, discovers that it has more than one way to do what you are asking for, and so instead of just choosing one, it barfs. Now, I can see why compiler designers would like this kind of behavior, but when integer type promotion gets involved then life gets stupid.

Here is what I used to play with it:

#include <iostream>
#include <limits>
#include <string>
using namespace std;

struct A
  {
  A() { cout << "ctor default\n"; }


  A( unsigned long n ) { cout << "ctor unsigned long = " << n << "\n"; }
  A( signed long n ) { cout << "ctor signed long = " << n << "\n"; }
  A( const A& a ) { cout << "ctor copy\n"; }
  A( const string& s ) { cout << "ctor string = " << s << "\n"; }



  A& operator = ( unsigned long n ) { cout << "assign unsigned long = " << n << "\n"; return *this; }
  A& operator = ( signed long n ) { cout << "assign signed long = " << n << "\n"; return *this; }
  A& operator = ( const A& a ) { cout << "assign copy\n"; return *this; }
  A& operator = ( const string& s ) { cout << "assign string = " << s << "\n"; return *this; }

  };

#define F( x ) cout << # x << " : "; x

int main()
  {
  string s = "greetings!";
  F( A a );
  F( A b( 7 ) );
  F( A c( numeric_limits <unsigned long> ::min() ) );
  F( A d( numeric_limits <unsigned long> ::max() ) );
  F( A e( numeric_limits <signed long> ::min() ) );
  F( A f( numeric_limits <signed long> ::max() ) );
  F( A g( "hello!" ) );
  F( A h( s ) );

  F( a = 7 );
  F( b = numeric_limits <unsigned long> ::min() );
  F( c = numeric_limits <unsigned long> ::max() );
  F( d = numeric_limits <signed long> ::min() );
  F( e = numeric_limits <signed long> ::max() );
  F( f = "hello!" );
  F( g = s );
  }

The offending lines (the ones that cause compile errors) are lines 31 and 39 -- with the bare integer '7'.

The compiler takes said integer as an int. Without an int constructor, it must type-promote it to something larger -- but there are two constructors taking larger values: unsigned long and signed long. Hence, the compiler complains that you are giving it ambiguous input.

So, a little fix:

#include <iostream>
#include <limits>
#include <string>
using namespace std;

struct A
  {
  A() { cout << "ctor default\n"; }
  A( unsigned n ) { cout << "ctor unsigned int = " << n << "\n"; }
  A( int n ) { cout << "ctor signed int = " << n << "\n"; }
  A( unsigned long n ) { cout << "ctor unsigned long = " << n << "\n"; }
  A( signed long n ) { cout << "ctor signed long = " << n << "\n"; }
  A( const A& a ) { cout << "ctor copy\n"; }
  A( const string& s ) { cout << "ctor string = " << s << "\n"; }

  A& operator = ( unsigned n ) { cout << "assign unsigned int = " << n << "\n"; return *this; }
  A& operator = ( int n ) { cout << "assign signed int = " << n << "\n"; return *this; }
  A& operator = ( unsigned long n ) { cout << "assign unsigned long = " << n << "\n"; return *this; }
  A& operator = ( signed long n ) { cout << "assign signed long = " << n << "\n"; return *this; }
  A& operator = ( const A& a ) { cout << "assign copy\n"; return *this; }
  A& operator = ( const string& s ) { cout << "assign string = " << s << "\n"; return *this; }

  };

#define F( x ) cout << # x << " : "; x

int main()
  {
  string s = "greetings!";
  F( A a );
  F( A b( 7 ) );
  F( A c( numeric_limits <unsigned long> ::min() ) );
  F( A d( numeric_limits <unsigned long> ::max() ) );
  F( A e( numeric_limits <signed long> ::min() ) );
  F( A f( numeric_limits <signed long> ::max() ) );
  F( A g( "hello!" ) );
  F( A h( s ) );

  F( a = 7 );
  F( b = numeric_limits <unsigned long> ::min() );
  F( c = numeric_limits <unsigned long> ::max() );
  F( d = numeric_limits <signed long> ::min() );
  F( e = numeric_limits <signed long> ::max() );
  F( f = "hello!" );
  F( g = s );
  }

Compiles great! But wait! There's more! As part of our special TV offer, we give you more reasons to be annoyed.

Try changing those bare integer constants to something like: -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

which is fine and dandy (I suppose???, it is, after all, a negative constant value), but running the program shows that my compiler (GCC) treated it as unsigned anyway...

I can only fix it by using a specific cast like (signed long)(-2147483648) or 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.

It kind of defeats the purpose for the weird two's complement numbers like MIN_INT, but at least the normal ability to distinguish between signed and unsigned bare integer constants is better than it was originally...

Good grief.

[Alrededor]

New poster here. I downloaded MS Visual C++ 2008 Express (since upgraded to 2010 Express) in early 2009. I stumbled on this site using Google when looking for the exact prototype of some function in the string library (it was easier than looking it up in a book). I liked the C++ reference and so bookmarked the site and eventually started following the forums. Then when Duoas posted his Bignum challenge I decided to give it a try.

I chose a binary implementation using boost dynamic_bitset. Since we expect to be able to do i/o in decimal, choosing any base other than ten or a power of ten means implementing two forms of division just to do input and output. Consequently, I didn't make the deadline for the challenge, but that has provided me the opportunity to make a more complete class.

I am strictly amateur and not a professional programmer. I am familiar with two's complement representations, but I deliberately refrained from looking for algorithms on line so the algorithms are my own, implemented very much the way a human does arithmetic. The base two probably makes the operations fairly slow, however I think the algorithms can be modified slightly to provide an 8-bit, 16-bit and perhaps a 32-bit base. I may make a stab at a generic solution using templates with perhaps a few template specializations as needed.

Below is the comment at the beginning of the class header file:

/*
The BigInt class provides an extension of the built-in integral types to integers
of arbitrary size. Constructors are implemented from the built-in integral
types together with a string constructor. The format for a valid string is

"[ base identifier ][ sign ] number "

base identifiers can be:

'b' or 'B' for binary
'x' or 'X' for hex
'd' or 'D' for decimal

sign can be '+' or '-'

A string with no base identifier defaults to decimal and no sign defaults
to positive. The internal storage mode is binary using boost dynamic_bitset.

A fairly full set of assignment, compound assignment and comparison operators
has been implemented together with overloads of the output and input operators.
The following manipulators have been defined for the output operator:

bigintbin
bigintdec
biginthex
bigintupper
bigintlower
bigintshowbase
bigintnoshowbase
bigintdefault

The default is bigintnoshowbase bigintdecimal.


Manipulators for the input operator are:

bigintbin
bigintdec
biginthex
bigintdefault

The default is decimal. The input manipulators only affect the treatment of
a string with no base identifier. Formatted strings that include a base
identifier can be correctly input without regard to any manipulators set.

Exceptions:

The string constructor will throw std::invalid_argument if passed an invalid
string. The offending string is incorporated into the what() message.
Strings can be tested by calling the function isValidBigIntString().
The assignment operator which takes a string for rhs may also throw because
it calls the BigInt string constructor implicitly.

An attempted to divide by zero will throw std::domain_error.
*/

For anyone who wishes to look the following are links to the source code on pastebin:

BigInt.h and BigInt.cpp http://pastebin.com/Db1LFxtL

Test_BigInt.h and Test_BigInt.cpp http://pastebin.com/haDuYJL6

The test code uses the boost unit_test library and while not exhaustive is fairly extensive.
Thanks for the challenge.