 Регистрирайте се
Оптимизация за целочислено делене на Мифсъд от 1970 г.
|
| Предишната тема :: Следващата тема |
| Автор |
Съобщение |
SkylineGTR
Начинаещ
Регистриран на: 16 May 2008
Мнения: 2
  
|
 Пуснато на: Fri May 16, 2008 9:18 am Заглавие: Оптимизация за целочислено делене на Мифсъд от 1970 г. |
|
|
Става въпрос за алгоритъм, който така и не успях да открия. Използван е за създаването на нестандартна библиотека за операции с големи числа.
За тези които се занимават със C++, библиотеката се казва HugeInt:
http://sourcecore.net/article.php?id=38
Ще ви бъда много благодарен, ако ми дадете поне препратка към въпросния алгоритъм. |
|
| Върнете се в началото |
|
 |
Реклама
|
| Пуснато на: Заглавие: Реклама |
|
|
|
|
|
| Върнете се в началото |
|
|
Irrefutable
Напреднал
Регистриран на: 15 Jul 2007
Мнения: 298
Местожителство: София
гласове: 5
|
| Пуснато на: Fri May 16, 2008 12:12 pm Заглавие: |
|
|
Е като имаш кода, какво повече ти трябва 
| Код: | 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)
гласове: 179
|
| Пуснато на: Fri May 16, 2008 12:30 pm Заглавие: |
|
|
Публикуван е в:
Communications of the ACM
Volume 13 , Issue 11 (November 1970) |
|
| Върнете се в началото |
|
|
|
|
Не Можете да пускате нови теми
Не Можете да отговаряте на темите
Не Можете да променяте съобщенията си
Не Можете да изтривате съобщенията си
Не Можете да гласувате в анкети
You cannot attach files in this forum
Може да сваляте файлове от този форум
|
|
Меню
