1. Для умножения столбиком двух чисел длиной в N разрядов нужно сделать N^2 поразрядных умножений и N^2 поразрядных сложений. При выполнении умножения в десятичной системе счисления с помощью кэширования вы можете уменьшить сложность первого этапа с N^2 до 9*N, то есть до пренебрежимо малой. Но при этом сложность второго этапа вырастет примерно в 20 раз потому, что в ином случае сложения выполнялись бы на процессоре разрядами по 8 байт, что примерно 20 сложений в десятичной системе счисления. Итого, общая сложность при переходе к десятичной системе счисления увеличится с 2*N^2 до 20*N^2.
2. Когда автор писал, что сложение быстрее умножения, он имел в виду выполнение операций не для одного разряда, а для двух длинных чисел. Умножение столбиком двух чисел длиной N разрядов выполняется за 2*N^2 поразрядных операций, а сложение - за N поразрядных операций. Сами операции сложения и умножения значений из регистров на процессоре занимают примерно одинаковое время.
Хотел написать всё тоже самое с примерами с предыдущих мест работы. Но нашёл ваш комментарий, с которым полностью согласен, и меня отпустило. Похоже, автор статьи просто не умеет готовить крокодилов. Хочу только напомнить ему, что каждый инструмент имеет свои границы применимости, и каждый специалист применяет их в меру своей квалификации.
Можно вычислять серединным поиском значение любой непрерывной мотонной функции (логарифма, экпоненты и т.д.). Казалось бы, решение подобных простейших задач не заслуживает размазывания на целую статью. Стыдно, но такой уж нынче Хабр победивших продактов, эйчаров и прочих чертей, не знакомых со школьными истинами.
Привет! Тема выбрана интересная. Но есть несколько пожеланий по форме подачи материала.
1. Мне кажется, было бы лучше организовать повествование от общего к частному. Сначала объяснить основную идею. Чтобы проще было понять хочешь ты это читать или нет. Детали реализации дать в конце, может быть в отдельном подразделе, или вообще ссылкой на код. Написать код все потенциальные заинтересованные лица здесь и сами смогут.
2. Я думаю, что в рамках формата статьи подавать материал нужно более простым языком. Желательно без формул. Совсем идеально было бы картинкой. Куда там какой разряд идёт. Как в самоучителе по математике, а не как в учебнике.
3. На мой взгляд, чем короче изложение, тем лучше. Потому, что у человеков размер окна внимания весьма ограничен. Тем кто не ещё знаком с информацией, приходиться это окно мучительно по тексту перемещать. А тем, кто знаком и у кого информация уже в памяти есть, тем читать смысла нет.
Посмотрел темы остальных публикаций в профиле. Вроде бы тоже обещает быть интересно. Сохранил себе в закладки на будущее.
Статья, я считаю, вышла неплохая. Было бы ещё лучше, если бы начинали от общего к частному: сначала показать табличку сравнения скорости выполнения и средней квадратичной ошибки того, что получилось со стандартной реализацией. Чтобы каждому было легче сразу для себя решить, стоит читать дальше или нет. Тем не менее олучилось бодро, с учётом засилия на хабре переведённого вторичного контента.
Я с присущей мне объективностью и богатым опытом написания взвешенных и полностью наполненных пруфами статей, хотел бы указать автору на его неточности.
Эмоционально окрашенные картинки, к примеру, с измерением носа - это ещё объективность или уже пруфы?
Так вот, у вас, а не у нас есть некий мануал, а вот уже у С++ программистов имеется не просто мануал, а целый международный стандарт.
Ты кусок говна в котором полно неопределённого поведения, который поддерживается компиляторами как попало, хоть стандартом назови, эталоном он от этого не станет.
Это было сделано именно для этого, что бы у компилятора было больше свободы оптимизации. Такое решение, но тогда оно было оправдано. Важен контекст.
Что деды воевали не является оправданием нам сейчас жить по дедовьи и совершать те же дедовские ошибки.
Не на что аргументировано возражать. Потому, что ус твоей стороны никаких пруфов, только понты типа "уж мы то знаем как на самом деле". Но ты не сдавайся - позорься до конца!
Ну так надо признать, что основную работу в коммутаторе делает процессор. Следовательно, без импортозамещения процессоров всё остальное пустой звук. А производить свои сопоставимые процессоры в России не возможно. Тогда и не надо врать в заголовке статьи.
Давайте без лживых клише. Совместимость людей в команде тех. специалистов - маловажный вопрос.
1. Для умножения столбиком двух чисел длиной в N разрядов нужно сделать N^2 поразрядных умножений и N^2 поразрядных сложений. При выполнении умножения в десятичной системе счисления с помощью кэширования вы можете уменьшить сложность первого этапа с N^2 до 9*N, то есть до пренебрежимо малой. Но при этом сложность второго этапа вырастет примерно в 20 раз потому, что в ином случае сложения выполнялись бы на процессоре разрядами по 8 байт, что примерно 20 сложений в десятичной системе счисления. Итого, общая сложность при переходе к десятичной системе счисления увеличится с 2*N^2 до 20*N^2.
2. Когда автор писал, что сложение быстрее умножения, он имел в виду выполнение операций не для одного разряда, а для двух длинных чисел. Умножение столбиком двух чисел длиной N разрядов выполняется за 2*N^2 поразрядных операций, а сложение - за N поразрядных операций. Сами операции сложения и умножения значений из регистров на процессоре занимают примерно одинаковое время.
Год прошёл - статьи про алгоритм O(N*ln(N)) так и не появилось. Автор, почему?
Хотел написать всё тоже самое с примерами с предыдущих мест работы. Но нашёл ваш комментарий, с которым полностью согласен, и меня отпустило. Похоже, автор статьи просто не умеет готовить крокодилов. Хочу только напомнить ему, что каждый инструмент имеет свои границы применимости, и каждый специалист применяет их в меру своей квалификации.
Аха-ха-ха, ты гений 🙂 А новость похожа на первоапрельскую шутку.
Можно вычислять серединным поиском значение любой непрерывной мотонной функции (логарифма, экпоненты и т.д.). Казалось бы, решение подобных простейших задач не заслуживает размазывания на целую статью. Стыдно, но такой уж нынче Хабр победивших продактов, эйчаров и прочих чертей, не знакомых со школьными истинами.
Спасибо за статью, спасибо за вновь пережитые воспоминания
В этом разделе мне не хватило дат, чтобы качественнее понастольгировать
Странно, я помню icq у себя на мобиле ещё году в 2007
Подход глубоко вторичный зато работает плохо 👍
Привет! Тема выбрана интересная. Но есть несколько пожеланий по форме подачи материала.
1. Мне кажется, было бы лучше организовать повествование от общего к частному. Сначала объяснить основную идею. Чтобы проще было понять хочешь ты это читать или нет. Детали реализации дать в конце, может быть в отдельном подразделе, или вообще ссылкой на код. Написать код все потенциальные заинтересованные лица здесь и сами смогут.
2. Я думаю, что в рамках формата статьи подавать материал нужно более простым языком. Желательно без формул. Совсем идеально было бы картинкой. Куда там какой разряд идёт. Как в самоучителе по математике, а не как в учебнике.
3. На мой взгляд, чем короче изложение, тем лучше. Потому, что у человеков размер окна внимания весьма ограничен. Тем кто не ещё знаком с информацией, приходиться это окно мучительно по тексту перемещать. А тем, кто знаком и у кого информация уже в памяти есть, тем читать смысла нет.
Посмотрел темы остальных публикаций в профиле. Вроде бы тоже обещает быть интересно. Сохранил себе в закладки на будущее.
Почему ваще такое пубоикуют на Хабре? Что за помойка тут началась?
Статья, я считаю, вышла неплохая. Было бы ещё лучше, если бы начинали от общего к частному: сначала показать табличку сравнения скорости выполнения и средней квадратичной ошибки того, что получилось со стандартной реализацией. Чтобы каждому было легче сразу для себя решить, стоит читать дальше или нет. Тем не менее олучилось бодро, с учётом засилия на хабре переведённого вторичного контента.
Это всё хорошо. Только вот на хабре теперь каждая третья статья - перевод. А из интересных - каждая первая. Что по уникальному контенту?
Бабки собрал и шесть лет ноль выхлопа. Вот из-за таких как ты краудфандинг и умирает.
Эмоционально окрашенные картинки, к примеру, с измерением носа - это ещё объективность или уже пруфы?
Ты кусок говна в котором полно неопределённого поведения, который поддерживается компиляторами как попало, хоть стандартом назови, эталоном он от этого не станет.
Что деды воевали не является оправданием нам сейчас жить по дедовьи и совершать те же дедовские ошибки.
Не на что аргументировано возражать. Потому, что ус твоей стороны никаких пруфов, только понты типа "уж мы то знаем как на самом деле". Но ты не сдавайся - позорься до конца!
Тебе то конечно виднее, мамкин эксперт по ФСБ, проживающий в Усть Пиздюйске.
Очевидно - вместо тысячи аргументов (сарказм). Утверждение в основе статьи на столько же безосновательное, как и все дальнейшие суждения.
Ну так надо признать, что основную работу в коммутаторе делает процессор. Следовательно, без импортозамещения процессоров всё остальное пустой звук. А производить свои сопоставимые процессоры в России не возможно. Тогда и не надо врать в заголовке статьи.
Довольно трудно разобраться, как резать огурцы на салат, если ты не огурец (сарказм).
В open source не приходят писать код за халявой и отсутвием лишего гемора ^_^