2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу Пред.  1, 2
 
 Re: На какую наибольшую степень числа 3 может делиться сумма?
Сообщение10.09.2025, 23:30 
gris в сообщении #1701340 писал(а):
Dmitriy40, почему в Энциклопедии нет этих замечательных чисел?
Мне откуда знать? Никто не добавил. Добавьте.

 
 
 
 Re: На какую наибольшую степень числа 3 может делиться сумма?
Сообщение11.09.2025, 01:04 
Аватара пользователя
Dmitriy40 в сообщении #1701262 писал(а):
C:\>fsum.exe 1000000007
571737250
Time: 9.283s
Спасибо! Значит, получается, простое число порядка $10^8$ обсчитается за десятые доли секунды, но всего их перебрать надо тоже где-то $10^8$ - задача на годик плюс минус на хорошей машине. Хм. (и не факт, что что-то найдётся, ведь $\kappa_n\sim\kappa_{n-1}!$ - лишь туманная гипотеза/выдумка)

wrest, первооткрыватель двух шлемоблещущих чисел - gris конечно, мне же хотелось попробовать найти третье. Ведь... вот есть даже девятки - т.е. нулевой остаток в этих суммах встречается и не раз, да только не на своем месте. Рано или поздно мог бы и на нужном нолик выпасть

 
 
 
 Re: На какую наибольшую степень числа 3 может делиться сумма?
Сообщение11.09.2025, 01:50 
waxtep в сообщении #1701352 писал(а):
Значит, получается, простое число порядка $10^8$ обсчитается за десятые доли секунды,
Нет, за секунду:
C:\>fsum.exe 100000007
85226649
Time: 1.062s

Зависимость для одного числа от его величины линейная, но числа растут тоже почти линейно (логарифм из-за простых в знаменателе мало влияет), в сумме получается почти квадратично.
Но для времён менее полусекунды начинает влиять время запуска и передачи результата в PARI, потому время перестаёт падать квадратично при уменьшении чисел и становится ближе к линейному.

Для второй задачи, поиска ровно n "нулей", я сделал обработку сразу списка чисел (например все простые в каждой тысяче натуральных), это существенно повысило скорость. Плюс можно же запускать многопоточно. В итоге за 4.5ч в ~3 потока (вместо 4-х имеющихся, это глюки PARI под виндой) проверилось до 1e7. Значит до 1e8 мне хватит пары недель ... Тем более что и простые можно генерить прямо "на лету" (мне лень было добавлять этот код, как и многопоточность реализовывать), тогда PARI вообще не нужен.

 
 
 
 Re: На какую наибольшую степень числа 3 может делиться сумма?
Сообщение11.09.2025, 01:59 
Аватара пользователя
Моя текущая реализация https://github.com/mihaild/dxdy/blob/ma ... l/main.cpp на моей машине обещает перебрать до $10^8$ за сутки.

 
 
 
 Re: На какую наибольшую степень числа 3 может делиться сумма?
Сообщение11.09.2025, 02:20 
mihaild в сообщении #1701356 писал(а):
Моя текущая реализация https://github.com/mihaild/dxdy/blob/ma ... l/main.cpp на моей машине обещает перебрать до $10^8$ за сутки.
Это в 128 потоков что ли? Тогда верю в сутки. У меня их всего 4. Я на 1e7 остановил, найденные восьмёрки привёл выше.

 
 
 
 Re: На какую наибольшую степень числа 3 может делиться сумма?
Сообщение11.09.2025, 02:24 
Аватара пользователя
Dmitriy40 в сообщении #1701357 писал(а):
Это в 128 потоков что ли?
В 24. Восьмерки подтверждаю.

 
 
 
 Re: На какую наибольшую степень числа 3 может делиться сумма?
Сообщение11.09.2025, 02:27 
Кстати, была у меня мысль по ускорению: не выполнять взятие остатка каждое умножение, накопить штук 5-10 умножений (пока влезают в пару-тройку регистров) и потом один раз взять модуль. А уж сложений можно накопить тысячи-миллионы. Но прикинув сколько потребуется умножений и сложений для работы с длинным числом посчитал выигрыш сомнительным (не кардинальным).

И кстати сложение по модулю лучше делать как сложение плюс if, чем с % (скорость может подняться раза в 1.5, проверьте) - не думаю что компилятор заменит медленное деление на сравнение и вычитание.

 
 
 
 Re: На какую наибольшую степень числа 3 может делиться сумма?
Сообщение11.09.2025, 02:38 
Аватара пользователя
Dmitriy40 в сообщении #1701359 писал(а):
И кстати сложение по модулю лучше делать как сложение плюс if, чем с % (скорость может подняться раза в 1.5, проверьте)
Как именно? x += y; if (x > z) x -= z;? У меня сразу становится в полтора раза медленнее (всё целиком, не просто сложение; сложение, соответственно, работает сильно медленнее)
Что там получается в ассемблере - https://godbolt.org/z/6W4qv6ffh - я понять уже не могу.

 
 
 
 Re: На какую наибольшую степень числа 3 может делиться сумма?
