pro.algorithms
Нужно вычислить выражение вот такого вида с точностью 3-4 знака
после запятой: (a * C(0, n) + b * C(1, n) + ... + z * C(n, n))/2^n, n до 50k. есть какие-нибудь идеи, как это сделать, не вылезая в длинную арифметику?
11 ответов
Как быстро растет C(a, b)?
tiom4eg
🇷🇺
Автор вопроса
Как быстро растет C(a, b)?
достаточно быстро, C(25000, 50000) = ~1e15000 (максимальное значение при данных условиях)
достаточно быстро, C(25000, 50000) = ~1e15000 (мак...
Ага... Ну вообще 1e15000 ~ 2^25000 Здесь сложно что-либо говорить, оно с трудом в quadruple precision влезает... Разве что смотреть, не сокращается как-нибудь C(2
tiom4eg
🇷🇺
Автор вопроса
Ага... Ну вообще 1e15000 ~ 2^25000 Здесь сложно чт...
есть вариант банально запихать в дабл эти 1e15000, но тогда точность умирает, даже 3 знака верно не выводит 😞
есть вариант банально запихать в дабл эти 1e15000,...
А там точно нигде ничего не сокращается? потому что иначе без длинной арифметики никак..
tiom4eg
🇷🇺
Автор вопроса
А там точно нигде ничего не сокращается? потому чт...
C(0, n) + ... + C(n, n) = 2^n, но дальше всё ломается, т.к. у каждого слагаемого свой множитель. хотя, наверное стоило упомянуть, что множители отсорчены по неубыванию (a <= b <= c <= ... <= z)
Если я нигде не ошибся: 1. Вычитаем и прибавляем к числителю сумму a * (C(0, n) + .. + C(n, n)). Тогда a * C(0, n) сокращается, остальное преобразуются в (b - a) * C(1, n) + (c - a) * C(2, n) + .., вне дроби оказывается + a. 2. Вычитаем и прибавляем в числителе (b - a) * C(0, n) - вычтенное выносим из дроби как -(b-a)*C(0, n)/2^n. N. Смотрим на полученную дробь и повторяем шаги 1-2, но уже не для a, а для b-a.
tiom4eg
🇷🇺
Автор вопроса
Если я нигде не ошибся: 1. Вычитаем и прибавляем к...
хорошая идея, спасибо, рассмотрю её подробнее
наивно считать в double не работает? (опционально с https://en.wikipedia.org/wiki/Kahan_summation_algorithm)
tiom4eg
🇷🇺
Автор вопроса
наивно считать в double не работает? (опционально ...
Не, пытался, точности не хватает на 3 знака
Не, пытался, точности не хватает на 3 знака
даже с компенсацией ошибок?
Похожие вопросы
Обсуждают сегодня