Допустим, код написан, проект синтезируется и никаких ошибок компилятор не показывает. Для обычной программы после этого можно запустить тесты и довольно далеко продвинуться вообще без контакта с физическим миром.
Не понял, что мешает делать тесты для RTL и прогонять их через симулятор? Тоже можно продвинуться довольно далеко без контакта с физическим миром. Да, так не все можно протестировать, но и у софтвера тоже эта проблема есть.
Для целых чисел что-то второй день не могу нагуглить, имя автора забыл :( Там доказывалось, что достаточно двух-трех (в зависимости от четности основания, но только для оснований больше 2) избыточных цифр. Я как-то доказывал (но не публиковал, т.к. слишком незначительное улучшение по сравнению с упомянутой работой) что достаточно двух дополнительных цифр для любого основания больше 2, чтобы перенос не распространялся дальше, чем на 1 разряд.
Не обязательно N^2 потоков. То, что можно сделать параллельно, можно сделать и последовательно. А значит можно использовать столько АЛУ-ядер, сколько есть. В отличие от стандартной позиционной системы, в которой складывать длинные числа вы будете на одном ядре, даже если у вас рядом таких ядер миллион простаивает.
Другими словами, неограниченный параллелизм здесь - не требование, а возможность.
Другое дело, что существующий подход к распараллеливанию вычислений длинной арифметикой не очень интересуется, и на то есть свои причины. И тут я с вами могу только согласиться: пока эти модели от широкой практики (по крайней мере, по моим данным) довольно далеки.
Но статья-то называется “Математики до сих пор не уверены, как быстрее всего перемножать числа”. А системы с избыточностью имеют прямое отношение к этой неуверенности: доказано, что это теоретически быстрее изолированно на сложении/умножении, но не доказано, что этот подход имеет преимущество перед другими подходами к распараллеливанию целевых алгоритмов (для которых арифметика - это не цель, а средство).
Нет, не ошибаюсь. Это результат, доказанный для сложения чисел, записанных в любой из избыточных форм, а не только “нормальных”. Под рукой ссылок на работы не нашлось, но если интересно, могу поискать.
В стандартной позиционной системе счисления операция сложения выполняется за O(N), т.к. бит переноса может распространяться на любое расстояние, вплоть до N, а значит параллельное сложение отдельных знаков слагаемых ничего не дает.
А в системах с избыточностью распространение переноса можно ограничить константой (есть системы, где эта константа равна 1), соответственно, сложение можно распараллелить и выполнить за один шаг, т.е. получить O(1).
То же касается и умножения числа длины N на число длины 1. В системах с избыточностью оно тоже выполняется за O(1). В обычной позиционной системе это делается за O(N), без вариантов.
В комментариях выше упоминалось, что процессорах умножение и сложение целых чисел выполняется довольно хитро и гораздо быстрее, по числу шагов, чем Карацуба. Потому что под капотом там как раз избыточные системы, только с ограниченной длиной чисел и с ограниченным параллелизмом.
У меня первая реакция была похожа на Вашу. Но потом просто попытался наглядно представить себе ситуацию: внезапное сокращение сроков с месяцев до двух недель плюс незапланированная (кстати, вот за этот факап можно попробовать покритиковать, да) доработка базовых протоколов, на которых держится вся софтовая часть проекта. Тут у кого угодно обязаны были наступить проблемы с коммуникацией.
Вы систематически путаете компании (юрлица) и проекты (дистрибутивы, исходный код). PostgreSQL - это проект, а не компания. Нет юрлица, которому он принадлежит. И не продался Постгрес крупному бизнесу не потому, что майнтейнеры работали в одной сильной и независимой компании (ее просто не было), а потому, что работали в разных, в том числе, крупных, компаниях. И ни одна компания не смогла ни получить права решающего голоса в коллективе майнтейнеров, ни “утопить” свободную версию PostgreSQL, чтобы заменить ее своей, проприетарной версией.
Кстати, даже если бы такая компания нашлась, не факт, что ей удалось бы удержать власть. Именно в силу лицензии. Подобную историю мы могли наблюдать с nodejs (гуглить joyent и io.js).
PostgreSQL и Postgres Pro уникальны тем, что они не продались крупному бизнесу, а с самого основания (30 лет подряд) вполне успешно пытаются вести дела самостоятельно как независимая компания.
Вы что-то путаете, PostgreSQL и Postgres Pro - это не компании. А компания Postgres Professional существует, очевидно, сильно меньше 30 лет.
Специально искал комментарий про Постгрес. Для тех, кто не сильно следит за этой СУБД, могут быть не очевидны несколько фактов:
Постгрес родом из того же Беркли.
Изначально распространялся под лицензией BSD, да и нынешняя лицензия имеет прямые родственные с ней связи.
В сообществе Постгрес приветствуется свобода делать закрытые форки, т.к. практика показала - им выгодно, по разным причинам, делать вклад в основную ветку.
Не знаю, что там на самом деле, но могу предположить и прямо противоположную проблему: из-за бурного роста часть инженеров могла перейти на менеджерские позиции и проявить себя там, скажем так, хуже, чем в роли инженеров. А теперь эту ошибку исправляют.
Вы рассуждаете о сферической автоматизации в вакууме. В реальном же мире все куда прозаичнее: после автоматизации бардака сопротивление попыткам навести порядок только вырастет - теперь упираться будет еще и система автоматизации.
Так вы посмотрите, что было раньше: те самые черные списки, которыми банки обменивались между собой. А БКИ появились уже позже, как способ ввести данную потребность банков в правовое поле.
Можно предположить, что рынок труда просто дозревает медленнее кредитного рынка. И будут нам и черные списки, и "Бюро трудовой истории"...
Интересно, практикует ли кто-нибудь такой метод, как запрос рекомендаций с предыдущего места работы? Помогает? По идее, если человек работал на одном месте больше года, несоответствие образа реальным результатам должно раскрыться.
"Начинающим" программистам не нужна стройная система знаний. Им нужна практика, им нужно "заговорить" на новом языке, не вдаваясь в ньюансы что такое там этот statement - выражение/оператор/инструкция/утверждение или ещё что-то.
Так ведь именно для того, чтобы быстро "заговорить" на новом для себя языке программирования, и нужна стройная система знаний. Например, когда я был студентом, нас больше года плотно терроризировали моделями вычислений, нотациями определения языков, в том числе все эти statements и operators, а потом за несколько занятий дали что-то около 20 языков. После этого конкретным языкам уже не учили, справедливо считая, что студент справится с этим сам.
Возможно, столкновение позиций тут происходит из-за того, кого считать "начинающим". Если я правильно понял, Вы имеете ввиду тех, кто недавно написал свой первый hello world. Тут можно только согласиться: абстрактная теория, которая никак не вяжется с личным опытом, скорее оттолкнет от программирования, чем поможет его освоить.
Но с другой стороны, даже выпускник ВУЗа, который начал программировать еще в школе, со всеми основаниями может считаться начинающим. И этому товарищу от стройной системы знаний одна сплошная польза.
Поразмышлял на досуге над подходом. Что, на мой взгляд, однозначно интересно: если взять за аксиому отказ от тотальной типизации и поставить вопрос о том, как может выглядеть разумная частичная типизация, то в первую очередь на ум приходят именно контракты на границах сервисов, библиотек, модулей. Причем это даже не будет стоить сильно дорого, т.к. документировать и тестировать эти границы все равно надо, и речь только о том, чтобы делать это понятным в т.ч. и для IDE способом. Идею, как Вы это сделали в своем проекте я понял, думаю, у себя ее воспроизвести тоже смогу, когда дозрею.
В любом случае, спасибо за публикацию своих идей! Последующие публикации на тему пока не смотрел, но, видимо, еще посмотрю :)
Хорошая статья. Еще можно добавить, что рассеянное мышление возможно и без отвлечения от работы.
У меня был случай: надо было разобраться в одной статье по компьютерной лингвистике. Ее автор писал для своих, кто "в теме", но мне эта область была тогда совсем незнакома. Читаю первое предложение и не понимаю ничего. Читаю его еще раз — эффект тот же. В итоге оставил попытки что-то понять и просто прочитал эту статью о зюзрях и хухрях от начала до конца несколько раз. Раз то ли на четвертый, то ли на пятый смысл текста как-то сам собой прояснился, и осталось только разобраться с деталями.
Если что, отказываться от отдыха не призываю. Мысль, скорее, в обратном: даже когда занят делом, полная концентрация иногда может мешать.
Не понял, что мешает делать тесты для RTL и прогонять их через симулятор? Тоже можно продвинуться довольно далеко без контакта с физическим миром. Да, так не все можно протестировать, но и у софтвера тоже эта проблема есть.
Вспомнил, Frougny. https://www.maths.tcd.ie/EMIS/journals/JIS/VOL16/Frougny/frougny3.pdf
Для целых чисел что-то второй день не могу нагуглить, имя автора забыл :( Там доказывалось, что достаточно двух-трех (в зависимости от четности основания, но только для оснований больше 2) избыточных цифр. Я как-то доказывал (но не публиковал, т.к. слишком незначительное улучшение по сравнению с упомянутой работой) что достаточно двух дополнительных цифр для любого основания больше 2, чтобы перенос не распространялся дальше, чем на 1 разряд.
А для действительных вот: https://keldysh.ru/abrau/2020/theses/54.pdf
Особая физика тут не нужна.
Не обязательно N^2 потоков. То, что можно сделать параллельно, можно сделать и последовательно. А значит можно использовать столько АЛУ-ядер, сколько есть. В отличие от стандартной позиционной системы, в которой складывать длинные числа вы будете на одном ядре, даже если у вас рядом таких ядер миллион простаивает.
Другими словами, неограниченный параллелизм здесь - не требование, а возможность.
Другое дело, что существующий подход к распараллеливанию вычислений длинной арифметикой не очень интересуется, и на то есть свои причины. И тут я с вами могу только согласиться: пока эти модели от широкой практики (по крайней мере, по моим данным) довольно далеки.
Но статья-то называется “Математики до сих пор не уверены, как быстрее всего перемножать числа”. А системы с избыточностью имеют прямое отношение к этой неуверенности: доказано, что это теоретически быстрее изолированно на сложении/умножении, но не доказано, что этот подход имеет преимущество перед другими подходами к распараллеливанию целевых алгоритмов (для которых арифметика - это не цель, а средство).
Нет, не ошибаюсь. Это результат, доказанный для сложения чисел, записанных в любой из избыточных форм, а не только “нормальных”. Под рукой ссылок на работы не нашлось, но если интересно, могу поискать.
Нет, N здесь тоже, как и в статье - длина числа.
В стандартной позиционной системе счисления операция сложения выполняется за O(N), т.к. бит переноса может распространяться на любое расстояние, вплоть до N, а значит параллельное сложение отдельных знаков слагаемых ничего не дает.
А в системах с избыточностью распространение переноса можно ограничить константой (есть системы, где эта константа равна 1), соответственно, сложение можно распараллелить и выполнить за один шаг, т.е. получить O(1).
То же касается и умножения числа длины N на число длины 1. В системах с избыточностью оно тоже выполняется за O(1). В обычной позиционной системе это делается за O(N), без вариантов.
В комментариях выше упоминалось, что процессорах умножение и сложение целых чисел выполняется довольно хитро и гораздо быстрее, по числу шагов, чем Карацуба. Потому что под капотом там как раз избыточные системы, только с ограниченной длиной чисел и с ограниченным параллелизмом.
У меня первая реакция была похожа на Вашу. Но потом просто попытался наглядно представить себе ситуацию: внезапное сокращение сроков с месяцев до двух недель плюс незапланированная (кстати, вот за этот факап можно попробовать покритиковать, да) доработка базовых протоколов, на которых держится вся софтовая часть проекта. Тут у кого угодно обязаны были наступить проблемы с коммуникацией.
В системах счисления с избыточностью и неограниченным параллелизмом умножение выполняется за log(N) шагов.
Статья без упоминания этого факта, мягко говоря, не полна.
Вы систематически путаете компании (юрлица) и проекты (дистрибутивы, исходный код). PostgreSQL - это проект, а не компания. Нет юрлица, которому он принадлежит. И не продался Постгрес крупному бизнесу не потому, что майнтейнеры работали в одной сильной и независимой компании (ее просто не было), а потому, что работали в разных, в том числе, крупных, компаниях. И ни одна компания не смогла ни получить права решающего голоса в коллективе майнтейнеров, ни “утопить” свободную версию PostgreSQL, чтобы заменить ее своей, проприетарной версией.
Кстати, даже если бы такая компания нашлась, не факт, что ей удалось бы удержать власть. Именно в силу лицензии. Подобную историю мы могли наблюдать с nodejs (гуглить joyent и io.js).
Вы что-то путаете, PostgreSQL и Postgres Pro - это не компании. А компания Postgres Professional существует, очевидно, сильно меньше 30 лет.
Специально искал комментарий про Постгрес. Для тех, кто не сильно следит за этой СУБД, могут быть не очевидны несколько фактов:
Постгрес родом из того же Беркли.
Изначально распространялся под лицензией BSD, да и нынешняя лицензия имеет прямые родственные с ней связи.
В сообществе Постгрес приветствуется свобода делать закрытые форки, т.к. практика показала - им выгодно, по разным причинам, делать вклад в основную ветку.
Не знаю, что там на самом деле, но могу предположить и прямо противоположную проблему: из-за бурного роста часть инженеров могла перейти на менеджерские позиции и проявить себя там, скажем так, хуже, чем в роли инженеров. А теперь эту ошибку исправляют.
Вы рассуждаете о сферической автоматизации в вакууме. В реальном же мире все куда прозаичнее: после автоматизации бардака сопротивление попыткам навести порядок только вырастет - теперь упираться будет еще и система автоматизации.
Так вы посмотрите, что было раньше: те самые черные списки, которыми банки обменивались между собой. А БКИ появились уже позже, как способ ввести данную потребность банков в правовое поле.
Можно предположить, что рынок труда просто дозревает медленнее кредитного рынка. И будут нам и черные списки, и "Бюро трудовой истории"...
Ну банки же как-то договорились о кредитных историях.
Интересно, практикует ли кто-нибудь такой метод, как запрос рекомендаций с предыдущего места работы? Помогает? По идее, если человек работал на одном месте больше года, несоответствие образа реальным результатам должно раскрыться.
Так ведь именно для того, чтобы быстро "заговорить" на новом для себя языке программирования, и нужна стройная система знаний. Например, когда я был студентом, нас больше года плотно терроризировали моделями вычислений, нотациями определения языков, в том числе все эти statements и operators, а потом за несколько занятий дали что-то около 20 языков. После этого конкретным языкам уже не учили, справедливо считая, что студент справится с этим сам.
Возможно, столкновение позиций тут происходит из-за того, кого считать "начинающим". Если я правильно понял, Вы имеете ввиду тех, кто недавно написал свой первый hello world. Тут можно только согласиться: абстрактная теория, которая никак не вяжется с личным опытом, скорее оттолкнет от программирования, чем поможет его освоить.
Но с другой стороны, даже выпускник ВУЗа, который начал программировать еще в школе, со всеми основаниями может считаться начинающим. И этому товарищу от стройной системы знаний одна сплошная польза.
В бесконечность прогресса веруете? Ну-ну )
Поразмышлял на досуге над подходом. Что, на мой взгляд, однозначно интересно: если взять за аксиому отказ от тотальной типизации и поставить вопрос о том, как может выглядеть разумная частичная типизация, то в первую очередь на ум приходят именно контракты на границах сервисов, библиотек, модулей. Причем это даже не будет стоить сильно дорого, т.к. документировать и тестировать эти границы все равно надо, и речь только о том, чтобы делать это понятным в т.ч. и для IDE способом. Идею, как Вы это сделали в своем проекте я понял, думаю, у себя ее воспроизвести тоже смогу, когда дозрею.
В любом случае, спасибо за публикацию своих идей! Последующие публикации на тему пока не смотрел, но, видимо, еще посмотрю :)
Хорошая статья. Еще можно добавить, что рассеянное мышление возможно и без отвлечения от работы.
У меня был случай: надо было разобраться в одной статье по компьютерной лингвистике. Ее автор писал для своих, кто "в теме", но мне эта область была тогда совсем незнакома. Читаю первое предложение и не понимаю ничего. Читаю его еще раз — эффект тот же. В итоге оставил попытки что-то понять и просто прочитал эту статью о зюзрях и хухрях от начала до конца несколько раз. Раз то ли на четвертый, то ли на пятый смысл текста как-то сам собой прояснился, и осталось только разобраться с деталями.
Если что, отказываться от отдыха не призываю. Мысль, скорее, в обратном: даже когда занят делом, полная концентрация иногда может мешать.