Thread: large binary number division

  1. #1
    Registered User
    Join Date
    Apr 2006
    Posts
    13

    large binary number division

    Hello,
    I am trying to divide a large binary number (54 bits) with another binary number (10 bits). Can some one please suggest what would be the fastest (in terms of execution speed) way to accomplish this?
    I plan to store my numbers in arrays of integers/strings:
    A=[1,0,1,1,0,.....0,1,0] - 54 bits
    B=[1,1,1,0...0,1,0] - 10 bits

    Thanks.

  2. #2
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    Code:
    #include <stdint.h>
    
    int main(void)
    {
      uint64_t num1 = some_big_number, num2 = some_other_big_number;
      uint64_t result;
    
      result = num1/num2;
    
      return 0;
    }
    If you're looking for speed, I sure as hell wouldn't store the number in binary representation in a string.
    Last edited by itsme86; 08-08-2006 at 01:03 AM.
    If you understand what you're doing, you're not learning anything.

  3. #3
    Hardware Engineer
    Join Date
    Sep 2001
    Posts
    1,398
    I plan to store my numbers in arrays of integers/strings:
    A=[1,0,1,1,0,.....0,1,0] - 54 bits
    B=[1,1,1,0...0,1,0] - 10 bits
    itsme86 is right. That's slow, inefficient, and it's the "hard way".

    Binary is a little tricky, because (unlike octal & hexadecimal) it's not built into cin & cout.

    Inside the computer, everything is already binary. It doesn't care if you consider it to be binary decimal, hex, etc.... You can input a decimal number and an octal number, add them together and display the result in hexadecimal without worrying about mixing bases! To the computer/compiler, they are just integers.

    There are two issues:
    1- You need to be able to handle 54 bit numbers. If your platform can't handle it, you may need a 3rd-party big number library.

    2- You need to get your input / output in binary form.

    For input, there is a standard C library function strtoul() that can convert (almost) any base to a regular integer. This may work for you, depending on the size of an unsiged long on your computer.

    For output/display, there is a C++ STL component called <bitset>. It can be used to display an integer in binary. Again, I'm not sure if there is a limit on the number of bits.

    Here are some code fragments from a program that works with smaller integers:
    Code:
    #include <bitset>
    
    int main()
    {
        const int MAX_BITS = 8;     // Limit to one-byte to make binary readable
        int Base, x;
        char InputString[40];
        char OutputString[40];      // For itoa()  [Microsoft only]
        char *pEnd = NULL;          // Required for strtol()
    
          
        cout << "Base? (2-36, 0 to exit) " ;
        cin >> Base;
    
        if(!Base)
              return 0;
    
        cout << "Number? ";
        cin >> InputString;
        x = (int)strtol(InputString, &pEnd, Base);     // String to long
        
        cout << endl;
                          
        cout << "\t" << dec << x << "\t\t Decimal" << endl;
        cout << "\t" << oct << x << "\t\t Octal" << endl;
        cout << "\t" << hex << x << "\t\t Hex" << endl;
        cout << "\t" << bitset<MAX_BITS>(x) << "\t Binary (LSB)" << endl;
    (The above sample uses strol() instead of stroul(). )

  4. #4
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    Note that there is also a strtoull() function that works on unsigned long long integers.
    unsigned long long int strtoull(const char *nptr, char **endptr, int base);
    If you understand what you're doing, you're not learning anything.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Number Guessing
    By blacknapalm in forum C Programming
    Replies: 2
    Last Post: 10-01-2008, 01:48 AM
  2. What's problem of adding two binary number?
    By Mathsniper in forum C Programming
    Replies: 1
    Last Post: 01-12-2007, 06:12 AM
  3. Logical errors with seach function
    By Taka in forum C Programming
    Replies: 4
    Last Post: 09-18-2006, 05:20 AM
  4. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  5. Prime number program problem
    By Guti14 in forum C Programming
    Replies: 11
    Last Post: 08-06-2004, 04:25 AM