Очень-очень большие целые числа - как вычислить?

[Hasim]

Попалась задачка (привожу только для сведения) :

найти наибольшее двузначное число n при котором остаток от деления числа 3 в степени n на 7 равен 5

или
3^n=7N+5
из неких соображений следует, что возможно n=95

Попытка проверить это вычислениями по формулам на листе провалилась:
точность вычислений крайне недостаточна для точного вычисления 3 в степени 95

Вопрос: как можно точно вычислять такие очень большие целые числа?

PS. Ясно, что приближенные вычисления ничего не дадут.

[JohnSUN]

Попытка проверить это вычислениями по формулам на листе провалилась:
точность вычислений крайне недостаточна для точного вычисления 3 в степени 95

"Ти что? Нарочно, да?Думаешь, если ОпенСоурс вспильчивый - так его дражнить можно?!!" (Жванецкий-Карцев)

Во-первых, не 95, а 89
Во-вторых, ты что - всерьёз собирался считать всю эту ерунду? Зачем?!!
A1 = 9
B1 = MOD(3^A1;7)=5
Растягиваем вниз на 90 ячеек
Ищем (глазами) самую нижнюю ИСТИНА

ЗЫ. А все подходящие двузначные числа - такие: 11, 17, 23, 29, 47, 48, 52, 56, 66, 71, 73, 76, 89
Ой, что это я такое понаписывал? Вечер пятницы, конец трудной недели... Не иначе как с устатку мозги ушли отдыхать... 

[Hasim]

В том и дело, что вычисления на листе не совпадают с выводами теории чисел.
Подходящие числа (любые, а не только двузначные) по теории = 5+6k, где k - любое целое неотрицательное число
5    11   17   23   29   35    41   47   53   59   65   71   77    83   89   95   101   107   113 ...

От твоих чисел отличаются!

Да и от моих тоже!

Можешь выложить твои вычисления?

[DixiX57]

В офисных программах, напрямую - никак. Все они используют IEEE 754 со всеми присущими проблемами. Вот, например, интересная статья про http://www.softelectro.ru/ieee754.html. Ряд языков программирования позволяет вычислять с большей точностью, если мне не изменяет память, LISP, есть какие-то расширения для C, вспомню ещё, - напишу.

[greenman]

Скорее http://comp-science.narod.ru/DL-AR/okulov.htm

http://en.wikipedia.org/wiki/GNU_Multiple_Precision_Arithmetic_Library

http://forum.openoffice.org/en/forum/viewtopic.php?f=9&t=60167

P.S. Любопытства ради немного повозился. На питоне делается элементарно. А сейчас, как я понимаю, питон подключается к либре. Только вот как именно, не разбирался.

Пример на python2

Код Выделить Развернуть


for i in range(1L,150L):
   if (pow(3L, i) % 7L) == 5L:
print i,


5 11 17 23 29 35 41 47 53 59 65 71 77 83 89 95 101 107 113 119 125 131 137 143 149

[DixiX57]

Договорились, что стандартными средствами не получится? Надо писать хоть маленький, но код на питоне.
В дополнение:
Интерактивный интерпретатор BC:

Код Выделить Развернуть

for(i=10;i<100;i++) if(3^i%7==5) print i," "
11 17 23 29 35 41 47 53 59 65 71 77 83 89 95
Maxima

Код Выделить Развернуть

for i:10 thru 99 do if mod(3^i,7)=5 then display(i)
i = 11 i = 17 i = 23 i = 29 i = 35 i = 41 i = 47 i = 53 i = 59 i = 65 i = 71 i = 77 i = 83 i = 89 i = 95
PARI/GP

Код Выделить Развернуть

? for(i=10,99,if(3^i%7==5,print(i)))
11  17  23  29  35  41  47  53  59  65  71  77  83  89  95

[Hasim]

Спасибо за эксперименты.
Попробую подключить код на встроенном Питоне.

Хотя странно, почему алгоритм на Питоне вычисляет правильно, а алгоритм Калка ошибается?
Алгоритм Калка неудачный?

Вот как верить после этого вычислениям на Калке?

[greenman]

Хотя странно, почему алгоритм на Питоне вычисляет правильно, а алгоритм Калка ошибается?

Алгоритм тот же самый. У питона (2) тип long без ограничений по разрядности (ограничен, как я понимаю, объемом памяти).
В питоне 3 это относится к типу int.

А по поводу ограничений при вычислениях в электронных таблицах на forum.openoffice.org/en научная работа выложена - On the Numerical Accuracy of Spreadsheets из журнала Journal of Statistical Software.

This paper discusses the numerical precision of five spreadsheets (Calc, Excel, Gnumeric, NeoOffice and Oleo) running on two hardware platforms (i386 and amd64) and on three operating systems (Windows Vista, Ubuntu Intrepid and Mac OS Leopard).

[DixiX57]

Вот как верить после этого вычислениям на Калке?

А и не надо верить, представление чисел в памяти ЭВМ в большинстве случаев приближённое - в силу ограниченности разрядной сетки. Точно можно представить только некоторое ограниченное множество чисел, записываемых дробями с целочисленным числителем и знаменателем. Только это не используется в офисных пакетах.
Числа с плавающей запятой всегда представляются с ошибкой. Ещё возникает ошибки при вычислениях. Представление с фиксированной запятой вроде бы точное, но и тут имеется подвох. При умножении (сложении) может возникнуть переполнение. При делении часто происходит округление. поэтому, иногда, результат существенно зависит от последовательности операций.
В рассматриваемом случае большие числа CALC представляет с плавающей запятой, при этом в десятичном представлении получается не более 15 значащих цифр, - делайте выводы.

  И, да, "Кесарю-кесарево", для разных задач нужно подбирать соответствующие программы (или писать самому)

[greenman]

Почитал аналогичную дискуссию на ЛОР-е. Весьма поучительно.

Как я понял, вне конкуренции (за исключением может быть learning curve) для таких вычислений Haskell.