Встала задача работы с большими неотрицательными целыми числами, намного больше чем любая из стандартных структур может в себе содержать.
Для этого в качестве основы была выбрана 256-ричная система исчесления, т.к. в ней числа можно хранить как массив байт
где B - это основание системы (для двоичной B=2, для десятичной B=10, для шестнадцатеричной B=16 и т.д). В нашем случае B=256 (B=2^8). byte (или uint8) принимет значения от 0 до 255.
Мне нужна функция, которая будет возвращать результат операции
Вот некоторые мои наработки, которые могут натолкнуть кого-то на идею. Эти функции возвращают неправильный результат, как их исправить?
(Для простоты можно считать, что размеры входных массивов одинаковы)
Алгоритм быстрого взятия (mod c) от произведения a*b
Готовые библиотеки не предлагать - в моем случае их нельзя использовать!
Вот некоторые примеры чисел:
Дополнительные источники: https://ru.wikipedia.org/wiki/Система_счисления
Для этого в качестве основы была выбрана 256-ричная система исчесления, т.к. в ней числа можно хранить как массив байт
byte[] number {...}. Наименьший разряд - слева, найбольший - справа. То есть числа будут выглядеть так:
Код:
x = sum from i to N-1 {number[i]*B^i}
N = number.LengthМне нужна функция, которая будет возвращать результат операции
a mod b деления с остатком, или хотя бы просто деление a div b ([a / b]). Или же алгоритм быстрого нахожднеия a*b mod c. Подойдет любое из этих трех (желательно 1-е или 3-е).Вот некоторые мои наработки, которые могут натолкнуть кого-то на идею. Эти функции возвращают неправильный результат, как их исправить?
(Для простоты можно считать, что размеры входных массивов одинаковы)
Код:
public static byte[] _Modulus(byte[] dividend, byte[] divisor) {
int len = dividend.length;
byte[] remainder = new byte[len];
Memory.copy(remainder, dividend, len);
for (int i = 0; i < len; i++) {
int carry = 0;
for (int j = i; j < len; j++) {
int temp = (remainder[j] & 0xff) + (carry << 8);
if (divisor[i] != 0) {
carry = temp % (divisor[i] & 0xff);
} else {
carry = temp;
}
//remainder[j] = (byte)carry;
//stdout.printf(@"i: $(i) j: $(j)\t carry: $(carry)\n");
}
remainder[i] = (byte)(carry & 0xff);
}
return remainder;
}
public static byte[] Modulus(byte[] dividend, byte[] divisor) {
int len = dividend.length;
byte[] remainder = new byte[len];
Memory.copy(remainder, dividend, len);
for (int i = 0; i < len; i++) {
int carry = 0;
for (int j = i; j < len; j++) {
int temp = (remainder[j] & 0xff) + (carry << 8);
if (divisor[i] != 0) {
carry = temp / (divisor[i] & 0xff);
remainder[j] = (byte)(temp % (divisor[i] & 0xff));
} else {
carry = temp;
}
}
}
return remainder;
}Алгоритм быстрого взятия (mod c) от произведения a*b
Код:
/*
1.[Начальная установка]
s = 0;
2.[Преобразовать все D байтов]
for (D-1 >= j >= 0){
s = 256s;
if (s >= N) {s = s - N};
s = s + x_j*y;
if (s >= N) {s = s - N};
}
return s;
*/
public static byte[] _MulMod(byte[] x, byte[] y, byte[] N) {
int D = N.length;
byte[] s = new byte[D];
byte[] byte256 = new byte[D];
byte256[1] = 1;
for (int j = D - 1; j >= 0; j--) {
s = multiply(s, byte256);
if (compare(s, N) >= 0) {
s = substract(s, N);
}
byte[] x_j = new byte[D];
x_j[0] = x[j];
//byte[] x_j = (byte[]) x[j];
s = add(multiply(y, x_j), s);
if (compare(s, N) >= 0) {
s = substract(s, N);
}
s = s[0:D];
}
return s;
}
Код:
//https://en.wikipedia.org/wiki/Long_division#Division
//https://en.wikipedia.org/wiki/Division_algorithm#Long_division
public static byte[] Divide(byte[] dividend, byte[] divisor) {
int len = dividend.length;
byte[] quotient = new byte[len];
byte[] remainder = new byte[len];
Memory.copy(remainder, dividend, len);
for (int i = 0; i < len; i++) {
int carry = 0;
for (int j = i; j < len; j++) {
int temp = (remainder[j] & 0xff) + (carry << 8);
if (divisor[i] != 0) {
quotient[j] = (byte)(temp / (divisor[i] & 0xff));
carry = temp % (divisor[i] & 0xff);
} else {
quotient[j] = (byte)carry;
carry = temp;
}
remainder[j] = (byte)carry;
}
}
return quotient;
}Готовые библиотеки не предлагать - в моем случае их нельзя использовать!
Код:
public static byte[] mod_int(uint64 x, uint64 y){
uint64 modulus = x, divisor = y;
while (modulus >= y){
while (divisor > modulus){
divisor >>= 1;
}
modulus = modulus - divisor;
}
return (byte[]) modulus;
}Вот некоторые примеры чисел:
13120_10 = {64 51 0 0 0 0 0 0}_25631214211316_10 = {244 16 131 68 7 0 0 0}_256418302432341123382_10 = {54 225 95 144 216 27 206 5}_256Дополнительные источники: https://ru.wikipedia.org/wiki/Система_счисления
Последнее редактирование:
