ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Yuriy Kaminskiy                      2:5020/517.21  08 May 2001  17:14:32
 To : Aleksey Malov
 Subject : Re: ОК
 -------------------------------------------------------------------------------- 
 

  Hello,  Aleksey! 
 
 >>>>> On 11:11 07/5/2001, Aleksey Malov <2:5052/30.8> writes:
  AM>   Можно HОД вообще без деления найти:
  AM> int nod (int A, int B) { while (A!=B) { if (A>B) A -= B else B -=
  AM> A; } return A; }
 
  Это полностью эквивалентно варианту, использующему деление, только еще
 более медленно (фактически, тут операция деления выполняется вручную -
 что, очевидно, гораздо медленнее зашитого в железо алгоритма).
  Если деление слишком долгая операция, то более осмысленно посмотреть
 на алгоритм бинарного вычисления gcd (приведен у Кнута, т. 2).
 -- 
 Yuriy Kaminskiy.
 PS /* Внимание! Тут подразумевается, что integer_t - ЗHАКОВЫЙ тип */
 integer_t binary_gcd(integer_t u, integer_t v)
 {
     scale_t shift;
     integer_t t;
     assert( u && v );
     for(shift = 0; !(u&1) && !(v&1); shift++, u /= 2, v /= 2)
         ;
     if(u&1) {
         t = -v;
   /* Да. goto - дурной тон; но если уж кому-то придет в голову
            использовать этот алгоритм, то для него скорость работы
            всяко важнее понятности кода :) */
         goto step4;
     } else
         t = u;
     do {
         do {
             t /= 2;
 step4:  
         } while(!(t&1));
         if(t > 0)                                              
             u = t;                                             
         else                                                   
             v = -t;                                            
         t = u-v;                                               
     } while(t);                                                
     return u<<shift;                                           
 }
 --- Gnus v5.2.25/XEmacs 19.14
  * Origin: none (2:5020/517.21@fidonet)
 
 

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

Тема:    Автор:    Дата:    НОК   Denes Raskovalov   06 May 2001 01:01:25   НОК   Aleksey Malov   07 May 2001 12:11:03   Re: ОК   Yuriy Kaminskiy   08 May 2001 17:14:32   НОК   Denes Raskovalov   08 May 2001 04:48:35   НОК   Aleksey Malov   12 May 2001 15:58:59