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

The answer from your C program is far too short. How many bits is an unsigned long long on your platform? However many it is, it's not enough to hold the answer. — Dawood ibn Kareem, Nov 13 '13 at 09:18

score 3 · Accepted Answer · edited May 23 '17 at 11:44

3

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.

edited May 23 '17 at 11:44

Community

1
1

answered Nov 13 '13 at 09:19

Joachim Sauer

302,674
57
556
614

1

The multiplication `MULT * oldId` overflows. It's ~10^33. – Tobias Brandt Nov 13 '13 at 09:21
In what sense is `unsigned long long` decimal? Wouldn't it overflowing at `2**64-1` mean that it's binary? – svk Nov 13 '13 at 09:22
@svk: that was a typo (or think-o): I actually meant integer, I was mixing it up with `BigDecimal` which is "a cousin" of `BigInteger` but not relevant to this question. – Joachim Sauer Nov 13 '13 at 09:24

score 1 · Answer 2 · answered Nov 13 '13 at 09:22

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. :)

score 1 · Answer 3 · answered Nov 13 '13 at 09:22

1

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.

answered Nov 13 '13 at 09:22

Dawood ibn Kareem

77,785
15
98
110

Yeah, now I get it. On my machine, unsigned long long is 64 bits – Saurabh Verma Nov 13 '13 at 09:23

score 1 · Answer 4 · answered Dec 29 '15 at 23:29

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.

score 0 · Answer 5 · answered Nov 13 '13 at 09:20

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.

Java equivalent of unsigned long long is not BigInteger?

5 Answers5