Алгоритм деления двух длинных чисел , Помогите, пожалуйста

Здравствуйте, очень нужна помощь знающих людей. У меня задание - написать программу деления 2 длинных чисел на Visual Studio Net(на языке C). Не могу понять, как выполнить деление. ПРочитал кучу инфы, но вопрос остается открытым. Я так понял, чтобы осуществить деление надо, чтобы 2 числа находились в массивах а дальше?
Буду очень признателен, если у кого-то есть готовый программный код иолил советы... Спасибо!

Ну ты напиши на листочке 2 числа и подели. и по аналогии делай...

Совет:
1.Юзать длинную математику
2.Описание алгоритма дано во 2 книге Д Кнута-Целочисленные вычисления
3.Если это очередная контрольная то исходных текстов не ждите тут -разбиритесь сами (вдруг препод смросит :
-а какого типа должны быть переменные хранящие длинные числа
4 У меня есть деления но я писал на VB(школьное деление)


Обозначим делитель B=(b0, b1, …, bn-1 ), делимое A=(a0, a1, …, an+m-1), числа имеют длины n и n+m
соответственно.
Общий цикл остается почти таким же: алгоритм состоит из последовательно выполняемых шагов,
где шаг представляет собой деление (n+1)-разрядной части A на n-разрядный делитель
B(исключение может составлять первый шаг, но это укладывается в общую схему, которая будет
обсуждаться ниже).
При этом i-й шаг состоит из двух действий:
1. Угадать i-ю цифру частного q[i]
2. Не создавая временных чисел, вычесть “сдвинутое” произведения B*q[i] из A.
При этом сдвиг B относительно A на каждом шаге уменьшается.
Рассмотрим действия, совершаемые при делении A=68971
на B=513. Здесь n=5, m=2
1. i = (индекс старшего коэффициента A) = 4
a. Угадываем q[0] = 1
b. Вычитаем сдвинутое B*1 = 513 из A
(на бумаге мы при этом пишем только
значимую для следующего шага часть A)
2. i = 3
a. Угадываем q[1] = 3
b. Вычитаем сдвинутое B*3 = 1539 из A
3. i = 2
a. Угадываем q[3] = 4
b. Вычитаем сдвинутое B*4 = 2052 из A
4. i < m = 2, процесс закончен. То, что осталось от A после вычитаний является остатком
деления.
Вроде бы, все очевидно, за исключением одного “творческого” шага – угадывания.
6 8 9 7 1
5 1 3
5 1 3
1 7 6 7
1 5 3 9
2 2 8 1
2 0 5 2
2 2 9
1 3 4
горизонтальные линии проводятся
между шагами
Как заставить компьютер генерировать правильное частное q ? Или, хотя бы, достаточно близкое к
нему число ?
Довольно интересный способ состоит в высказывании догадки qGuess по первым цифрам
делителя и делимого. Понятно, что этих нескольких цифр недостаточно для гарантированно
правильного результата, однако неплохое приближение все же получится.
Пусть очередной шаг представляет собой деление некоторого U = (u0, u1, …, un) на B=(b0, b1, …, bn-
1). Если bn-1 ≥ BASE/2, то можно доказать следующие факты1.
1. Если положить qGuess = (un*BASE + un-1) / bn-1 , то qGuess-2 ≤ q ≤ qGuess.
Иначе говоря, вычисленная таким способом “догадка” будет не меньше искомого частного,
но может быть больше на 1 или 2.
2. Если же дополнительно выполняется неравенство
qGuess*bn-2 > BASE*r + un-2 , где r – остаток при нахождении qGuess и qGuess ≠ BASE, (2)
то qGuess-1 ≤ q ≤ qGuess, причем вероятность события qGuess = q+1 приблизительно равна
2/BASE.
Таким образом, если bn-1 ≥ BASE/2, то можно вычислить qGuess = (un*BASE + un-1) / bn-1 и
уменьшать на единицу до тех пор, пока не станут выполняться условия (2). Получившееся
значение будет либо правильным частным q, либо, с вероятностью 2/BASE, на единицу большим
числом.
Что делать, если bn-1 слишком мало, чтобы пользоваться таким способом ?
Например, можно домножить делитель и делимое на одно и то же число scale = BASE / ( bn-1 +1 ).
При этом несколько изменится способ вычисления остатка, а частное останется прежним. Такое
домножение иногда называют нормализацией числа.
На тот случай, если qGuess получилось все же на единицу большим q, будем использовать в
пункте (b) вычитание, аналогичное функции Sub, которое вместо отрицательного числа даст
дополнение до следующей степени основания.
Если такое произошло, то последний перенос будет равен borrow = -1. Это сигнал, что необходимо
прибавить одно B назад. Заметим, что в конце сложения будет лишний перенос carry=1, о котором
нужно забыть (он компенсирует borrow=-1).
Например, делим A=505 на B=50. Угаданное частное qGuess=11.
505-550 = 955(=1000-45). Последний перенос borrow=-1, рельное частное q=qGuess-1=10.
Необходимо прибавить одно B: 955+50 = 5.
При сложении произошел перенос carry=1 из старшего разряда. Должно было получится 1005, но
об этом переносе “забыли”, так как он компенсировал borrow=-1.

// Q = A/B, R=A%B
void Div(const BigInt &A, BigInt &B, BigInt &Q, BigInt &R) {
// Вырожденный случай 1. Делитель больше делимого.
if ( A.Size < B.Size ) {
Q.zero();
R=A;
return;
}
// Вырожденный случай 2. Делитель – число базового типа.
if ( B.Size == 1) {
SDiv ( A, B.Coef[0], Q, R.Coef[0]);
R.Size = 1;
return;
}
1 Доказательства не очень сложны, и если они интересны – они присутствуют в книге Д. Кнута [3].
// Создать временный массив U, равный A
// Максимальный размер U на цифру больше A, с учетом
// возможного удлинения A при нормализации
BigInt U(A.Size+1); U = A; U.Coef[A.Size]=0;
// Указатели для быстрого доступа
short *b=B.Coef, *u=U.Coef, *q=Q.Coef;
long n=B.Size, m=U.Size-B.Size;
long uJ, vJ, i;
long temp1, temp2, temp;
short scale; // коэффициент нормализации
short qGuess, r; // догадка для частного и соответствующий остаток
short borrow, carry; // переносы
// Нормализация
scale = BASE / ( b[n-1] + 1 );
if (scale > 1) {
SMul (U, scale, U);
SMul (B, scale, B);
}
// Главный цикл шагов деления. Каждая итерация дает очередную цифру частного.
// vJ - текущий сдвиг B относительно U, используемый при вычитании,
// по совместительству - индекс очередной цифры частного.
// uJ – индекс текущей цифры U
for (vJ = m, uJ=n+vJ; vJ>=0; --vJ, --uJ) {
qGuess = (u[uJ]*BASE + u[uJ-1]) / b[n-1];
r = (u[uJ]*BASE + u[uJ-1]) % b[n-1];
// Пока не будут выполнены условия (2) уменьшать частное.
while ( r < BASE) {
temp2 = b[n-2]*qGuess;
temp1 = r*BASE + u[uJ-2];
if ( (temp2 > temp1) || (qGuess==BASE) ) {
// условия не выполнены, уменьшить qGuess
// и досчитать новый остаток
--qGuess;
r += b[n-1];
} else break;
}
// Теперь qGuess - правильное частное или на единицу больше q
// Вычесть делитель B, умноженный на qGuess из делимого U,
// начиная с позиции vJ+i
carry = 0; borrow = 0;
short *uShift = u + vJ;
// цикл по цифрам B
for (i=0; i<n;i++) {
// получить в temp цифру произведения B*qGuess
temp1 = b[i]*qGuess + carry;
carry = temp1 / BASE;
temp1 -= carry*BASE;
// Сразу же вычесть из U
temp2 = uShift[i] - temp1 + borrow;
if (temp2 < 0) {
uShift[i] = temp2 + BASE;
borrow = -1;
} else {
uShift[i] = temp2;
borrow = 0;
}
}
// возможно, умноженое на qGuess число B удлинилось.
// Если это так, то после умножения остался
// неиспользованный перенос carry. Вычесть и его тоже.
temp2 = uShift[i] - carry + borrow;
if (temp2 < 0) {
uShift[i] = temp2 + BASE;
borrow = -1;
} else {
uShift[i] = temp2;
borrow = 0;
}
// Прошло ли вычитание нормально ?
if (borrow == 0) { // Да, частное угадано правильно
q[vJ] = qGuess;
} else { // Нет, последний перенос при вычитании borrow = -1,
// значит, qGuess на единицу больше истинного частного
q[vJ] = qGuess-1;
// добавить одно, вычтенное сверх необходимого B к U
carry = 0;
for (i=0; i<n; i++) {
temp = uShift[i] + b[i] + carry;
if (temp >= BASE) {
uShift[i] = temp - BASE;
carry = 1;
} else {
uShift[i] = temp;
carry = 0;
}
}
uShift[i] = uShift[i] + carry - BASE;
}
// Обновим размер U, который после вычитания мог уменьшиться
i = U.Size-1;
while ( (i>0) && (u[i]==0) ) i--;
U.Size = i+1;
}
// Деление завершено !
// Размер частного равен m+1, но, возможно, первая цифра - ноль.
while ( (m>0) && (q[m]==0) ) m--;
Q.Size = m+1;
// Если происходило домножение на нормализующий множитель –
// разделить на него. То, что осталось от U – остаток.
if (scale > 1) {
short junk; // почему-то остаток junk всегда будет равен нулю…
SDiv ( B, scale, B, junk);
SDiv ( U, scale, R, junk);
} else R=U;
}

При делении числа длины n на число длины m производится Θ(n-m) проходов цикла, каждый из
которых делает несколько операций стоимостью Θ (m). Таким образом, общая оценка будет
квадратичной, как и у умножения: Θ (nm).

Сообщение отредактировано: Dethlord - 14.11.07, 21:51

в двоичную систему переводишь и делишь столбиком
1. выравниваешь делимое и делитель по старшему биту
2. вычитаешь из делимого делитель
3. если возникает перенос, т.е. делимое меньше, то оставлем его без изменений, -> п.5
4. результат пишешь в делимое, в частное + 1
5. сдвигаешь в право делитель, влево частное на 1 бит
6. делитель не изменился? -> п.2
7. теперь в делимом остаток, ставим запятую, если надо делим дальше до нужной точности

Dethlord спасибо, но не понял, что за код приведен, там не описаны используемые в нем функции.
tDCKWL хороший алгоритм, но чтобы мне его реализовать потребуется очень много времени, а его мало. Не мог бы написать на С? Буду оч. признателен.

я си не знаю тока асм

Ну тогда может подскажешь... смотри у меня 2 массива, в первом - делимое, во втором - делитель. В каждой ячейке массива по одной цифре. Как реализовать твой метод? Мы же не можем получить полнео число, чтобы потом его перевести в двоичную систему(оно же длинное)...

делай как на бумажке делишь. длину разряда выбирай произвольно, не важно, бит, байт, слово и т.п.

Я написал подробную схему в чем проблемма то?

Мы этому товарищу уже замучились объяснять как же надо делить
Деление двух длинных чисел

Dethlord
В конце твоего решения последний пункт, денормализация, это ты что делаешь, просто делишь значения в массиве на scale или там есть ещё какая-то магия известная только тебе?