Сообщение11.09.2025, 03:47 
mihaild в сообщении #1701360 писал(а):
Как именно? x += y; if (x > z) x -= z;?
Да, типа такого. Только в if знак >=, как и есть в вашем примере кода ниже.
mihaild в сообщении #1701360 писал(а):
У меня сразу становится в полтора раза медленнее (всё целиком, не просто сложение; сложение, соответственно, работает сильно медленнее)
Странно. Но хорошо что проверили.
mihaild в сообщении #1701360 писал(а):
Что там получается в ассемблере - https://godbolt.org/z/6W4qv6ffh - я понять уже не могу.
Там всё как написано, стр. 423-428 - вычитание и если оказалось не меньше, то перезапись на новое.
Тормозит вероятно из-за множества обращений в память, особенно по записи, тем более условных. Такие моменты (условная перезапись памяти) легко могут страшно тормозить. По хорошему должно быть сначала копирование в другой регистр (это есть), вычитание и если что, то модификация регистра (можно одной командой условной пересылки как у меня в коде выше), и лишь в итоге запись готового в память, уже без условий и лишь один раз.

-- 11.09.2025, 03:48 --

Обнаружил у себя ошибку для $2^{31}<p<2^{32}$, поправил, оба файла в облаке обновил, ссылки те же.

-- 11.09.2025, 04:06 --

Проверил как у меня будет при замене sub+cmovc на div: для $p=4294967291$ время ухудшается с 38.7с до 47.4с. Хм, не сильно, думал будет хуже, похоже команда div в процессорах оптимизирована для случая малых чисел.

 
 
 
 Re: На какую наибольшую степень числа 3 может делиться сумма?
Сообщение11.09.2025, 10:51 
Аватара пользователя
Внезапно - можно попросить LLM переписать код на CUDA (если просить написать с нуля, то получается бред), и после некоторого допинывания он вроде бы даже работает (по крайней мере предыдущие результаты воспроизводит), и считает до $10^8$ за 25 минут.
Нашел еще три девятки
73739857: [6235359, 6414028, 20707256, 29077216, 42789242, 48187907, 50455742, 59049130, 71542857]
78527249: [1309012, 1314912, 10538320, 24564045, 24937373, 32475313, 42528008, 48110782, 70855513]
98449157: [21143860, 23027419, 33619199, 48486686, 51781066, 53999947, 57086251, 64851692, 82766190]
Больше ничего интересного не нашлось.
До миллиарда обещает считаться двое суток.

 
 
 
 Re: На какую наибольшую степень числа 3 может делиться сумма?
Сообщение11.09.2025, 15:10 
Аватара пользователя
Dmitriy40 в сообщении #1701361 писал(а):
похоже команда div в процессорах оптимизирована для случая малых чисел
А какие числа тут малые?

 
 
 
 Re: На какую наибольшую степень числа 3 может делиться сумма?
Сообщение11.09.2025, 19:03 
mihaild в сообщении #1701487 писал(а):
А какие числа тут малые?
Максимум в несколько раз (вдвое) больше делителя (который простое число).

-- 11.09.2025, 19:09 --

mihaild в сообщении #1701397 писал(а):
Внезапно - можно попросить LLM переписать код на CUDA (если просить написать с нуля, то получается бред), и после некоторого допинывания он вроде бы даже работает (по крайней мере предыдущие результаты воспроизводит), и считает до $10^8$ за 25 минут.
Удиивтельно что LLM выдал достаточно хороший код, действительно внезапно ...
А вот что хорошо параллелится - не удивительно, тут же можно и по простым параллелить, и по факториалу по модулю. Код внутреннего цикла достаточно простой (умножение, деление, сложение, снова или деление или сравнение плюс условное вычитание, которое кстати на GPU делается вообще без штрафов) и в то же время не настолько простой чтобы уложиться в пяток тактов, как раз задачка для GPU.

 
 
 
 Re: На какую наибольшую степень числа 3 может делиться сумма?
Сообщение11.09.2025, 20:33 
Аватара пользователя
Реализация на CUDA https://github.com/mihaild/dxdy/blob/ma ... al/main.cu. Условное вычитание дало прирост примерно 20% к производительности, алгоритм Барретта при умножении еще примерно утроение. В итоге до $10^8$ считается за 390 секунд, до $10^9$ обещает 10 часов. Еще процентов на 10 можно было бы ускорить отправкой всех чисел на подсчет сразу, но мне больше нравится возможность следить за прогрессом.

-- 11.09.2025, 20:11 --

Dmitriy40 в сообщении #1701521 писал(а):
Удиивтельно что LLM выдал достаточно хороший код, действительно внезапно
Там в целом ничего сложного. Но всю обвязку с копированием я совсем не знаю, как писать, а читать документацию всегда было лень.
В целом у меня просто сильно устаревшее представление о GPU. Я как-то не задумывался, что на них можно на каждом ядре цикл с целочисленной арифметикой считать.

Нашлись девятки
125816333: [4168573, 41608562, 51583106, 53564485, 59596441, 64874051, 66242996, 109743687, 124273619]
128096569: [31083535, 36979974, 47158457, 47485268, 49934824, 60255887, 61654817, 69144802, 75898499]
137719801: [22771441, 34650819, 45451974, 63934796, 67245188, 87495486, 111732945, 116580790, 119821025]
150036223: [24363564, 39953214, 50425127, 68163059, 83537136, 86980045, 108542657, 112341436, 139766002]
Больше, наверное, девятки выкладывать смысла нет. Посмотрим, что найдется до миллиарда.

(Оффтоп)

Первый раз такой шум от GPU, и 83 градуса. Ну зимой буду считать до десяти миллиардов.

 
 
 [ Сообщений: 28 ]  На страницу Пред.  1, 2


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group