HugeInt (BigInt) optimization

This is a discussion on HugeInt (BigInt) optimization within the C++ Programming forums, part of the General Programming Boards category; A few of you have mentioned in the "Division Algorithm" thread that you've your own BigInt type classes. I'd just ...

  1. #1
    Magically delicious LuckY's Avatar
    Join Date
    Oct 2001
    Posts
    856

    HugeInt (BigInt) optimization

    A few of you have mentioned in the "Division Algorithm" thread that you've your own BigInt type classes. I'd just like to know two things:
    1) How you store your data and what kind of data it is
    2) The speed of performing large calculations (examples: factorial 1200, for i = 0 to 1000 2^i)
    If it's too inconvenient you don't have to go out of your way to determine actual time in seconds (but if you could it would help); a relative estimate would do.

    I'm curious because I've been working on a HugeFloat class that has been working very well. I started thinking about starting from scratch because the code for most functions is very long and complex and I've been doing some reading and thought perhaps storing the data with a large base might yield simpler algorithms yet maintain fast speeds. I just wrote a simple class storing data using base 65536 and it performs horribly. My HugeFloat class can perform factorial 1200 in under a second and print out from i = 0 to 1000, 2^i in about 8 seconds, but the new class cannot even calculate 2^8 within several minutes (that's when I killed it).

    Your thoughts?

  2. #2
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    Powers of integers can be optimized heavily.

    Example:
    Code:
    x^276  =  x^100010100b = x^256 * x^16 *x^4  = 
    
    = (..(x^2)^2)^2)^2)^2)^2)^2) * (..(x^2)^2)^2)^2) * (x^2)^2
    This improves performance a lot. Only 14 multiplications are done when raising x to the power of 2.
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  3. #3
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    And if you use binary internal representation, powers of two can be calculated in constant time.

    2^n = 1000...00 (n zeroes)
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Turn Off Optimization?
    By danlee58 in forum C Programming
    Replies: 6
    Last Post: 12-10-2008, 02:52 AM
  2. need reading material for c++ database optimization
    By elninio in forum C++ Programming
    Replies: 0
    Last Post: 07-24-2008, 11:32 PM
  3. Hugeint Class Problem
    By chottachatri in forum C++ Programming
    Replies: 2
    Last Post: 03-29-2008, 07:46 PM
  4. Optimization settings
    By Roaring_Tiger in forum C Programming
    Replies: 4
    Last Post: 02-23-2005, 01:53 AM
  5. bigInt help
    By noob2c in forum C++ Programming
    Replies: 14
    Last Post: 10-10-2003, 08:18 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21