Den Raskovalov
29.04.2004 23:03
Возникла у меня необходимость реализовать RSA ;) Неожиданно поймал себя на мысли, что толком не умею писать деление длинного числа на длинное. Непорядок. В качестве отправной точки написал бинарный поиск :wink: Ничего, работает 8) Почитал что-то в и-нете. То, что я смог найти и понять, весьма криво. Поэтому предлагаю обсудить, кто как пишет это самое деление? ;) В качестве представление длинный чисел предлагаю представление по основанию, скажем, 2^15 ;)
PPS Вообще у меня готов неплохой классик CBigInteger (все кроме деления в нем классно ;), если кому интересно, могу выслать. Если интересно многим, можно запостить в форум, обсудить. Я за OpenSource ;)
CBigInteger& operator/=(const CBigInteger& value)PS Сейчас Кнута с полки возьму. Редчайший случай :lol:
{
if ( (m_sign == bisPositive) && (value.m_sign == bisPositive) )
{
if (value != Zero())
{
CBigInteger l = 0;
CBigInteger r = *this;
while (r - l > One())
{
CBigInteger mid = (l + r).SDiv(2);
if (mid*value <= *this)
l = mid;
else
r = mid;
}
while (l*value <= *this)
++l;
--l;
*this = l;
}
else
throw CAuxException("CBigInteger::operator/= Деление на 0");
}
else
{
*this = Abs() / value.Abs();
if (m_sign == value.m_sign)
m_sign = bisPositive;
else
m_sign = bisNegative;
}
return *this;
}
PPS Вообще у меня готов неплохой классик CBigInteger (все кроме деления в нем классно ;), если кому интересно, могу выслать. Если интересно многим, можно запостить в форум, обсудить. Я за OpenSource ;)