divide ULONGLONG ?

Posted on 2003-03-18
Medium Priority
Last Modified: 2012-05-04
Cfile::GetLength() returns a ULONGLONG.

I need to divide this value... how do i do it???


c = a/b;

How do i cope with the insane amount of bits?? :D

Question by:dave_p_r_b
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions

Expert Comment

ID: 8159998
This is the definition of a LONGLONG (similar for ULONGLONG)

typedef union _LARGE_INTEGER {
  struct {
     DWORD LowPart;
     LONG  HighPart;
  LONGLONG QuadPart;

The following is an example of how to manipule large numbers, you can beautify the multiplication by 4294967296 if you want using arithmetic shift or any other way but it is not the main issue.

  // as we work with very large numbers we need to divide the number before we make
  // mathematical manipulation with them
  // we return a percentage.
  short space_on_disk(string drive_path)
    ULARGE_INTEGER freeBytesAvailableToCaller;
    ULARGE_INTEGER totalNumberOfBytes;
    ULARGE_INTEGER totalNumberOfFreeBytes;

    if (!GetDiskFreeSpaceEx(drive_path.c_str(),  
       throw IOError("space_on_disk");
    unsigned __int64 i;
    unsigned __int64 j;

    i = totalNumberOfFreeBytes.LowPart;
    j = totalNumberOfFreeBytes.HighPart * 4294967296;

    __int64 m = j + i;

    i = totalNumberOfBytes.LowPart;
    j = totalNumberOfBytes.HighPart * 4294967296;

    __int64 n = j + i;

    return short((m / 100) / (n / 10000));

Hope this helps
LVL 12

Accepted Solution

Salte earned 200 total points
ID: 8160498
Actually ULONGLONG is fine.

Most modern compilers provide a 64 bit integer.

GNU GCC C++ and C compilers use the name

long long x; // signed 64 bit integer
unsigned long long x; // unsigned 64 bit integer

MSVC and Borland C++ builder uses the names

__int64 x; // signed 64 bit integer
unsigned __int64 x; // unsigned 64 bit integer.

To make code that works on both compilers you are adviced to make a typedef which goes something like this:

#if _GNU_
typedef long long int64_t;
typedef unsigned long long uint64_t;
#else // assume MSVC or BCB
typedef __int64 int64_t;
typedef unsigned __int64 uint64_t;

If you have something that is neither GNU, nor MSVC, nor Borland C++ builder but it also provide a 64 bit integer you just have to make the #if a bit more fancy.

Then the question about dividing the values are simply:

uint64_t a;
uint64_t b;
uint64_t c = a / b;

All those compilers provide support for +, -, *, / and % on 64 bit integer data types both signed and unsigned.

What if your compiler do NOT provide support but you still want to do it? what then?

Easy enough:

Step 1. define a struct to hold the data:

struct uint64_t {
   unsigned int low;
   unsigned int high;

You might want to switch 'low' and 'high' if you're on a machine with different endianess than a pentium processor.

Then the answer is simply:

uint64_t operator / (const uint64_t & a, const uint64_t & b);

For the body of this function the following must be kept in mind:

A 64 bit value represented as two 32 bit values is simply:

V = H * R + L

Here V is the value of the 64 bit integer.
H is the high 32 bit part (high in that struct above).
L is the low 32 bit part (low in that struct above).
R is the value pow(2,32) or 2 raised to the power of 32.

If you have two such values A and B, B > 0 then you can find a quotient Q and a remainder R such that:

A = Q * B + R.

0 <= R < B

If Q == QH * R + QL, A == AH * R + AL, B == BH * R + BL and R == RH * R + RL this becomes:

AH * R + AL == (QH * R + QL) * (BH * R + BL) + RH * R + RL

Multiplying out we get:

AH * R + AL = QH * BH * R*R + (QH * BL + QL * BH + RH) * R + (QL * BL + RL)

Since Each value here AH,AL,QH,QL,BH,BL,RH,RL are all such that they are 0 <= val < R it follows that A < R*R and so QH * BH == 0. Thus one of them must be 0.

Thus we have two situations:

BH == 0 or BH != 0

IF BH == 0, B == BL and the division is simply done like this:

Divide a 64 bit unsigned integer with a 32 bit unsigned integer.

Most computers already provide an instruction that does that, if you don't have access to such an instruction you need to resort to multiple precision techniques or splitting the 64 bit value into four 16 bit values. However, this is kinda ugly so unless you state you need that I won't provide it.

If BH != 0 then QH must be 0 and so we get:

AH * R + AL = QL * (BH * R + BL) + RH * R + RL
            = (QL * BH  + RH) * R + (QL * BL + RL)

Here it is clear that AH = QL * BH + RH + (QL * BL + RL)/R.

If you do a AH,AL / BH. I.e. a 64 bit unsigned integer divided by a 32 bit unsigned integer you get a quotient q and remainder r. The quotient q is close to QL but might be off by some amount. If q >= R set q = R - 1. Under no circumstance should q be greater or equal to R.

You find out how much it is off by doing:

q * B == q * (BH * R + BL) == (q * BH) * R + (BL * q)
      == (q * BH + (BL*q)/R) * R + (BL * q) % R

doing a long multiplication of q and subtract it from A you get:

A - q * B = pH * R * pL

if q * B is greater than A then q is too large and you should make it smaller and compute the q * B again and subtract again. Repeat this process until q * B is less or equal to A, then you have QL == q and:

q * B is a 32 bit unsigned number q multiplied by a 64 bit unsigned number B (BH * R + BL).

A - QL * B == RH * R + RL

QL is the result of the division.

Since you need to do 32 bit by 64 bit multiplication to do the division you probably need that algorithm as well:

A * (BH * R + BL) == A * BH * R + A * BL
            == (A * BH + (A * BL)/R) * R + (A * BL) % R

so, multiply A * BL, this usually give a 64 bit result if you use machine instructions. The lower 32 bits of this is the lower 32 bits of the result. The upper bits are kept and added to A * BH. This give a 64 bit result so the result value can actually be 96 bits but if you want to keep only the lower 64 bits you just test the upper 32 bits of this high multiplication. If that result is non-zero you flag overflow and if it is zero you drop it and keep only the lower 32 bits of that high multiplication as the high 32 bit of the result (after adding the upper 32 bits of the lower multiplication).

In other words:

Compute A * BL into 64 bits (32 * 32 into 64 result)
the lower 32 bits is the lower 32 bits of result.
The upper 32 bits is kept - we call it x.
Compute A * BH into 64 bits and then add x and store the upper 32 bits in z and the lower 32 bits in y.
If the upper 32 bits (z) is non-zero flag overflow (throw exception or whatever), if z is zero save y into the 32 upper bits of result.

Multiplying two 64 bit values into a 128 bit value is similar:

(AH * R + AL)* (BH * R + BL) ==
   AH * BH * R * R + (AH * BL + AL * BH) * R + AL * BL

I.e. first multiply AL * BL into 64 bits, the low 32 bits are the low 32 bits of result, keep the upper 32 bits into x.

Then multiply AH * BL + AL * BH + x. The low 32 bits are bits 32..63 of result and the upper 32 bits are stored into x.

Then multiply AH * BH + x. The 64 bits are bits 64.127 of the result.

As you can see, the multiplication is several times easier than division.


Featured Post

Free Tool: SSL Checker

Scans your site and returns information about your SSL implementation and certificate. Helpful for debugging and validating your SSL configuration.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Templates For Beginners Or How To Encourage The Compiler To Work For You Introduction This tutorial is targeted at the reader who is, perhaps, familiar with the basics of C++ but would prefer a little slower introduction to the more ad…
This article shows you how to optimize memory allocations in C++ using placement new. Applicable especially to usecases dealing with creation of large number of objects. A brief on problem: Lets take example problem for simplicity: - I have a G…
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.
Suggested Courses
Course of the Month12 days, 13 hours left to enroll

777 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question