Стандартная задача с одной из тренировок ВолгоградскогоГосударственногоУниверситета: деление длинного на короткое и вывод 2-х результатов: целочисленный результат и остаток.
стандартное решение на Java:
BigInteger a = in.nextBigInteger();
BigInteger b = in.nextBigInteger();
BigInteger r[] = a.divideAndRemainder(b);
out.print(r[0]);
out.print(r[1]);
программа не проходит и как оказалось работает 2.032 с.
Запрограммированная ручками по алгоритму ДА на С++ работает 0.009 с.
В ходе тех же экспериментов над встроенной ДА в Питоне получилось 2.074 с.
и дает всего в 10 раз худшее время чем С++ LISP.
В чем проблема? неужели встроенная ДА НАСТОЛЬКО тормазная??? У кого какие версии?
З.Ы. Знала бы как приложить файл, приложила бы input.
Я как-то раз даже писал свою функцию перевода длинного в строку.
Вот - выдрал из старого кода:
public static String ToString(BigInteger x) {
BigInteger pows[] = new BigInteger[32];
pows[0] = BigInteger.valueOf(10);
int i = 0;
for (; x.compareTo(pows[i]) >= 0; ++i)
pows[i + 1] = pows[i].multiply(pows[i]);
return ToString(x, pows, i - 1, false);
}
private static String ToString(BigInteger x, BigInteger[] pows, int k,
boolean needZeros) {
if (k <= 0) {
if (needZeros || x.compareTo(BigInteger.ZERO) != 0)
return x.toString();
else
return "";
}
int cmp = x.compareTo(BigInteger.ZERO);
if (!needZeros && cmp == 0)
return "";
BigInteger[] parts = x.divideAndRemainder(pows[k]);
StringBuffer buf = new StringBuffer(ToString(parts[0], pows, k - 1,
needZeros));
String tmp = ToString(parts[1], pows, k - 1, needZeros
|| parts[0].compareTo(BigInteger.ZERO) > 0);
if (needZeros || parts[0].compareTo(BigInteger.ZERO) > 0) {
StringBuffer[] t = new StringBuffer[32];
t[0] = new StringBuffer("0");
int needLen = (1 << k) - tmp.length();
if (needLen > 0) {
int j = 0;
for (int i = needLen; i > 0; i >>= 1) {
t[j + 1] = new StringBuffer();
t[j + 1].append(t[j].toString());
t[j + 1].append(t[j].toString());
++j;
}
j = 0;
while (needLen > 0) {
if ((needLen & 1) > 0)
buf.append(t[j]);
++j;
needLen >>= 1;
}
}
}
buf.append(tmp);
return buf.toString();
}
Попробуйте применить. На действительно длинных числах заметно ускоряет.
Вот лог работы на моем не слишком шустром ноуте:
Done reading input and computing in:
2.567
Done quick output in:
2.305
Done default output in:
5.639
Т.е. дефолтный вывод занимает времени больше чем чтение, подсчет, и мой вывод вместе взятые. Поэтому я утверждаю, что в данном случае как раз вывод числа - самое тонкое место.
И проблема не в том сколько бит используется для хранения, проблема в ассимптотике алгоритма перевода из 2-ичной системы в 10-чную. Тот метод, что привел я ассимптотически лучше.
В Java достаточно неплохая реализация деления длинного на длинное A / B выполнится за время O(Len(A) * Len(B))
Len(B) == 1 в нашем случае т.к. оно короткое
а вот перевод из десятичной систему в двоичную
и обратно займёт O(Len(A) ^ 2) .
Поэтому в данному случае преобразование систем счисления основная причина медленной работы.
Кстати, аналогичную задачу из книги Ф.В. Меньшикова я сумел сдать именно реализовав длиную арифметику. И возможно это было первый и последний раз, когда я её писал руками.
Там писанины на три строчки, а ты говоришь "сумел сдать". Ну молодец, че тут скажешь. Растешь над собой :)
А вообще, выучи С++ и волей-неволей придется вспоминать как ты однажды "сумел сдать" ))
Можно посмотреть на скорость вывода циферок в следующем примере:
print 0
s = '1' + '0' * 100000
print 1
n = int (s)
print 2
m = n / 3
print 3
t = '%d' % m
print 4