Форум программистов, компьютерный форум CyberForum.ru

Кнут - деление длинных чисел - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.82
Shandr_71
13 / 13 / 1
Регистрация: 05.12.2011
Сообщений: 84
01.05.2012, 16:03     Кнут - деление длинных чисел #1
Нужна помощь в переводе алгоритма деления длинных чисел из книги:
Д. Э. Кнут - Искусство Программирование Том 2 Получисленные Алгоритмы.
Особенно интересен третий шаг, я никак не могу понять, что там имеется в виду.

Мой код 4го шага:
C++
1
2
3
4
5
6
7
int q((static_cast<int>(num[j+n])*255+static_cast<int>(num[j+n-1]))/v[n-1]);
int r((static_cast<int>(num[j+n])*255+static_cast<int>(num[j+n-1]))%v[n-1]);
while(q!=255 || (q*static_cast<int>(v[n-2])<=255*r+static_cast<int>(num[j+n-2])))
    {
        q--;
        r+=static_cast<int>(v[n-1]);
    }
num соответствует переменной u из книги, v - v, n и m те же.
Числа предствлены в виде std::vector<unsigned char>, младший разряд соответствует нулевому элементу.

Добавлено через 6 часов 3 минуты
Вопрос все еще актуален.

Добавлено через 16 часов 53 минуты
Проблема решена:
C++
1
2
3
4
5
6
7
8
9
10
int q((static_cast<int>(u[j+n])*255+static_cast<int>(u[j+n-1]))/v[n-1]);
    int r((static_cast<int>(u[j+n])*255+static_cast<int>(u[j+n-1]))%v[n-1]);
 
    if(q==ds_int || (q*static_cast<int>(v[n-2])>ds_int*r+static_cast<int>(u[j+n-2])))
    {
        q--;
        r+=static_cast<int>(v[n-1]);
        if(q*static_cast<int>(v[n-2])>ds_int*r+static_cast<int>(u[j+n-2]) && r<ds_int)
            q--;
    }
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.05.2012, 16:03     Кнут - деление длинных чисел
Посмотрите здесь:

Быстрое деление 2х длинных C++
C++ Деление длинных чисел нацело
Умножение длинных чисел C++
C++ Умножение длинных чисел
C++ Сравнение длинных чисел >, <
Сложение/деление двух длинных чисел (длиной 1024 бита) C++
Деление длинных чисел столбиком C++
Сложение длинных чисел C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 15:44. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru