Java equivalent of unsigned long long is not BigInteger?

Question

I have a simple C code which uses unsigned long long:

#include<stdlib.h>
unsigned long long get_random_id(const char *imeiId)
{
    const unsigned long long MULT = 2862933555777941757LL;
    const unsigned long long ADDEND = 3037000493LL;
    unsigned long long newId, oldId;
    oldId = atoll(imeiId);
    newId = MULT * oldId + ADDEND;
    return newId;
}
void main()
{
  printf("%llu",get_random_id("351746051295833"));
}

I'm supposed to convert this to a java code, so I'm using BigInteger as follows:

public static void main(String args[]) {
        System.out.println(get_random_id("351746051295833"));
    }
    static BigInteger get_random_id(String imeiId) {
        final String MULT_STRING = "2862933555777941757";
        final String ADDEND_STRING = "3037000493";

        BigInteger MULT =  new BigInteger(MULT_STRING);
        BigInteger ADDEND = new BigInteger(ADDEND_STRING);
        BigInteger oldId = new BigInteger(imeiId);
        BigInteger temp = MULT.multiply(oldId);
        BigInteger newId = temp.add(ADDEND);
        return newId;
    }

My problem here is that I'm not getting the same output for Java and C Code. For C code, I'm getting 10076018645131828514. while for Java code I'm getting 1007025573367229468539210487799074.

I'm not able to understand these different outputs for the same input.

PS: I'm running the code on Ubuntu 32 bit machine and using gcc compiler

Answer 1

unsigned long long is a limited-length integer format (probably 64bit or more). That means that it can hold no value larger than 2⁶⁴-1.

A BigInteger is an arbitrary-length integer format. That means that the size of the number stored in a BigInteger is effectively limited only by the available memory (and some JVM restrictions like the size of an array, but those are pretty big).

Somewhere in your calculation in the C program the unsigned long long probably overflows and you get a cut-off result.

That doesn't happen with BigInteger (it never silently overflows), it will just give the exact result.

You can emulate an overflow by creating a BigInteger that holds the desired bit mask (64 set bits) and using myValue.and(MASK) to get the "overflown" result.

You'd have to do that at every step where an overflow could occur, 'though. And it would certainly be slower than the C code.

Answer 2

Output of Java is correct, if you do the actual multiplication.

I used Python to find the below:

>>> 2862933555777941757 * 351746051295833 + 3037000493
1007025573367229468539210487799074L

Then to get what you are getting in your C code:

>>> 2862933555777941757 * 351746051295833 + 3037000493
1007025573367229468539210487799074L
>>> _ % (2**64)   # Previous result mod 2 ^ 64 (**Assumming ULL is 64 bits on your system**)
10076018645131828514L  # This is what you have as the output of your C code.

You have an unsigned long long wrap around. :)

Answer 3

You'll need a type that can handle at least 110 bits, to calculate the answer correctly. I suspect that on your platform, a C unsigned long long is probably only 64 bits, which is not enough. It's overflowing.

The answer from your Java program is correct.

Answer 4

This is a widely used linear congruential generator:

(2862933555777941757 * N + 3037000493) % 2^64

The modulus part is provided at zero cost by the word size, in this case 64 bits, and therefore has not been included in the C code. Any version of this code using multi-precision arithmetic is wrong, it must be 64-bits. A good data type for the state would be uint64_t.

Answer 5

long longs are platform dependent. You can't count on them being portable, or being the same size on other machines.

Try doing a sizeof(unsigned long long) to see how big it actually is on your machine. Although my guess is that you're getting overflow.