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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 4.71
boomeer
0 / 0 / 0
Регистрация: 30.10.2010
Сообщений: 8
#1

Быстрое деление 2х длинных - C++

13.01.2011, 17:18. Просмотров 1824. Ответов 7
Метки нет (Все метки)

Предположим у меня есть вектор a и вектор b. Каждый элемент вектора содержит 9 цифр (основание миллиард). Дак вот вопросец, как поделить a на b оптимальным способом.
Деление длинного на короткое реализовал

C++
1
2
3
4
5
6
7
carry = 0;
    for (int i=(int)a.size()-1; i>=0; --i) { 
        long long cur = a[i] + carry * 1ll * base;
        a[i] = int (cur / (n));
        carry = int (cur % (n));
    }
    while (a.size() > 1 && a.back() == 0) a.pop_back();
Прошу помочь с делением 2х длинных
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.01.2011, 17:18
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Быстрое деление 2х длинных (C++):

Быстрое умножение длинных чисел. - C++
В общем вопрос стоит так: где можно найти красивый код на агоритм Карацубы. В часности -...

Деление длинных чисел - C++
Код который делит очень длинное число на обычное число. Если вводить 121 и 2 выводит неправильный ответ. Какие условия надо поставить...

Деление длинных чисел столбиком - C++
Привет. У меня возникла проблема при написании курсовой. Необходимо реализовать деление двух больших чисел(записанных "зеркально"). Хотя я...

Деление длинных чисел нацело - C++
Возникла проблема. Завтра сдавать курсовик (арифметика длинных чисел), а у меня не готово деление, так как не знаю, как сделать. Курсовик...

Умножение/деление длинных целых чисел из строк - C++
у кого есть код 'умножение и деление целых чисел из строк'? заранее спасибо Добавлено через 32 минуты или библиотека и функции

Сделать сложение, вычитание, умножение и деление длинных чисел - C++
В общем, задача такая, что надо сделать сложение, вычитание, умножение и деление длинных чисел. Сумму сделал, с вычитанием какая-то засада....

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
vx5
187 / 171 / 4
Регистрация: 04.09.2010
Сообщений: 656
13.01.2011, 17:24 #2
C++
1
long long
это что за тип такой? неужели 16 байт ?
boomeer
0 / 0 / 0
Регистрация: 30.10.2010
Сообщений: 8
13.01.2011, 17:38  [ТС] #3
Цитата Сообщение от vx5 Посмотреть сообщение
C++
1
long long
это что за тип такой? неужели 16 байт ?
8 байт
easybudda
Модератор
Эксперт CЭксперт С++
9530 / 5523 / 932
Регистрация: 25.07.2009
Сообщений: 10,608
13.01.2011, 17:39 #4
Цитата Сообщение от vx5 Посмотреть сообщение
это что за тип такой? неужели 16 байт ?
Не, 8. В stdint.h его псевдоним объявлен так
C
1
typedef long long            int64_t;
В мелкомягком варианте
__int64
vx5
13.01.2011, 17:50
  #5

Не по теме:

я уже проверил с помощью sizeof получается просто одиночный long дублирует int ?

boomeer
0 / 0 / 0
Регистрация: 30.10.2010
Сообщений: 8
13.01.2011, 20:13  [ТС] #6
Тут 100% ответов не по теме... А хотелось бы именно по ней
boomeer
0 / 0 / 0
Регистрация: 30.10.2010
Сообщений: 8
14.01.2011, 20:15  [ТС] #7
Вверх! Актуально!
1337_|-|4}{0r
Сообщений: n/a
02.02.2011, 20:36 #8
http://ru.wikipedia.org/wiki/БПФ
http://informatics.mccme.ru/moodle/m...iew.php?id=878

1. Представить числа как полиномы от одной переменной, (121 = X^2 + 2x + 1,x = 10).
2. Посчитать фурье-образы.
3. Поэлементно делим коэф-ты с одинаковыми индексами
4. Обратное преобразование.

Все это работает только если ты точно знаешь, что они какбе разделятся.

Для уверенности еще алгоритм Евклида в помощь.

На все - про все - nlogn операций ( n - в твоем случае sizeof(long long))

Только вот реальный выигрыш ты на таких значениях не получишь.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.02.2011, 20:36
Привет! Вот еще темы с ответами:

Сложение/деление двух длинных чисел (длиной 1024 бита) - C++
Всем привет! Есть две вот такие задачи: 1. используя вставку кода в программу на С++, составить программу для сложения 2-х длинных...

Задача про деление яблок (целочисленное деление) - C++
Ребят,помогите с задачкой,как написать input.txt и output.txt? Помогите решить задачу. C++. Заранее спасибо! N школьников делят K яблок...

Быстрое шифрование - C++
Народ добрый , день , такая задача решил делать курсач на тему криптография , вот первым делом буду использовать шифрование быстрым методом...

Быстрое изучение С++ - C++
Си знаю, C# знаю. На все про все у меня неделя. Что посоветуете? Заранее благодарен.


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
02.02.2011, 20:36
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru