Re: 2^500

From

Sergey Andrianov (2:5020/1507.400)

To

Vladislav Terehov

Date

2002-09-19T09:00:06Z

Area

RU.ALGORITHMS

Здравствуй, Vladislav!

Однажды 17-Sep-02  в 18:15   Vladislav Terehov (2:5030/1307.25)
написал       All    по поводу
-=-   2^500  -=-

VT> Самый быстpый/самый компкактный (в плане пожиpания pесуpсов) алгоpитм, для 
VT> поэтапного вычисления и печати кусков сабжевого выpажения (2 в 500й 
VT> степени) на экpане в десятеpичной системе счисления кто подскажет?

	Думаю, что "вычисление" здеесь излишне. Нужно просто перевести известное число (надеюсь понятно, почему 2^500 в двоичной системе вычислять не нужно) из одной системы счисления (двоичной, восьмеричной или шестнадцатиричной) в десятичную. 
	Для этого нужна процедура, умеющая находить частное и остаток двух длинных чисел. Т.к. процедура неизбежно получится ресурсоемкой, то, чтобы сократить объем вычислений я бы попытался применить реукурсивный алгоритм с делением числа примерно на корень из него, а затем по тому же алгоритму обрабатывать частное и остаток.
	То есть найти степень 10 примерно равную 2^250 и поделить на нее, затем частное и остаток на прмерно 10^125, и т.д.

                  До свидания,  в  08:51 MSK
                                 Sergey

---
 * Origin: Sergiev Posad (2:5020/1507.400)