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

[Geen]

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

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

getrandbits(400_000_000)

[wrest]

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

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

Можно, просто это очень долго.

[wrest]

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

Можно, просто это очень долго.

Поясню -- $2^{32}$ это $~10^1$ десятичных цифр. А нам надо заполнить $10^8$ десятичных цифр. Так что сдвинуть надо $~10^7$ раз. Ну и сгенерировать ещё эти 10 млн. случайных чисел которые будем продвигать. Для интерпретируемого языка это тяжко. Вернее, тяжко для юзера, который будет ждать когда ж это закончится
Так что сгенерировать 50 мегабайт случайного бреда - более-менее легко, а вот сделать из него число разрядностью $\approx 300$ млн. бит - трудно.

[zykov]

dgwuqtj в сообщении #1675526 писал(а):

Нет же, длины чисел при перемножении складываются.

Да, извиняюсь, поторопился и ошибся.
Перемножайте спокойно, всё в память влезает, по времени тоже всё хорошо, где-то $n \log n$.

[Geen]

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

а вот сделать из него число разрядностью $\approx 300$ млн. бит - трудно.

Python 3.11.1 (tags/v3.11.1:a7a450f, Dec  6 2022, 19:58:39) [MSC v.1934 64 bit (AMD64)] on win32
>>> from random import *
>>> from math import *
>>> tic();a=getrandbits(400_000_000);b=getrandbits(400_000_000);toc();log10(a);log10(b);tic();n=a*b;toc();log10(n);
0:00:00.128505
120411998.02910759
120411998.08420475
0:16:14.372622
240823996.11331233

[wrest]

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

Так что сгенерировать 50 мегабайт случайного бреда - более-менее легко, а вот сделать из него число разрядностью $\approx 300$ млн. бит - трудно.

А... оказалось что в pari/gp можно генерить случайные числа любого размера А я почему-то думал что $2^{31}$ максимум. Не знаю почему я так думал.
Ну, в общем,

? a=random(10^(10^8));b=random(10^(10^8));
? ##
  ***   last result computed in 3,162 ms.
? c=a*b;
? ##
  ***   last result computed in 2,366 ms.
? log(c)/log(10)
%10 = 199999999.57713489111468590207305590809
?

Генерация двух случайных чисел 3 секунды, перемножение 2 секунды. Планшет андроид, CPU Qualcomm Snapdragon 8 Gen 1