float stepA = 0;
for (int i = 0; i < 100 000; i++){
stepA += ln(A);
}
Можно ли обойтись без длинной арифметики ?
Столкнулся с задачей.
Есть два масива А и Б, в каждом по 100 000 елементов (цифри от 1 до 10).
Для каждого масива нужно перемножыть все его елементы и сказать какое произведение больше или они ровны.
Я делал через длинную арифметику но мое решение не подходило по времени выполения, товарищи делали примерно так
а потом сравнивали stepA, stepB.
Вот мне интересно можно ли придумать такие входние данние, где точности при таком решении не хватит.
Математики, просветите пожалуйста.
Есть два масива А и Б, в каждом по 100 000 елементов (цифри от 1 до 10).
Для каждого масива нужно перемножыть все его елементы и сказать какое произведение больше или они ровны.
Я делал через длинную арифметику но мое решение не подходило по времени выполения, товарищи делали примерно так
Код:
а потом сравнивали stepA, stepB.
Вот мне интересно можно ли придумать такие входние данние, где точности при таком решении не хватит.
Математики, просветите пожалуйста.
Попробовать может порыть в таком направлении.
Для каждого из этих чисел получить данные 1^a1 * 2^a2 * ... * a9.
Потом "сократить" эти массивы, и дальше как нибудь анализировать полученные данные.
Для каждого из этих чисел получить данные 1^a1 * 2^a2 * ... * a9.
Потом "сократить" эти массивы, и дальше как нибудь анализировать полученные данные.
Цитата: Zorkus
Попробовать может порыть в таком направлении.
Для каждого из этих чисел получить данные 1^a1 * 2^a2 * ... * a9.
Потом "сократить" эти массивы, и дальше как нибудь анализировать полученные данные.
Для каждого из этих чисел получить данные 1^a1 * 2^a2 * ... * a9.
Потом "сократить" эти массивы, и дальше как нибудь анализировать полученные данные.
По поводу сокращения - не поможет. Если в одном масиве сплошные 7, а в другом 5 - не сократится. Конечно можно понять что 7 > 5. Ну а если в первом только 7 и 3, а в другом 5 - и не сократится и фиг его знает где меньше.
Меня больше интересует вариант с логарифмами. Слону понятно что exp(stepA) нам не даст точного произведения, но можно ли подобрать два таких масива для которых произведения будут немного отличатся, а для значения их логарифмов (то что я не совсем удачно назвал stepA) не хватит точности, чтоб ето проверить. Или же разница для двох самых близких произведений из 100 000 елементов будет настолько большая, что решение с логарифмами всегда даст правильный ответ ?
Все элементарно, Ватсон. Организуем 2 массива на 10 элементов. В первый - записываем количество соответствующих цифр из первого массива. Во второй - из второго. Далее сокращаем.. для начала соответствующие элементы в соответствующих ячейках - дальше скоращаем путем НОК(наименьшее общее кратное). оставшиеся числа в 64-разрядное целое уж точно влезут, если оценить получше - то может и в 32-разрядное.
Цитата: Dart Bobr
Все элементарно, Ватсон. Организуем 2 массива на 10 элементов. В первый - записываем количество соответствующих цифр из первого массива. Во второй - из второго. Далее сокращаем.. для начала соответствующие элементы в соответствующих ячейках - дальше скоращаем путем НОК(наименьшее общее кратное). оставшиеся числа в 64-разрядное целое уж точно влезут, если оценить получше - то может и в 32-разрядное.
Я поспешил с самокритикой (коорую уже удалил).
Не скоротится. 100 перемножених 7-ок не скоротятся с 100 премножеными 5-ками.
Цитата: Rebbit
Код:
float stepA = 0;
for (int i = 0; i < 100 000; i++){
stepA += ln(A);
}
for (int i = 0; i < 100 000; i++){
stepA += ln(A);
}
А может сделать по-другому?
Код:
float result = 1;
for (int i = 0; i < 100 000; i++){
result *= A/B;
}
for (int i = 0; i < 100 000; i++){
result *= A/B;
}
Ну а потом сравниваем result с 1.
Цитата: shine
А может сделать по-другому?
Ну а потом сравниваем result с 1.
Код:
float result = 1;
for (int i = 0; i < 100 000; i++){
result *= A/B;
}
for (int i = 0; i < 100 000; i++){
result *= A/B;
}
Ну а потом сравниваем result с 1.
(1/10)^{всяко меньше 50 000} будет нулю равняться, так что ничего хорошенго не получится тоже. Сначала нужно какую-нибудь сортировку хитрую применять, что тоже времени дохера сожрет.
Цитата: Kulti
(1/10)^{всяко меньше 50 000} будет нулю равняться, так что ничего хорошенго не получится тоже. Сначала нужно какую-нибудь сортировку хитрую применять, что тоже времени дохера сожрет.
Тогда делаем то же самое только result будет массивом. Когда текущее значение элемента массива приближается к максимальному или минимальному значению начинаем писать в следующий элемент массива. После пробега по всем данным анализируем данные в массиве результатов: перемножаем максимумы и минимумы и т. д.
Хм.... Если посортить а потом брать с разных концов и так пока оба конца не будут больше или меньше 1.... Прикольно.
А если просто вместо 32-разрядного float использовать 80-разрядный long double? Точность и макс. хранимое число выше, а время выполнения то же.
Как вариант с составлениями массивов типа число--сколько раз повторяется. Если возводить эти числа в степени (=число повторений) сопроцессором (задать принудительно тип long double), получится быстрее.
Как вариант с составлениями массивов типа число--сколько раз повторяется. Если возводить эти числа в степени (=число повторений) сопроцессором (задать принудительно тип long double), получится быстрее.
Поскольку сами произведения вам не нужны, можно хранить только старшие разряды, сколько позволяет точность.
Для 1 массива заведем 2 переменные ( man - длинное вещественное, por - длинное целое ).
Далее пример:
M1 = 22*33 *44*55
man = 0.100000 por = 1 (умножаем на 22 и нормализуем)
man = 0.220000 por = 2 (умножаем на 33 и нормализуем)
man = 0.726000 por = 3 (умножаем на 44 и нормализуем)
man = 0.319440 por = 5 (умножаем на 55 и нормализуем)
man = 0.175692 por = 7 (запоминаем ответ)
M2 = 66*77*88
man = 0.100000 por = 1 (умножаем на 66 и нормализуем)
man = 0.660000 por = 2 (умножаем на 77 и нормализуем)
man = 0.508200 por = 4 (умножаем на 88 и нормализуем)
man = 0.447216 por = 6 (запоминаем ответ)
В этом примере первое произведение больше даже по порядку (por = 7).
Равентство нужно проверять отдельно (как правильно сказали выше, все элементы должны сократиться).
Для 1 массива заведем 2 переменные ( man - длинное вещественное, por - длинное целое ).
Далее пример:
M1 = 22*33 *44*55
man = 0.100000 por = 1 (умножаем на 22 и нормализуем)
man = 0.220000 por = 2 (умножаем на 33 и нормализуем)
man = 0.726000 por = 3 (умножаем на 44 и нормализуем)
man = 0.319440 por = 5 (умножаем на 55 и нормализуем)
man = 0.175692 por = 7 (запоминаем ответ)
M2 = 66*77*88
man = 0.100000 por = 1 (умножаем на 66 и нормализуем)
man = 0.660000 por = 2 (умножаем на 77 и нормализуем)
man = 0.508200 por = 4 (умножаем на 88 и нормализуем)
man = 0.447216 por = 6 (запоминаем ответ)
В этом примере первое произведение больше даже по порядку (por = 7).
Равентство нужно проверять отдельно (как правильно сказали выше, все элементы должны сократиться).
Ета идея мне тоже приходила в голову. По сути ето чемто похоже на решение с логарифмами. В por будет целая часть от логарифма с основой 10 + старшие розряди произведения.
Спасибо всем за интересные решения.
Но вопрос хватит ли точности остается открытым.
Можно ли подобрать такие масивы при которых не хватит точности для логарифмов или для решения от Alex_soldier ? Мой знакомый утверждает что решение с логарифмами точно не даст ошибки при любом входе, но почему ето так он не обяснил. Ну он математик, ему виднее, но сам я не могу понять почему нельзя подобрать два произведения которые будут отличатся совсем немного друг от друга.
Спасибо всем за интересные решения.
Но вопрос хватит ли точности остается открытым.
Можно ли подобрать такие масивы при которых не хватит точности для логарифмов или для решения от Alex_soldier ? Мой знакомый утверждает что решение с логарифмами точно не даст ошибки при любом входе, но почему ето так он не обяснил. Ну он математик, ему виднее, но сам я не могу понять почему нельзя подобрать два произведения которые будут отличатся совсем немного друг от друга.
При последовательном перемножении погрешность остается на уровне младшего разряда числа.
Я не о том.
Смотри. Чему ровно ln(10^100000). Я не знаю. А в том варианте который я в начале привел с логарифмами мои знакомые сравнивают именно такие результаты.
В твоем случае интересует man. Хватит ли у него етих старшых розрядов чтоб отличить два произведения которые близки между собой даже припуская, что при умножении не будет погрешности.
Смотри. Чему ровно ln(10^100000). Я не знаю. А в том варианте который я в начале привел с логарифмами мои знакомые сравнивают именно такие результаты.
В твоем случае интересует man. Хватит ли у него етих старшых розрядов чтоб отличить два произведения которые близки между собой даже припуская, что при умножении не будет погрешности.
ln(10^100000) = 100000 * ln(10) примерно 230258,51
Если отбросить погрешности логарифмирования, то получается примерно тоже самое - ошибка младшего разряда.
Я не случайно написал про отдельную проверку равенства.
А вот самый худший из вариантов - когда произведения ПРАКТИЧЕСКИ совпадают.
Тут уж совсем плохо.
Кстати, как вариант - при перемножении хранить и сколько-то младших разрядов. Тогда будет теряться только середина.
В общем же случае для полноценного сравнения нужны все цифры чисел.
Если отбросить погрешности логарифмирования, то получается примерно тоже самое - ошибка младшего разряда.
Я не случайно написал про отдельную проверку равенства.
А вот самый худший из вариантов - когда произведения ПРАКТИЧЕСКИ совпадают.
Тут уж совсем плохо.
Кстати, как вариант - при перемножении хранить и сколько-то младших разрядов. Тогда будет теряться только середина.
В общем же случае для полноценного сравнения нужны все цифры чисел.
Цитата: Alex_soldier
ln(10^100000) = 100000 * ln(10) примерно 230258,51
Я пошел учить математику :(.
За обяснения по точности спасибо. Больше у меня вопросов нет.