Комментарии 24
Звучит как интересная задача для тренировки в свободное время, надо будет как-нибудь самому попробовать её решить:)
Я уже пробовал писать тесты на простоту, но максимум писал тест Ферма для u64, биг инт не пробовал окунаться.
Интересно, например, даст ли метод Карацубы реальный прирост производительности на 1024 битных числах, или нет. На небольших числах он все же плохо себя показывает.
Мне вот тоже довольно интересно, как понимать математику в книгах и статьях. Может посоветуете, с чего начать на базе курса школьной математики 10-11 классов?
На сколько будет медленее если ещё увеличить разрядность?
Проверка простоты специально подобранного числа имеет сложность O(n*n*log(n)), где n - разрядность
Для произвольного числа сложность проверки на простоту выше, если не ошибаюсь.
Если увеличить разрядность вдвое, то будет примерно в 4 раза дольше проверяться. Плюс к этому вероятность встретить простое число снизится в 2 раза. Итого - будет медленнее в 8 раз.
Прочитал с интересом, спасибо! Сам в универе занимался тч, правда аналитической больше, так что люблю эту тему.
Умножение Монтгомери ещё сделать
Всё круто, но я это всё в 14 лет на C++ делал :)
Заняло у меня тогда это около пары дней, но я сразу начал с BigInt
и что же, интересно, вы теперь пишете, в свои N лет? (судя по стилю этого и других комментариев, никак не больше 15-16). И где ваши отлично оформленные и познавательные публикации на Хабре? Я вижу только тонну комментариев с завышенным самомнением зазнавшегося выскочки
А смысл писать что-то на хабре? Я в университете преподавал несколько лет пока времени не перестало хватать вместо этого... Публичных разработок мало, пишу на всём что можно, сейчас в основном C++, TypeScript, PHP. Сервера для онлайн-игр, расширения для PHP (из них публичное только одно), аналитика, BigData. Опыт уже больше 25 лет в разработке, а начинал с C++ и asm.
А самомнение не завышенное, постоянно собеседую программистов и всё это наблюдаю
Все ясно, синдром препода и интервьюера. Рынок всегда состоял на 90% из шлака, сколько себя помню (в айти 18 лет, это когда в офис по 8 в день, не когда начал увлекаться программированием). Но походите по собесам сами в толковые технологичные стартапы - быстро собьют эту спесь, звездную болезнь и вернут на место
Собеседовался, звали и в Яндекс и везде куда ходил ради интереса. ЗП от 500k сейчас мне лично найти не проблема. Синдрома препода никакого нет, ведь ушёл потому что свой бизнес отнимает всё время, а зарабатываю я сейчас в десять раз больше :)
Я в IT гораздо дольше :) Начал в 9 лет, первый заработок в 16 лет, в 18 лет уже имел ЗП 100k, что на текущие деньги около 300k. Создал один из первых частных Lineage 2 серверов в РФ, код был основан на l2j и переписан на 90% мной лично :)
Сочувствую. Это ж надо было всю жизнь ничем кроме программирования не заниматься?.. И как оно? Стоило?
Программирование это хобби же. Я ни дня в жизни не работал, только делал что нравится и где нравится. Объездил кучу стран, получил степень MBA, два диплома к основному высшему, дети, машины, квартиры. Куча знакомых благодаря онлайн-играм и дополнительному образованию. Сегодня вернулся из СПб с комик-кона. Осваиваю 3D-печать на фотополимерной смоле, изучаю 3D-моделирование, помогаю своей женщине с косплеем, недавно вот топор вырезал из фанеры :) Так что считаю - стоило. И всё это не работая, а только занимаясь тем, чем я бы и бесплатно занимался :)
А смысл писать что-то на хабре?
А смысл комментировать что-то на хабре?
, а первая единица гарантирует, что число будет достаточно большим и охватывать весь нужный мне диапазон битов.
то есть вы изначально отбрасываете половину возможных значений рандомного числа (те что меньше 32768)?
Сложно ли генерировать 1024-битные простые числа?