19th May
2010
written by admin

The Idea

A lot of the problems that I keep attempting on projecteuler.net require more bits than than unsigned __int64, so I started thinking about making my own LargeInt class.  For the particular problem I’m solving I need the following operators.

  • operator*
  • operator=
  • operator+
  • operator
  • operator<
  • operator>
  • operator==

I need to be able to have numbers of nearly infinite size with fast indexing to perform operations on.  I decided to utilize the vector class in the Standard Template Library, but you can pretty much use any dynamic array.

Implementation

Because of the way I build my numbers I work in reverse index order for example in the number 111119, number[0] would be equal to 9.  I began working out an algorithm to multiply two infinitely large numbers together and the idea of it is actually pretty simple.

  1. Create a temporary buffer to hold the result.
  2. Loop through all the digits of the smaller number and multiply by each of the digits by the largest number.
  3. Add the number to the buffer if a number doesn’t exist, otherwise add the new value onto it.
  4. Cleanup the buffer and make sure no digit is over 9
  5. Add any additional carried values over to the buffer
  6. Build a new LargeInt using the new buffer.

This works out perfectly, but the time complexity is O(n*n) or more accurately O(n*m) where n is equal to the largest number of digits, and m is equal to the smallest number of digits.  Is there a way to do this in O(n) time?  I’m not sure yet but I am looking for some ideas.  In general though for my solution i am currently more worried about correctness than optimal performance in the class, as the algorithm I’m trying to solve will be more expensive than the LargeInt operators.

Conclusion

I have a class that can perform all the operations above on nearly any size positive integers, but it comes at a tremendous cost.  Here are the costs of each operator (n = digits1, m = digits2):

  • operator*  Cost: O(n*m)
  • operator= Cost: O(n)
  • operator< Cost: O(n)
  • operator> Cost: O(n)
  • operator+ Cost: O(n)
  • operator–  Cost: O(n)
  • operator== Cost: O(n)

As you can see the worst case is really bad for multiplying numbers together, the others are fairly efficient, but generally have a much higher better case sometimes at a constant speed of 1.  I was able to use this class to solve several of the problems on ProjectEuler.net.

Whats Next

Division, I really needed this to solve one of the problems I attempted at Project Euler, but I ended up being able to restructure the formula to get around needing it.  I’m also hoping at some point to have the class complete enough to release to the public so I can continue to refine it after getting some feedback.