Явный эквивалент невыполненного длинного длинного не BigInteger?

Question

У меня есть простой код C, который использует беззнаковое долго долго:

#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")); 
} 

Я должен преобразовать это код Java, поэтому я использую BigInteger следующим образом:

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; 
    } 

Мои проблема в том, что я не получаю такой же результат для Java и C Code. Для кода C, я получаю 10076018645131828514. while для Java-кода я получаю 1007025573367229468539210487799074.

Я не могу понять эти разные выходы для того же входа.

PS: Я бег кода на Ubuntu 32-битной машину и с помощью GCC компилятора

Answer 1

unsigned long long является ограниченной длиной целочисленного форматом (вероятно, 64bit or more). Это означает, что он не может содержать значение больше 2 -1.

A BigInteger - это целочисленный формат произвольной длины. Это означает, что размер числа, хранящегося в BigInteger, фактически ограничен только доступной памятью (и некоторыми ограничениями JVM, такими как размер массива, но они довольно большие).

Где-то в ваших расчетах в программе C unsigned long long, вероятно, переполняется, и вы получаете результат отсечки.

Это не происходит с BigInteger (он никогда не переполняется), он просто даст точный результат.

Вы можете эмулировать переполнение, создав BigInteger, который содержит требуемую битовую маску (64 бита набора) и используя myValue.and(MASK), чтобы получить результат «overflown».

Вам нужно будет делать это на каждом шагу, где может произойти переполнение. И это, конечно, будет медленнее, чем код C.

Answer 2

long long s зависят от платформы. Вы не можете рассчитывать на то, что они переносятся или будут иметь одинаковый размер на других машинах.

Попробуйте сделать sizeof(unsigned long long), чтобы увидеть, насколько он на самом деле на самом деле. Хотя я предполагаю, что вы переполняете.

Answer 3

Результат Java корректен, если вы выполняете фактическое умножение.

Я использовал Python, чтобы найти ниже:

>>> 2862933555777941757 * 351746051295833 + 3037000493 
1007025573367229468539210487799074L 

Тогда, чтобы получить то, что вы получаете в коде C:

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

Вы неподписанный долго долго обертку вокруг. :)

Answer 4

Вам понадобится тип, который может обрабатывать не менее 110 бит, чтобы правильно рассчитать ответ. Я подозреваю, что на вашей платформе C unsigned long long, вероятно, всего 64 бита, чего недостаточно. Он переполнен.

Ответ на вашу Java-программу верен.

Answer 5

Это широко используемый линейный конгруэнтный генератор:

(2862933555777941757 * N + 3037000493)% 2^64

Модуля часть обеспечивается при нулевой стоимости по размеру слова, в данном случае 64 бита , и поэтому не был включен в код C. Любая версия этого кода с использованием арифметики с несколькими точками неверна, она должна быть 64-битной. Хорошим типом данных для состояния будет uint64_t.