c++algorithmbignum

Dividing a 2x32 bit big integer by 1000


I have big number, time (micro seconds) stored in two 32bit variables. I need a help, how to change micro seconds time into millisecond, so I can store result of difference in 32bit number.

More details: I have one time in two 32bit variables. Where one variable have more significant bits and other have less significant bits. This time have microseconds resolution so I want to change it to milliseconds. So how to divide number that is stored in two variables.


Solution

  • If you don't have a 64-bit type, you can do it like the following:

    uint32_t higher, lower; // your input
    
    lower /= 1000;
    lower += (higher % 1000) * 4294967L; // approximate 2^32 / 1000
    higher /= 1000;
    

    If the result fitted in lower itself, higher should be 0.

    Just note that as @Mikhail pointed out, this solution is approximate, and has an error of 0.296 * higher + 2 ms (unless I'm missing something).


    If you really want a better precision and don't care about efficiency, you can use a bit of floating-point arithmetic in the middle, and round the results correctly. I doubt if it's worth the effort:

    uint32_t higher, lower; // your input
    
    // simpler without a helper variable
    if (lower % 1000 >= 500)
    {
        lower /= 1000;
        ++lower;
    }
    else
        lower /= 1000;
    
    lower += round((higher % 1000) * 4294967.296); // 2^32 / 1000
    higher /= 1000;
    

    You'll need to include <cmath> for round().

    As a note, @Mikhail's solution in this case is probably better and may be faster. Though it's too complex for me.


    If you have a 64-bit type, you can convert the split value to it:

    uint64_t whole_number = higher;
    whole_number <<= 32;
    whole_number |= lower;
    

    And then you can use whole_number as usual.


    Note that if you only need a difference, it will be faster to subtract the values before actually dividing.

    Assuming that you know which value is bigger:

    uint32_t higher1, lower1; // smaller value
    uint32_t higher2, lower2; // bigger value
    
    uint32_t del_high = higher2 - higher1;
    uint32_t del_low = lower2 - lower1;
    
    if (lower2 < lower1)
        --del_high;
    

    And now you can convert the result like explained before. Or with a bit luck, del_high will be 0 (if the difference is smaller than 2^32 μs), and you will have the result in del_low (in μs).