Регистрирайте сеРегистрирайте се

Оптимизация за целочислено делене на Мифсъд от 1970 г.


 
   Форум за математика Форуми -> Kомпютърни изчисления
Предишната тема :: Следващата тема  
Автор Съобщение
SkylineGTR
Начинаещ


Регистриран на: 16 May 2008
Мнения: 2

Репутация: 3.2Репутация: 3.2Репутация: 3.2

МнениеПуснато на: Fri May 16, 2008 9:18 am    Заглавие: Оптимизация за целочислено делене на Мифсъд от 1970 г.

Става въпрос за алгоритъм, който така и не успях да открия. Използван е за създаването на нестандартна библиотека за операции с големи числа.

За тези които се занимават със C++, библиотеката се казва HugeInt:
http://sourcecore.net/article.php?id=38

Ще ви бъда много благодарен, ако ми дадете поне препратка към въпросния алгоритъм.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Реклама







Пуснато на:     Заглавие: Реклама

Върнете се в началото
Irrefutable
Напреднал


Регистриран на: 15 Jul 2007
Мнения: 298
Местожителство: София
Репутация: 28.8Репутация: 28.8Репутация: 28.8
гласове: 5

МнениеПуснато на: Fri May 16, 2008 12:12 pm    Заглавие:

Е като имаш кода, какво повече ти трябва Smile
Код:
void HugeInt::divide(HugeInt denom, HugeInt& quot, HugeInt& rem, bool want_rem) const

   if(denom.m_llen == 0) {
      cerr << "Division by zero!\n";
      terminate();
   }

   bool QuotNeg = (m_neg != denom.m_neg), RemNeg = m_neg;
   
   int r, n;
   
   uint q, d;
   
   HugeInt num = *this;
   num.m_neg = denom.m_neg = 0;

   if(num < denom) { 
      quot = 0;
      rem = num;
      rem.m_neg = RemNeg;
      return;
   }


   if(denom.m_llen == 1 && num.m_llen == 1) { 
      quot = uint(num.m_pDig[0]/denom.m_pDig[0]);
      rem = uint(num.m_pDig[0]%denom.m_pDig[0]);
      quot.m_neg = QuotNeg;
      rem.m_neg = RemNeg;
      return;
   } 
   else if(denom.m_llen == 1 && (denom.m_pDig[0] & LMASK) == 0) {  // Denominator fits into a half word

      uint divisor = denom.m_pDig[0], dHi = 0, q1, r, q2, dividend;

      quot.set_len(m_llen);
      for(int i=m_llen-1; i>=0; --i) { 
         dividend = (dHi << HLEN) | (m_pDig[i] >> HLEN);
         q1 = dividend/divisor;
         r = dividend % divisor;
         dividend = (r << HLEN) | (m_pDig[i] & RMASK);
         q2 = dividend/divisor;
         dHi = dividend % divisor;
         quot.m_pDig[i] = (q1 << HLEN) | q2;
      }
      quot.reduce();
      rem = dHi;
      quot.m_neg = QuotNeg;
      rem.m_neg = RemNeg;
      return;
   }

   HugeInt num0 = num, denom0 = denom;
   int x=0;
   bool SecondDone = normalize(denom, num, x);
   r = denom.m_llen - 1;
   n = num.m_llen - 1;
   quot.set_len(n - r);

   for(int i=quot.m_llen-1; i>=0; i--)
      quot.m_pDig[i] = 0;

   rem = num;
   if(rem.m_pDig[n] >= denom.m_pDig[r]) {
      rem.incr_len(rem.m_llen + 1);
      ++n;
      quot.incr_len(quot.m_llen + 1);
   }
   
   d = denom.m_pDig[r];
   for(int k=n; k>r; k--) { 
      q = dd_quotient(rem.m_pDig[k], rem.m_pDig[k-1], d);
      substract_mul(rem.m_pDig + k - r - 1, denom.m_pDig, r + 1, q);
      quot.m_pDig[k - r - 1] = q;
   }

   quot.reduce();
   quot.m_neg = QuotNeg;

   if(want_rem) { 
      unnormalize(rem, x, SecondDone);
      rem.m_neg = RemNeg;
   }
}

Това като го гледам е някакъв "multiple-precision division" алгоритъм, има няколко такива, и можеш да потърсиш и други.
Като цяло тази библиотечка ми се вижда бая бавна. Автора е писал че може лесно да я пригоди за плаваща запетая, заради pow и sqrt, но реализацията му е с голяма сложност. Всъщност ползва шифтинг който му отнема О(N) време , където N е броя битове на числото в съответната бройна система. Дълеч по-добре за плаваща запетая е мантисата да е реализирана с двустранна опашка. А още по-добре с кръгал масив с директна индексация. Където шифтовете са О(1)
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение Посетете сайта на потребителя
r2d2
VIP


Регистриран на: 28 Feb 2007
Мнения: 1936
Местожителство: in the galaxy (Far Far Away)
Репутация: 311.2Репутация: 311.2
гласове: 179

МнениеПуснато на: Fri May 16, 2008 12:30 pm    Заглавие:

Публикуван е в:
Communications of the ACM
Volume 13 , Issue 11 (November 1970)
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Покажи мнения от преди:   
   Форум за математика Форуми -> Kомпютърни изчисления Часовете са според зоната GMT + 2 Часа
Страница 1 от 1

 
Идете на:  
Не Можете да пускате нови теми
Не Можете да отговаряте на темите
Не Можете да променяте съобщенията си
Не Можете да изтривате съобщенията си
Не Можете да гласувате в анкети
You cannot attach files in this forum
Може да сваляте файлове от този форум
Copyright © 2005-2021 math10.com.