Java: вычисления огромных чисел с помощью примитивных типов
Задание: найти произведение квадратов от 1 до 200. Нельзя использовать BigInteger. Массивы, строки я так понимаю тоже. Ментор с тренинга сказала использовать только примитивные типы. Модуль самый первый и строки / массивы еще не проходили.
Каким вообще могут быть варианты подсчета? Вычислив через BigInteger там результат получился длиною в километр. Я максимум что смог сделать так это при достижении long(max value) / (200 * 200) делил это число само на себя(что бы избежать переполнения), выводил этот один из многих множителей в консоль через запятую в процессе вычисления. Была идея отслеживать изменения старшего бита, что бы знать сколько переполнений случилось и отталкиваться от этого, но числа настолько большие, что переполнение в круг идет. Думал разлаживать на 2^32, но ничего годного не получилось. Каким способом можно выполнить данное задание?
Ответы (3 шт):
Насколько точно вам нужно посчитать? Приблизительно, с относительной точностью порядка 1e-13 вам подойдёт?
Если да, то сначала нужно вычислить десятичный логарифм вашего произведения, а затем напечатать его значение, не используя возведение в степень. Возводить в степень не нужно, та как для n = 200 точности представления встроенного типа double не хватит.
Вот идея решения на Python:
# логарифм результата
logres=0.0
# логарифм произведения квадратов от 1 до 200
for n in range(1,201):
logres+=2*log10(n)
# logres == 749.7937772800806
# результат равен (10**0.7937772800806)*1e749
# десятичная экспонента
pwr = floor(logres) # 749
# мантисса
mnt = pow(10, logres-pwr) # (10**0.7937772800806)
print("{0}E{1}".format(mnt, pwr))
Результат равен 6.2198123175648155E749
C точным результатом совпадают первые 12 цифр 6.21981231756, относительная ошибка 1.64e-13
Решение на Java
/**
* Вычисление произведения квадратов без использования `BigInt`
*/
public class BigSquares {
/**
* Возвращает логарифм произведения квадратов чисел от 1 до <code>n</code>
* @param n количество квадратов в произведении
* @return логарифм произведения квадратов
*/
public static double logMulSquares(int n) {
double logres = 0.0;
for (int i = 1; i <= n; i++) {
logres += 2*Math.log10(i);
}
return logres;
}
/**
* Возвращает строковое представление <code>10**logres</code>
* @param logres Логарифм результата
* @return строковое представление числа <code>10**logres</code>
*/
public static String exp10(double logres) {
int pwr = (int) Math.floor(logres);
double mnt = Math.pow(10, logres-pwr);
return String.format("%.16gE%d", mnt, pwr);
}
public static void main(String[] args) {
System.out.println("Произведение квадратов от 1 до 200: " + exp10(logMulSquares(200)));
System.out.println("Произведение квадратов от 1 до 400: " + exp10(logMulSquares(400)));
System.out.println("Произведение квадратов от 1 до 1000: " + exp10(logMulSquares(1000)));
}
}
Результат вычислений:
Произведение квадратов от 1 до 200: 6.219812317564816E749
Произведение квадратов от 1 до 400: 4.100420116197644E1737
Произведение квадратов от 1 до 1000: 1.619155070705591E5135
Если достаточно приблизительного значения, то можно так: https://ideone.com/cckBDC
import java.util.*;
import java.lang.*;
import java.io.*;
class Ideone {
public static void main (String[] args) throws java.lang.Exception {
int n = 200;
long x = 1;
int p = 0;
for (int q = n; q != 0; --q) {
for (int w = 0; w < 2; ++w) {
for (; Long.MAX_VALUE / q < x; ++p) {
x = x / 10 + (x % 10 > 5 ? 1 : x % 10 < 5 ? 0 : (x / 10 & 1));
}
x *= q;
}
}
System.out.println("Somewhere near " + x + " * 10**" + p);
}
}
Получается:
6219812317563792060 * 10**731
А правильное значение:
621981231756379489999997501700030226361030042908402135795585416076780567701229627071194748755274771867550481130867332728398608915678217606208944334143532903157416015053231992085653846275159616127812272870349795208758168675609821292383968189620347359298821336964567268936282003057371855944848505049857604569455105033587666178052186125598590101814860460233644389300432456960009702905584857393518877079243717213370983146491503406155228997954249347719005783769360467152555665800216223615428450836858053400856713359967484823371026535062161096211713506798207812398746913836648755132232834523663952442186966337759051603462287553956523494664588575257708095078400000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
Т. е. мы верно определили 15 первых знаков (и ещё 4 выведены неверно). Впрочем, как достоверно (если не знать ответ) определить, какое количество знаков мы вычислили верно, я не знаю.
Хотя, оценить тоже можно: достаточно считать обе границы - минимальную и максимальную: https://ideone.com/GHJOzR
import java.util.*;
import java.lang.*;
import java.io.*;
class Ideone {
public static void main (String[] args) throws java.lang.Exception {
int n = 200;
long l = 1, x = 1, r = 1;
int pl = 0, px = 0, pr = 0;
for (int q = n; q != 0; --q) {
for (int w = 0; w < 2; ++w) {
for (; Long.MAX_VALUE / q < l; ++pl) {
l = l / 10;
}
for (; Long.MAX_VALUE / q < x; ++px) {
x = x / 10 + (x % 10 > 5 ? 1 : x % 10 < 5 ? 0 : (x / 10 & 1));
}
for (; Long.MAX_VALUE / q < r; ++pr) {
r = r / 10 + 1;
}
l *= q;
r *= q;
x *= q;
}
}
System.out.println("Min: " + l + " * 10**" + pl);
System.out.println("Opt: " + x + " * 10**" + px);
System.out.println("Max: " + r + " * 10**" + pr);
}
}
Получается
Min: 6219812317563751272 * 10**731
Opt: 6219812317563792060 * 10**731
Max: 6219812317563849792 * 10**731
Значит мы гарантированно уверены в первых 13 цифрах: 6219812317563.
Эта задача оказалось удивительно интересной и трудной. Разрешено передавать в процедуру, обрабатывать в процедуре и возвращать из процедуры фиксированный объём информации. Рекурсию я разрешил сам: без рекурсии задача не разрешима, так как без рекурсии ограничен общий объём памяти для работы. Для тех кто понимает: без рекурсии получится конечный автомат, которым задачу не решить для произвольного числа.
С рекурсией задача разрешима в принципе. Алгоритм работает за экспоненциальное время. Лучше я придумать не смог и, кажется, это не возможно. Но и это я не знаю как доказать.
Другими словами: можно ли вычислить квадрат факториала в чём-то похожем на автомат с магазином быстрее чем за экспоненту?
Теперь к практике. Программа ниже за 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;
}
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;
}
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;
}
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