Comments 40
Это мой первый перевод и топик на хабре, по этому конструктивная критика приветствуется!
Интересно, почему статья «Real Programmers...» вдруг оказалась сатирической. Мы в своё время считали её описанием «как надо» и в какой-то мере руководством к действию…
Интересно, что автор, пропагандируя математику, делает ошибки, т.к. сложность вычисления k-го числа Фибоначчи по крайней мере Ω(k), а для факториала k — по крайней мере Ω(k*ln(k)). Это исходя из только длины результатов.
Это зависит от точности. Если ему хватит 16 значащих цифр и порядка, то можно быстрее.
А почему вы омегу используете? Там же просто О.
upd. Оказывается, это оценка снизу. Не знал, не знал.
upd. Оказывается, это оценка снизу. Не знал, не знал.
Наконец, а не «на конец».
Мне кажется, что противопоставление Лиспа Фортрану немного уводит акценты в сторону. Сейчас водораздел пролегает не между полным отрицанием роли математики и признанием ее важности, а скорее между культурой дискретной математики (условная культура Lisp) и культурой математики «непрерывной» (условная культура Fortran). То, что сейчас Fortran почти полностью заменен на C, по сути ничего не меняет (хотя рекурсия и стала доступной, да). В свое время был такой известной афоризм: «за душу каждого математика борется ангел топологии и дьявол абстрактной алгебры». Если учесть, что по сути топология (в несколько расширенном смысле) представляет всю непрерывную математику, а абстрактная алгебра — математику дискретную, то сейчас такая же борьба идет за души программистов.
Интересно, что программисты из «непрерывного» лагеря получают существенное преимущество — их методы применимы непосредственно к данным, получаемым из реального мира (звуки, изображения, видео), а их оппоненты ограничены обласями, в которых уже есть так или иначе подготовленные данные. И чем большее распространение получают дешевые устройства получения данных из внешнего мира, тем большее преимущество получает непрерывный лагерь.
Интересно, что программисты из «непрерывного» лагеря получают существенное преимущество — их методы применимы непосредственно к данным, получаемым из реального мира (звуки, изображения, видео), а их оппоненты ограничены обласями, в которых уже есть так или иначе подготовленные данные. И чем большее распространение получают дешевые устройства получения данных из внешнего мира, тем большее преимущество получает непрерывный лагерь.
А зачем эти две вещи противопоставлять? Тот же Google Self-driving Car не поедет, ни без функционального анализа и теории вероятностей, ни без алгоритмов поиска оптимальных маршрутов и автоматического доказательства теорем. Так что… Надо и то, и то знать.
А зачем там автоматическое доказательство теорем?
Чтоб не было скучно в дороге
Насколько я понял из лекций от Google, у машины есть описание правил поездки в виде набора предикатов (всякие там ограничения скорости, возможности совершать повороты, перестраиваться между линиями), начальное положение машины формулируется в виде посылки «теоремы», а цель в виде «следствия». И маршрут получается в виде доказательства этой теоремы. Это можно было бы выразить в виде очень-очень мелкой сеточки на карте, по которой можно было бы запустить поиск по графу, но это слишком тяжело вычислительно, и слишком сложно такую глобальную карту подготовить. Когда рассчитываются локальные манёвры, они используют поиск оптимального маршрута, а когда глобальные, то вот такое вот планирование, на уровне: поедь до этого перекрёстка, потом до следующего и т.д. Они совмещают много техник.
На самом деле, в системном программировании и сетевом очень много математики. Проблема в том, что большинство людей, открывших сокет, уже считают себя великими сетевыми программистами и системными мегахакерами (как товарищ Реймонд, например). Но разве это так: давайте сравним Реймонда с Джерардом Холзманом — это тоже системный программист, который разработал Promela (SPIN); кто из них действительно хакер? Откройте любую серьёзную современную статью по мобильным или p2p сетям, или по современным компиляторам, или по планировщикам реального времени. Там от тервера и математической логики мозги клинит. Люди, к сожалению, слишком быстро обожествляют свои знания того, как нечто можно сделать, и не задумываются о том, почему именно так, и где у этого «как» корни. При этом, знания основ, безусловно, полезны, они дают большую гибкость в выборе подходов. Поэтому математика всегда была важна для действительно хардкорных хакеров.
Лисп, лисп, лисп… Математика не нужна… И только лисперами жива…
Вспоминая свои математические ухищрения для построения некоторых сортировок и поисков, порой заставляет задуматься о том, что без математики все равно никуда… Поверхностное программирование не требует оного, но попробуйте без математики передвинуть хотя бы кнопку или див по красивой траектории — тут сразу вернемся и к геометрии и к математике…
В современном мире очень многие гуманитарные науки начинают сталкиваться с тем, что математика требуется даже в них.
Для перехода в цифровую сферу требуется оцифровка (простите за тавтологию), а большинство оных можно провести только используя математику.
ИМХО, все зависит только от уровня работы, несмотря на язык программирования.
Вспоминая свои математические ухищрения для построения некоторых сортировок и поисков, порой заставляет задуматься о том, что без математики все равно никуда… Поверхностное программирование не требует оного, но попробуйте без математики передвинуть хотя бы кнопку или див по красивой траектории — тут сразу вернемся и к геометрии и к математике…
В современном мире очень многие гуманитарные науки начинают сталкиваться с тем, что математика требуется даже в них.
Для перехода в цифровую сферу требуется оцифровка (простите за тавтологию), а большинство оных можно провести только используя математику.
ИМХО, все зависит только от уровня работы, несмотря на язык программирования.
Печально, когда умные с виду программисты бросаются подобными заявлениями. Если присмотреться внимательно, то в нашем деле математика просто повсюду. Напишите компилятор, не зная математики. Напишите распознаватель лиц на фото в фейсбуке. Придумайте новый эффективный формат кодирования аудио. Честно говоря, даже трудно пресдавить, где математика не нужна.
При этом большинство считает, что высшее образование не нужно. Похоже, что они собираются писать «распознаватели лиц и форматы кодирования аудио», используя знания и навыки школьной математики…
Правда, сейчас скажут, что перечисленными и похожими на них по уровню задачами занимается менее 1% программистов. Вполне возможно, что так и есть.
Правда, сейчас скажут, что перечисленными и похожими на них по уровню задачами занимается менее 1% программистов. Вполне возможно, что так и есть.
>>Похоже, что они собираются писать «распознаватели лиц и форматы кодирования аудио», используя знания и навыки школьной математики…
Похоже просто они не собираются этим заниматься
Похоже просто они не собираются этим заниматься
Программирование разнообразно и включает в себя множество занятий, в которых требуется знание математики на разном уровне. Люди разнообразны и некоторые из них могут сами изучить необходимые им области, высшее образование тоже представлено в разных вариантах, и многие вузы — просто бесполезная трата времени. К чему нужны категоричные суждения?
>>Эти вопросы имеют увлекательный ответ, который не так легко осмыслить
Это точно! Всегда уважал тех кто с математикой на «Ты». К сожалению мой уровень математики очень горько плачет. А попытки улучшить, а не сидеть на месте, приводят к тому что слишком глубоко погружаюсь так что начальная цель уже теряется. К примеру не понятен термин1 лезу искать определение, в найденном непонятны подтермин1,… подтерминN, далее ищу под-подтермин1 чтобы понять подтермин1 и т.д. Пока не вижу выхода из этого замкнутого круга…
Это точно! Всегда уважал тех кто с математикой на «Ты». К сожалению мой уровень математики очень горько плачет. А попытки улучшить, а не сидеть на месте, приводят к тому что слишком глубоко погружаюсь так что начальная цель уже теряется. К примеру не понятен термин1 лезу искать определение, в найденном непонятны подтермин1,… подтерминN, далее ищу под-подтермин1 чтобы понять подтермин1 и т.д. Пока не вижу выхода из этого замкнутого круга…
Ощущение, что автор читал только первые главы учебников по лиспу. Ну, да — факториал и числа фибоначчи. Ну, да, ни кто в своём уме не станет их так считать, если они действительно нужны. Но это же учебники. Они для учёбы, а не для работы! Вот в в первых главах учебников по фортрану что? Эххх, давно не читал учебников по фортрану… Подозреваю, что бинарный поиск в сортированном массиве и, собственно, сортировки? Начиная с пузырьковой, да? :)
Кстати, а что значит взять факториал фракции?
Кстати, а что значит взять факториал фракции?
«факториал фракции» — имеется в виду факториал вещественного числа (или дроби). Математики нашли интеграл, зависящий от параметра, значение которого при целых значениях n этого параметра равно (n-1)!, и назвали его гамма-функцией. Для натуральных n выполняется Г(n)=(n-1)!, поэтому если кто-то хочет определить факториал вещественного числа a>-1, то может взять a!=Г(а+1). Правда, математики термина «факториал вещественного числа» не используют, но это мелочи.
Уместно указать, что тут наблюдается некорректный перевод английского слова «fraction», означающего не только фракцию (в химическом смысле слова; в политическом было бы «faction» без «r»), но и дробь (в математическом смысле). Поэтому desperius должен был записывать «дробь» вместо «фракция» в этом месте.
Посчитайте, пожалуйста асимптотику расчета члена Фибоначчи по обычным формулам, через матричное умножение и через формулу Бине. Напоминаю, что формула Бине корректно работает только пока хватает точности. Задача — определить необходимую точность и посчитать значение формулы, используя самописную вещественную арифметику. И асимптотику пожалуйста. А то глядишь, асимптотика получится хуже, чем через матричное умножение. Напоминаю, что и метод умножения матриц, и формула Бине требуют возведения в степень порядка n (logn по оптимизированной
Да, через матрицы можно найти за O(n*log(n)), используя быстрое умножение (множителем log(log(n)) пренебрегаем) — но надо хорошо повозиться (не так давно это здесь сделали). Через вещественную арифметику (если мы хотим все цифры) получается n*log(n)2: нам достаточно взять чуть больше цифр, чем будет в результате.
С факториалом хуже — там вообще непонятно, есть ли асимптотика, сходящаяся с точностью до целого (ряд Стирлинга расходится — я раньше этого не знал :) ). Какие-то формулы вроде бы сходятся, но насколько быстро?
С факториалом хуже — там вообще непонятно, есть ли асимптотика, сходящаяся с точностью до целого (ряд Стирлинга расходится — я раньше этого не знал :) ). Какие-то формулы вроде бы сходятся, но насколько быстро?
Во многих олимпиадных задачах формулировка ставится по другому — найти остаток n-го числа Фибоначчи на mod. Для матриц асимптотика основывается на том, что сложение чисел имеет асимптотику O(log mod), а в формуле Бине нам все равно нужно вычислять с точностью до последней цифры (O(n)), а уже потом применять операцию взятия остатка от деления
А что мешает нам вычислить sqrt(5) по нужному модулю (возможно, с расширением до GF(p^2)), и воспользоваться формулой Бине напрямую, без вещественной арифметики? В случае составного модуля — применить Китайскую теорему.
А можно поподробнее? Увы, знаний математики не хватает
:)
Возьмём, например, вычисления по модулю P=59. По этому модулю S=sqrt(5)=8 (поскольку 8*8%59==5). Есть еще значение 51, но в формуле нам надо использовать какое-то одно значение.
Подставив это S в формулу для чисел Фибоначчи, получим
F[n]%59=((((S+1)/2)^n-((1-S)/2)^n)/S mod 59) = ((34^n — 26^n)*37)%59. Здесь 34=(1+8+59)/2, 26=(1-8+59)/2, 37=(1+5*59)/8.
Проверяем:
F[0]=(1-1)*37%59 = 0
F[1]=(34-26)*37%59 = 1
F[3]=((34^3-26^3)*37)%59 = (21728*37)%59 = 2
F[10] = 55
и т.п.
Если же по заданному модулю sqrt(5) не существует (например, P=23 или P=125), придется работать с формальными выражениями вида a+b*S (и умножением по формуле (a+b*S)*(c+d*S)=(a*c+5*b*d)+S*(a*d+b*c) — считается за 4 умножения). Будет ли это выгоднее, чем вычисления через матрицы или через формулу для F[2*n], не уверен. В случае, если P%10==0, описанная схема не будет работать вообще (там 1+sqrt(5) на 2 не делится)
Возьмём, например, вычисления по модулю P=59. По этому модулю S=sqrt(5)=8 (поскольку 8*8%59==5). Есть еще значение 51, но в формуле нам надо использовать какое-то одно значение.
Подставив это S в формулу для чисел Фибоначчи, получим
F[n]%59=((((S+1)/2)^n-((1-S)/2)^n)/S mod 59) = ((34^n — 26^n)*37)%59. Здесь 34=(1+8+59)/2, 26=(1-8+59)/2, 37=(1+5*59)/8.
Проверяем:
F[0]=(1-1)*37%59 = 0
F[1]=(34-26)*37%59 = 1
F[3]=((34^3-26^3)*37)%59 = (21728*37)%59 = 2
F[10] = 55
и т.п.
Если же по заданному модулю sqrt(5) не существует (например, P=23 или P=125), придется работать с формальными выражениями вида a+b*S (и умножением по формуле (a+b*S)*(c+d*S)=(a*c+5*b*d)+S*(a*d+b*c) — считается за 4 умножения). Будет ли это выгоднее, чем вычисления через матрицы или через формулу для F[2*n], не уверен. В случае, если P%10==0, описанная схема не будет работать вообще (там 1+sqrt(5) на 2 не делится)
кто-нибудь может объяснить, почему exp(lgamma(n+1)), а не просто tgamma(n+1)?
Sign up to leave a comment.
Хакер-математик