Re: 2^500

From

Alexandr A. Redchuck ()

To

Sergey Andrianov

Date

2002-09-24T09:27:38Z

Area

RU.ALGORITHMS

From: "Alexandr A. Redchuck" <real@real.kiev.ua>

19-Sep-02 08:00 Sergey Andrianov wrote to Vladislav Terehov:

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

SA>     Думаю, что "вычисление" здеесь излишне. Нужно просто перевести
SA> известное число
SA> (надеюсь понятно, почему 2^500 в двоичной системе вычислять не нужно) из
SA> одной
SA> системы счисления (двоичной, восьмеричной или шестнадцатиричной) в
SA> десятичную.
 Не могу не согласиться.

SA>     Для этого нужна процедура, умеющая находить частное и остаток двух
SA> длинных чисел.
 А это считаю абсолютно избыточным. Одно дело пользоваться для
преобразования /% при аппаратном делении нужной разрядности, а другое -
при программной реализации.
 В данном случае гораздо экономичнее вместо деления многозначных чисел
выполнять их умножение на 2 :-) Только что набросал, просьба не пинать за
вечерние корявости :-) (при небольшой доработке это дело сможет переводить
из двоичной формы в ascii числа произвольной длины).

int main( int ac, char **av) {
  int   p2 = 500;
  int   digits;
  char *string;
  int   i,j;

  if( ac >= 2 ) sscanf( av[1], "%d", &p2);
  if( p2<0 ) return 2;

  digits = (int)ceil(p2*log(2)/log(10));
  if( !digits) digits=1;
  string = (char*)malloc( digits+1);
  if( !string) {
     puts( "мало памяти");
     return 1;
  }
  // В массиве string[] одна десятичная цифра в байте
  // Если бы писать на асме, то можно было бы в одном байте держать
  // две двоично-десятичных цифры и ниже вместо if( .. >=10)
  // использовать команду двоично-десятичной коррекции после сложения,
  // было бы крепко быстрее

  memset( string, 0, digits+1); // заодно и концевой '\0'
  string[digits-1] = 1;         // 2^0
  j = p2; // p2 раз умножаем число в string[] на 2
  while( j--) {
     int carry=0;
     i=digits;
   // место для "небольшой доработки":
   // если бы переводили в десятичную форму не 2^p2, а произвольное число,
   // то тут надо было бы сделать сдвиг влево всего двоичного числа
   // и в carry выдвинуть старший его бит (т.е. возможный перенос 0 или 1)
     while( --i>=0) {
        string[i] = 2*string[i]+carry;
        carry = 0;
        if( string[i] >= 10 ) {
           carry = 1; // больше не бывает при умножении 1-значного
                      // десятичного числа на 2 при предыдущем переносе
                      // максимум 1.
           string[i] -= 10;
        }
     }
  }

  i=digits;
  while( --i >= 0) {  // переводим в ASCII наглым непортабельным образом.
     string[i]+='0';
  }

  printf( "2^%d=\n%s\n", p2, string);
  return 0;
}


wbr,
--
/* Alexandr Redchuck, Kyiv, Ukraine */
/* real на real тчк kiev тчк ua     */

--- ifmail v.2.15dev5
 * Origin: ReAl at home (2:5020/400)