ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Alexandr A. Redchuck                 2:5020/400     24 Sep 2002  09:27:38
 To : Sergey Andrianov
 Subject : Re: 2^500
 -------------------------------------------------------------------------------- 
 

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

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор