Да, типа как таблицу квадратов: n^2, n^4, n^8, n^16, n^32. В общем случае n^(2^i). Но в принципе можно, наверное, извратиться, чтобы и без таблицы вовсе. Или можно таблицу сделать в стеке и рекурсией вынимать из неё значения.
В принципе для итеративного возведения в целую степень можно было написать функцию, которая возводит в квадраты. Потребовалось бы сильно меньше итераций.
n^2 - (n^2)^2 - .... - n^4096 (12 шагов для получения n^4096) *(n^2048)*(n^1024)*(n^512)*(n^256)*(n^64) плюс ещё 5 умножений на известные числа
Да, из математических программ. Я использую PARI для математического моделирования, модульной арифметики и криптографических задач.
До этого пользовался Maxima, а ещё до этого Derive. Последняя впечатлила ещё тогда, когда работала под DOS.
Mathematica - совсем чуть-чуть.
Системы компьютерной алгебры меня очаровали ещё давно. Дают чувство волшебства, когда сложные задачи могут символьно решать. Или численно с невообразимой точностью.
PARI ещё умеет мультипроцессорность использовать очень просто. Отдельную статью напишу про это.
Вы что-то путаете. Вот официальное место для скачки. Там последняя версия 1.07.
The fourth is an independent implementation by Gavin Howard[1] that is included in Android (operating system),[2][3] FreeBSD as of 13.3-RELEASE,[4][5][6] and macOS as of 13.0.[7][8][9]
Потом я сделал в Математике: (N[1 + 1/10^24443, 50000])^N[10^24443, 50000]
Получил простыню и проверил все знаки, что посчитала PARI - знаки верные. Вывод: Математика иногда жульничает и не выдаёт результат с нужной точностью. То, что на встроенный показатель точности полагаться нельзя - это плохо.
Потом в PARI вычислил следующее: (1.0 + 1.0/10^24444)^(10.0^24444) 2.7182818284590452353602874713526624977572470936999595749669675985385547268541
Получил в ответ короткое число, как видишь.
Вывод: механизм возведения в степень у обоих программ схож. Если показатель степени вещественное число, то считает урезанно. Если показатель степени целый, то старается считать как можно точнее. C целым показателем показателем степени Математика страшно замедляется, но быстрее PARI в 2.5 раза, правда чисел выводит всё-равно раза в 2 меньше.
С целым показателем степени Математика работает существенно дольше. Уже всего в 3 раза быстрее, чем PARI. Но, чисел выдала с целым показателем значительно меньше, чем PARI.
Чтобы заставить Математику выдать 24500 цифр я использовал выражение:
(N[1 + 1/10^24443, 50000])^(10^24443) // Timing
И на моём ноуте оно выполнялось 29 секунд. Против 10 секунд у PARI.
А вот в вещественной степени Математика оказалась в 2.5 раза быстрее. Но опять с потерей точности.
PARI - 5 микросекунд (1.0 + 1/10^24443)^(10^24443+0.0) 2.7182818284590452353602874713526624977572470936999595749669676260605536564921
Математика (N[1 + 1/10^24443, 24500])^N[10^24443, 24500] // Timing {0.002106, 2.71828182845904523536028747135266249775724709369995957497}
Как выяснилось есть много подводных камней. И функции возведения в степень, если экспонента вещественная сделаны с существенной потерей точности в обоих программах.
Видимо, Математика как-то заточена чтобы немножно хитрить на больших числах, Пари пытается считать точно и вылетает по памяти на очень больших числах.
Пока что я вижу, что при одинаковой выходной точности PARI работает не хуже, а временами лучше (на целочисленных степенях).
А какая будет логика суммирования в double double? Положительные значения в одну переменную, а отрицательные в другую? Почему это даст прирост точности?
11-я математика с указанием избыточной точности на ноуте тоже посчитала c 10^1000000000. Видимо, дело в том, что когда мы используем целые Mathematica преобразует в дробь, а дробь уже пытается перевести в целое.
А с избыточной точностью числа сразу получаются вещественными.
Но проверил ниже и не подтвердилось...
(1 + N[1/10^2000, 1000])^N[10^2000, 1000] Overflow[] Это выражение у меня вызывает Overflow, хотя каждый компонент в отдельности это Real
Фигня вышла такая же, как и у меня. Тоже ноль. Кстати, а зачем ты (можно так?) указываешь точность в миллиардах знаков? Для моего теста нужна всего лишь 1000.
Похоже ваш код так и делает, как я предложил. Извините, торопился, понял неправильно.
Да, типа как таблицу квадратов: n^2, n^4, n^8, n^16, n^32. В общем случае n^(2^i). Но в принципе можно, наверное, извратиться, чтобы и без таблицы вовсе. Или можно таблицу сделать в стеке и рекурсией вынимать из неё значения.
Так меньше всего действий. Всё через умножение.
Вопрос. Если бы у вас стояла задача просто сделать телеграмм мини апп, то какой бы стэк вы выбрали?
Представьте у клиента нет никаких мобильных приложений. Причём, желательно, чтобы бэкэнд можно было подключить на любом языке, не только на node.js.
В принципе для итеративного возведения в целую степень можно было написать функцию, которая возводит в квадраты. Потребовалось бы сильно меньше итераций.
n^2 - (n^2)^2 - .... - n^4096 (12 шагов для получения n^4096)
*(n^2048)*(n^1024)*(n^512)*(n^256)*(n^64) плюс ещё 5 умножений на известные числа
Итого 17 шагов.
Спасибо. Исправил.
Вставил ссылку на этот коммент в статью. Спасибо!
Вставил инфу о BSD версии bc в статью и твоём тестировании.
Вставил ссылку на твоё тестирование в статью.
Сколько стоят?
Да, из математических программ. Я использую PARI для математического моделирования, модульной арифметики и криптографических задач.
До этого пользовался Maxima, а ещё до этого Derive. Последняя впечатлила ещё тогда, когда работала под DOS.
Mathematica - совсем чуть-чуть.
Системы компьютерной алгебры меня очаровали ещё давно. Дают чувство волшебства, когда сложные задачи могут символьно решать. Или численно с невообразимой точностью.
PARI ещё умеет мультипроцессорность использовать очень просто. Отдельную статью напишу про это.
Спасибо за сравнение и комментарии. Кстати, благодаря нашим тестам я нашёл небольшой баг в PARI и отправил вчера баг-репорт.
Да, чтобы задать вещественную степеньв Pari нужно к целому числу, например, добавить 0.0. Чтобы произошло преобразование типа к вещественному.
Попробуйсте посмотреть до какого порядка нормально работают эти утилиты и за какое время, пожалуйста. Я вставлю информацию в статью.
Вы что-то путаете. Вот официальное место для скачки. Там последняя версия 1.07.
The fourth is an independent implementation by Gavin Howard[1] that is included in Android (operating system),[2][3] FreeBSD as of 13.3-RELEASE,[4][5][6] and macOS as of 13.0.[7][8][9]
В линуксе эта версия не используется.
Итак, результат любого деления/умножения/степени c участием обычного float имеет тип обычного float.
1.0 / SetPrecision[n, 24500] // Precision15.9546
SetPrecision[Pi, 24500]^ 3.0 // PrecisionMachinePrecision
N - не гарантированно повышает точность. В отличие от SetPrecision.
N[1.0, 24500] // Precision
MachinePrecision
SetPrecision[1.0, 24500] // Precision
24500
Если в середине числа много нулей, а в конце значащий бит, то Математика поднимает точность в 2 раза
1 + 1/SetPrecision[n, 24500] // Precision48943
Иногда при экспоненциации Математика теряет точность (если показатель степени вещественен, но не всегда).
(1 + 1/SetPrecision[n, 24500])^SetPrecision[n, 24500] // Precision
72.9546
SetPrecision[Pi, 24500]^ SetPrecision[Pi, 24500] // Precision
24499.2
Вот сколько неочевидных моментов....
Не уверен, что это хорошо, что Математика сама решает какую точность выдать.
(N[1 + 1/10^24443, 24500])^N[10^24443, 24500]2.71828182845904523536028747135266249775724709369995957497
(N[1 + 1/10^24443, 24500])^N[10^24443, 24500] // Precision
57
Когда я сделал это в PARI она честно выплюнула огромную простыню.
default(realprecision, 24500);(1 + 1.0/10^24443)^(10^24443)
2.718281828459045235360287471352662497757247093699959574966967627724076630353547594571382178525166427427466391932003059.......................
Потом я сделал в Математике:
(N[1 + 1/10^24443, 50000])^N[10^24443, 50000]Получил простыню и проверил все знаки, что посчитала PARI - знаки верные.
Вывод: Математика иногда жульничает и не выдаёт результат с нужной точностью.
То, что на встроенный показатель точности полагаться нельзя - это плохо.
Потом в PARI вычислил следующее:
(1.0 + 1.0/10^24444)^(10.0^24444)2.7182818284590452353602874713526624977572470936999595749669675985385547268541
Получил в ответ короткое число, как видишь.
Вывод: механизм возведения в степень у обоих программ схож. Если показатель степени вещественное число, то считает урезанно. Если показатель степени целый, то старается считать как можно точнее. C целым показателем показателем степени Математика страшно замедляется, но быстрее PARI в 2.5 раза, правда чисел выводит всё-равно раза в 2 меньше.
(N[1 + 1/10^24443, 24500])^(10^24443) // Timing{3.70777, 2.71828182845904523536028747135266249775724709369995957497}
С целым показателем степени Математика работает существенно дольше. Уже всего в 3 раза быстрее, чем PARI. Но, чисел выдала с целым показателем значительно меньше, чем PARI.
Чтобы заставить Математику выдать 24500 цифр я использовал выражение:
(N[1 + 1/10^24443, 50000])^(10^24443) // TimingИ на моём ноуте оно выполнялось 29 секунд. Против 10 секунд у PARI.
А вот в вещественной степени Математика оказалась в 2.5 раза быстрее. Но опять с потерей точности.
PARI - 5 микросекунд
(1.0 + 1/10^24443)^(10^24443+0.0)2.7182818284590452353602874713526624977572470936999595749669676260605536564921
Математика
(N[1 + 1/10^24443, 24500])^N[10^24443, 24500] // Timing{0.002106, 2.71828182845904523536028747135266249775724709369995957497}
Как выяснилось есть много подводных камней. И функции возведения в степень, если экспонента вещественная сделаны с существенной потерей точности в обоих программах.
Видимо, Математика как-то заточена чтобы немножно хитрить на больших числах, Пари пытается считать точно и вылетает по памяти на очень больших числах.
Пока что я вижу, что при одинаковой выходной точности PARI работает не хуже, а временами лучше (на целочисленных степенях).
А какая будет логика суммирования в double double? Положительные значения в одну переменную, а отрицательные в другую? Почему это даст прирост точности?
Есть какой-то подвох. Это выражение выдаёт результат примерно в 500 цифр
(N[1 + 1/10^24444, 25000])^N[10^24444, 25000] // Timing
А вот это в несколько тысяч. Это странно
(N[1 + 1/10^4000, 25000])^N[10^4000, 25000] // Timing
Это странно. Если поднять точность до 50000, то получается простыня...
11-я математика с указанием избыточной точности на ноуте тоже посчитала c 10^1000000000. Видимо, дело в том, что когда мы используем целые Mathematica преобразует в дробь, а дробь уже пытается перевести в целое.
А с избыточной точностью числа сразу получаются вещественными.
Но проверил ниже и не подтвердилось...
(1 + N[1/10^2000, 1000])^N[10^2000, 1000]
Overflow[]
Это выражение у меня вызывает Overflow, хотя каждый компонент в отдельности это Real
(N[1, 1000] + N[1/10^2000, 1000])^N[10^2000, 1000]
Overflow[]
(1.0 + N[1/10^2000, 1000])^N[10^2000, 1000]
1.0
Похоже, что overflow означает, что ему не хватает точности. что теряет разряды. Но ведь это не проблема при апроксимации?
(N[1 + 1/10^2000, 1000])^N[10^2000, 1000]
Тоже overflow
Фигня вышла такая же, как и у меня. Тоже ноль. Кстати, а зачем ты (можно так?) указываешь точность в миллиардах знаков? Для моего теста нужна всего лишь 1000.