Java: вычисления огромных чисел с помощью примитивных типов
1,00
р.
Задание: найти произведение квадратов от 1 до 200. Нельзя использовать BigInteger. Массивы, строки я так понимаю тоже. Ментор с тренинга сказала использовать только примитивные типы. Модуль самый первый и строки / массивы еще не проходили.
Каким вообще могут быть варианты подсчета? Вычислив через BigInteger там результат получился длиною в километр. Я максимум что смог сделать так это при достижении long(max value) / (200 * 200) делил это число само на себя(что бы избежать переполнения), выводил этот один из многих множителей в консоль через запятую в процессе вычисления. Была идея отслеживать изменения старшего бита, что бы знать сколько переполнений случилось и отталкиваться от этого, но числа настолько большие, что переполнение в круг идет. Думал разлаживать на 2^32, но ничего годного не получилось. Каким способом можно выполнить данное задание?
Ответ
Эта задача оказалось удивительно интересной и трудной. Разрешено передавать в процедуру, обрабатывать в процедуре и возвращать из процедуры фиксированный объём информации. Рекурсию я разрешил сам: без рекурсии задача не разрешима, так как без рекурсии ограничен общий объём памяти для работы. Для тех кто понимает: без рекурсии получится конечный автомат, которым задачу не решить для произвольного числа.
С рекурсией задача разрешима в принципе. Алгоритм работает за экспоненциальное время. Лучше я придумать не смог и, кажется, это не возможно. Но и это я не знаю как доказать.
Другими словами: можно ли вычислить квадрат факториала в чём-то похожем на автомат с магазином быстрее чем за экспоненту?
Теперь к практике. Программа ниже за 20 минут точно вычисляет квадраты факториалов от нуля до двухсот. Только примитивные типы. В самой нагруженной функции четырнадцать параметров. Алгоритм экспоненциальный, все усилия были направлены на уменьшение константы.
public class Product { public static void main(String... args) { int n = 1 for (int m = 0 m < 201 ++m) { System.out.print(m) System.out.print("!^2 = ") long d = product(m, n, true) d %= BASE if (d != 0) { ++n } for (int l = 1 l < m + 1 ++l) { for (int k = l k % 5 == 0 k /= 5) { System.out.print("00") } } System.out.println() } }
private static final int BASE_SIZE = 18 private static final long BASE = pow10(BASE_SIZE) private static final long HALF_BASE = pow10(BASE_SIZE / 2)
private static long product(int m, int n, boolean print) { if (!print && m <= 1) { return (n == 0) ? 1 : 0 }<br> int m5 = mi(m) int m4 = mi(m5) int m3 = mi(m4) int m2 = mi(m3) int m1 = mi(m2)
return digits(pi(m2), pi(m3), pi(m4), pi(m5), pi(m), m1, n, 0, 0, 0, 0, 0, 0, print) }
private static long pi(int m) { long p = 1 int m1 for (m1 = m m1 > 1 --m1) { long l = removeTens(m1) if (BASE / (l * l) <= p) { break } p = removeTens(p * l * l) } return p }<br> private static int mi(int m) { long p = 1 int m1 for (m1 = m m1 > 1 --m1) { long l = removeTens(m1) if (BASE / (l * l) <= p) { break } p = removeTens(p * l * l) } return m1 }<br> private static long low(long p, long d, long c) { long pl = p % HALF_BASE long ph = p / HALF_BASE long dl = d % HALF_BASE long dh = d / HALF_BASE long i = pl * dh + ph * dl return (pl * dl + i % HALF_BASE * HALF_BASE + c) % BASE }
private static long high(long p, long d, long c) { long pl = p % HALF_BASE long ph = p / HALF_BASE long dl = d % HALF_BASE long dh = d / HALF_BASE long i = pl * dh + ph * dl long l = pl * dl + i % HALF_BASE * HALF_BASE return ph * dh + i / HALF_BASE + (l + c) / BASE }
private static long digits(long p1, long p2, long p3, long p4, long p5, int m, int n, int j, long c1, long c2, long c3, long c4, long c5, boolean print) { long d = product(m, j, false) long l1 = low(p1, d, c1) long h1 = high(p1, d, c1)
long l2 = low(p2, l1, c2) long h2 = high(p2, l1, c2)
long l3 = low(p3, l2, c3) long h3 = high(p3, l2, c3)
long l4 = low(p4, l3, c4) long h4 = high(p4, l3, c4)
long l5 = low(p5, l4, c5) long h5 = high(p5, l4, c5)
long dd = l5 if (j < n) { dd = digits(p1, p2, p3, p4, p5, m, n, j + 1, h1, h2, h3, h4, h5, print) } if (print) { boolean skipZeros = dd / BASE == 0 dd %= BASE return ((print(l5, skipZeros)) ? 0 : BASE) + dd } return dd }
private static long removeTens(long n) { while (n % 10 == 0) { n /= 10 } return n }
private static boolean print(long n, boolean skipZeros) { for (int i = BASE_SIZE - 1 i >= 0 --i) { long d = n % pow10(i + 1) / pow10(i) if (d != 0 || !skipZeros) { System.out.print(d) } if (d != 0) { skipZeros = false } } return skipZeros }
private static long pow10(int n) { long p = 1 for (int i = 0 i < n ++i) { p *= 10 } return p } }
$ javac Product.java && java Product 0!^2 = 1 1!^2 = 1 2!^2 = 4 3!^2 = 36 4!^2 = 576 5!^2 = 14400 6!^2 = 518400 7!^2 = 25401600 8!^2 = 1625702400 9!^2 = 131681894400 10!^2 = 13168189440000 ... 200!^2 = 621981231756379489999997501700030226361030042908402135795585416076780567701229627071194748755274771867550481130867332728398608915678217606208944334143532903157416015053231992085653846275159616127812272870349795208758168675609821292383968189620347359298821336964567268936282003057371855944848505049857604569455105033587666178052186125598590101814860460233644389300432456960009702905584857393518877079243717213370983146491503406155228997954249347719005783769360467152555665800216223615428450836858053400856713359967484823371026535062161096211713506798207812398746913836648755132232834523663952442186966337759051603462287553956523494664588575257708095078400000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
Каким вообще могут быть варианты подсчета? Вычислив через BigInteger там результат получился длиною в километр. Я максимум что смог сделать так это при достижении long(max value) / (200 * 200) делил это число само на себя(что бы избежать переполнения), выводил этот один из многих множителей в консоль через запятую в процессе вычисления. Была идея отслеживать изменения старшего бита, что бы знать сколько переполнений случилось и отталкиваться от этого, но числа настолько большие, что переполнение в круг идет. Думал разлаживать на 2^32, но ничего годного не получилось. Каким способом можно выполнить данное задание?
Ответ
Эта задача оказалось удивительно интересной и трудной. Разрешено передавать в процедуру, обрабатывать в процедуре и возвращать из процедуры фиксированный объём информации. Рекурсию я разрешил сам: без рекурсии задача не разрешима, так как без рекурсии ограничен общий объём памяти для работы. Для тех кто понимает: без рекурсии получится конечный автомат, которым задачу не решить для произвольного числа.
С рекурсией задача разрешима в принципе. Алгоритм работает за экспоненциальное время. Лучше я придумать не смог и, кажется, это не возможно. Но и это я не знаю как доказать.
Другими словами: можно ли вычислить квадрат факториала в чём-то похожем на автомат с магазином быстрее чем за экспоненту?
Теперь к практике. Программа ниже за 20 минут точно вычисляет квадраты факториалов от нуля до двухсот. Только примитивные типы. В самой нагруженной функции четырнадцать параметров. Алгоритм экспоненциальный, все усилия были направлены на уменьшение константы.
public class Product { public static void main(String... args) { int n = 1 for (int m = 0 m < 201 ++m) { System.out.print(m) System.out.print("!^2 = ") long d = product(m, n, true) d %= BASE if (d != 0) { ++n } for (int l = 1 l < m + 1 ++l) { for (int k = l k % 5 == 0 k /= 5) { System.out.print("00") } } System.out.println() } }
private static final int BASE_SIZE = 18 private static final long BASE = pow10(BASE_SIZE) private static final long HALF_BASE = pow10(BASE_SIZE / 2)
private static long product(int m, int n, boolean print) { if (!print && m <= 1) { return (n == 0) ? 1 : 0 }<br> int m5 = mi(m) int m4 = mi(m5) int m3 = mi(m4) int m2 = mi(m3) int m1 = mi(m2)
return digits(pi(m2), pi(m3), pi(m4), pi(m5), pi(m), m1, n, 0, 0, 0, 0, 0, 0, print) }
private static long pi(int m) { long p = 1 int m1 for (m1 = m m1 > 1 --m1) { long l = removeTens(m1) if (BASE / (l * l) <= p) { break } p = removeTens(p * l * l) } return p }<br> private static int mi(int m) { long p = 1 int m1 for (m1 = m m1 > 1 --m1) { long l = removeTens(m1) if (BASE / (l * l) <= p) { break } p = removeTens(p * l * l) } return m1 }<br> private static long low(long p, long d, long c) { long pl = p % HALF_BASE long ph = p / HALF_BASE long dl = d % HALF_BASE long dh = d / HALF_BASE long i = pl * dh + ph * dl return (pl * dl + i % HALF_BASE * HALF_BASE + c) % BASE }
private static long high(long p, long d, long c) { long pl = p % HALF_BASE long ph = p / HALF_BASE long dl = d % HALF_BASE long dh = d / HALF_BASE long i = pl * dh + ph * dl long l = pl * dl + i % HALF_BASE * HALF_BASE return ph * dh + i / HALF_BASE + (l + c) / BASE }
private static long digits(long p1, long p2, long p3, long p4, long p5, int m, int n, int j, long c1, long c2, long c3, long c4, long c5, boolean print) { long d = product(m, j, false) long l1 = low(p1, d, c1) long h1 = high(p1, d, c1)
long l2 = low(p2, l1, c2) long h2 = high(p2, l1, c2)
long l3 = low(p3, l2, c3) long h3 = high(p3, l2, c3)
long l4 = low(p4, l3, c4) long h4 = high(p4, l3, c4)
long l5 = low(p5, l4, c5) long h5 = high(p5, l4, c5)
long dd = l5 if (j < n) { dd = digits(p1, p2, p3, p4, p5, m, n, j + 1, h1, h2, h3, h4, h5, print) } if (print) { boolean skipZeros = dd / BASE == 0 dd %= BASE return ((print(l5, skipZeros)) ? 0 : BASE) + dd } return dd }
private static long removeTens(long n) { while (n % 10 == 0) { n /= 10 } return n }
private static boolean print(long n, boolean skipZeros) { for (int i = BASE_SIZE - 1 i >= 0 --i) { long d = n % pow10(i + 1) / pow10(i) if (d != 0 || !skipZeros) { System.out.print(d) } if (d != 0) { skipZeros = false } } return skipZeros }
private static long pow10(int n) { long p = 1 for (int i = 0 i < n ++i) { p *= 10 } return p } }
$ javac Product.java && java Product 0!^2 = 1 1!^2 = 1 2!^2 = 4 3!^2 = 36 4!^2 = 576 5!^2 = 14400 6!^2 = 518400 7!^2 = 25401600 8!^2 = 1625702400 9!^2 = 131681894400 10!^2 = 13168189440000 ... 200!^2 = 621981231756379489999997501700030226361030042908402135795585416076780567701229627071194748755274771867550481130867332728398608915678217606208944334143532903157416015053231992085653846275159616127812272870349795208758168675609821292383968189620347359298821336964567268936282003057371855944848505049857604569455105033587666178052186125598590101814860460233644389300432456960009702905584857393518877079243717213370983146491503406155228997954249347719005783769360467152555665800216223615428450836858053400856713359967484823371026535062161096211713506798207812398746913836648755132232834523663952442186966337759051603462287553956523494664588575257708095078400000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
