Возможности Пайтона и языка С на бытовом компе

[semikolenov]

Подскажите: бытовой комп на пайтоне или языке С может перемножать ( как вариант, ещё три математические операции) числа длиной 100 млн знаков или это невозможно достичь на бытовом уровне?

Спасибо.

[Ghost_of_past]

semikolenov в сообщении #1675464 писал(а):

Подскажите: бытовой комп на пайтоне

Может конечно, вопрос в скорости и не будет ли он виснуть. Но бытовые компы бывают разные: одно дело простой развлекательный ноутбук 20летней давности, а другое дело - новенький профессиональный ноут. Это разные вещи.

В принципе не уверен, что конкретный язык сильно на это повлияет - например, что на Питоне все будет работать хорошо, а на R неожиданно нет. Хотя возможно совместимость ПО как-то может оказывать влияние...

[semikolenov]

Ghost_of_past в сообщении #1675467 писал(а):

semikolenov в сообщении #1675464 писал(а):

Подскажите: бытовой комп на пайтоне

Может конечно, вопрос в скорости и не будет ли он виснуть. Но бытовые компы бывают разные: одно дело простой развлекательный ноутбук 20летней давности, а другое дело - новенький профессиональный ноут. Это разные вещи.

В принципе не уверен, что конкретный язык сильно на это повлияет - например, что на Питоне все будет работать хорошо, а на R неожиданно нет. Хотя возможно совместимость ПО как-то может оказывать влияние...

Спасибо.
Проект GIMPS заточен специально под работу с простыми числами ( алгоритмы) или просто многоуровневое распаралеливание: не в курсе ?

[wrest]

semikolenov
Дайте пару чисел, я попробую перемножить "на бытовом компе".

[mihaild]

Если что-то не совсем древнее, то вполне подъемно, со временем работы от единиц до сотен секунд в зависимости от деталей.
Стандартная реализация умножения в cpython довольно медленная, в gmpy2 пошустрее. Быстрее всего gnump, либо его биндинг к питону python-gmp (если он еще жив, не проверял).

semikolenov в сообщении #1675468 писал(а):

Проект GIMPS заточен специально под работу с простыми числами ( алгоритмы) или просто многоуровневое распаралеливание

Не просто с простыми, а именно с числами Мерсенна - для них есть тест Люка-Лемера, который позволяет их проверять на простоту гораздо быстрее, чем другие числа такого же размера. Собственно за счет этого теста числа Мерсенна держат рекорд как наибольшие известные простые.

[semikolenov]

(Оффтоп)

wrest в сообщении #1675473 писал(а):

semikolenov
Дайте пару чисел, я попробую перемножить "на бытовом компе".

Спасибо за помощь.
Пока на этапе проверки гипотезы работа.

-- 19.02.2025, 00:22 --

(Оффтоп)

mihaild в сообщении #1675474 писал(а):

Если что-то не совсем древнее, то вполне подъемно, со временем работы от единиц до сотен секунд в зависимости от деталей.
Стандартная реализация умножения в cpython довольно медленная, в gmpy2 пошустрее. Быстрее всего gnump, либо его биндинг к питону python-gmp (если он еще жив, не проверял).

semikolenov в сообщении #1675468 писал(а):

Проект GIMPS заточен специально под работу с простыми числами ( алгоритмы) или просто многоуровневое распаралеливание

Не просто с простыми, а именно с числами Мерсенна - для них есть тест Люка-Лемера, который позволяет их проверять на простоту гораздо быстрее, чем другие числа такого же размера. Собственно за счет этого теста числа Мерсенна держат рекорд как наибольшие известные простые.

Спасибо.

[wrest]

(Оффтоп)

semikolenov в сообщении #1675476 писал(а):

Пока на этапе проверки гипотезы работа.

Ага, ясно.

[Geen]

wrest в сообщении #1675473 писал(а):

Дайте пару чисел, я попробую перемножить "на бытовом компе".

Ага, причём, в сообщении на форуме... ну ладно, в паре сообщений

[zykov]

semikolenov в сообщении #1675464 писал(а):

числа длиной 100 млн знаков

Если перемножить два числа "по 100 миллионов десятичных знаков" (т.е. $10^8$ знаков), то будет число $10^{16}$ знаков. Если примерно по байту на знак, то будет под 10000 терабайт (даже если в 2-2.4 раза меньше, то это мало что меняет). Где взять бытовой комп с таким количеством памяти?

[dgwuqtj]

Нет же, длины чисел при перемножении складываются. Если даже хранить их в десятичном виде по $4$ цифры на $64$-битное целое число (для умножения через модулярное ДПФ), то $2 \cdot 10^8$ знаков — это $200$ мегабайт.

[Yadryara]

zykov в сообщении #1675524 писал(а):

Если перемножить два числа "по 100 миллионов десятичных знаков" (т.е. $10^8$ знаков), то будет число $10^{16}$ знаков.

Ни фига себе, что у нас ЗУ вытворяет.

Если перемножить два числа "по 100 миллионов десятичных знаков" (т.е. $10^8$ знаков), то будет число $2\cdot 10^8$ знаков.

[wrest]

zykov в сообщении #1675524 писал(а):

Если перемножить два числа "по 100 миллионов десятичных знаков" (т.е. $10^8$ знаков), то будет число $10^{16}$ знаков.

Ну не всё так уж драматично. Будет $2\cdot 10^8$ знаков.

[wrest]

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

? a=1;b=1;for(i=1,120,a=a*(random(2^31))^(100000);b=b*(random(2^31))^(100000))
*** _*_: Warning: increasing stack size to 16000000. 
*** _*_: Warning: increasing stack size to 32000000. 
*** _*_: Warning: increasing stack size to 64000000. 
*** _*_: Warning: increasing stack size to 128000000. 
? ##   
***   last result computed in 2min, 3,234 ms.   
? log(a)/log(10) 
%9 = 106720248.94152256841209630055419925005   
? log(b)/log(10) 
%10 = 106350225.57462590252755414765015601449  
? c=a*b;  
*** _*_: Warning: increasing stack size to 16000000.   
 *** _*_: Warning: increasing stack size to 32000000. 
*** _*_: Warning: increasing stack size to 64000000. 
*** _*_: Warning: increasing stack size to 128000000. 
? ##  
 ***   last result computed in 3,059 ms.   
? log(c)/log(10) 
%12 = 213070474.51614847093965044820435526453  
?

Генерация 2 минуты. Умножение сгенерированных чисел - 3 секунды.
Это интерпретируемый язык (pari/gp), на планшете андроид. В один поток.
Ну тут "качество" чисел конечно такое себе. Генерировать большие числа трудно, поэтому я и просил ТС-а дать готовые

[Amw]

zykov в сообщении #1675524 писал(а):

Если примерно по байту на знак...

Зачем же примерно и по байту? И пол-байта с лихвой хватит, причем точно...

[mihaild]

wrest в сообщении #1675538 писал(а):

Ну тут "качество" чисел конечно такое себе. Генерировать большие числа трудно

Раз Вы умеете равномерно генерировать на $[0, 2^{31})$, то просто на каждом шаге умножать на $2^{31}$ (делать сдвиг, если pari/gp само до этого не додумается) и прибавлять случайное число из этого диапазона.