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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 4.71
boomeer
0 / 0 / 0
Регистрация: 30.10.2010
Сообщений: 8
13.01.2011, 17:18     Быстрое деление 2х длинных #1
Предположим у меня есть вектор 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х длинных
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
vx5
 Аватар для vx5
187 / 171 / 4
Регистрация: 04.09.2010
Сообщений: 656
13.01.2011, 17:24     Быстрое деление 2х длинных #2
C++
1
long long
это что за тип такой? неужели 16 байт ?
boomeer
0 / 0 / 0
Регистрация: 30.10.2010
Сообщений: 8
13.01.2011, 17:38  [ТС]     Быстрое деление 2х длинных #3
Цитата Сообщение от vx5 Посмотреть сообщение
C++
1
long long
это что за тип такой? неужели 16 байт ?
8 байт
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9383 / 5433 / 916
Регистрация: 25.07.2009
Сообщений: 10,428
13.01.2011, 17:39     Быстрое деление 2х длинных #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  [ТС]     Быстрое деление 2х длинных #6
Тут 100% ответов не по теме... А хотелось бы именно по ней
boomeer
0 / 0 / 0
Регистрация: 30.10.2010
Сообщений: 8
14.01.2011, 20:15  [ТС]     Быстрое деление 2х длинных #7
Вверх! Актуально!
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.02.2011, 20:36     Быстрое деление 2х длинных
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
1337_|-|4}{0r
Сообщений: n/a
02.02.2011, 20:36     Быстрое деление 2х длинных #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))

Только вот реальный выигрыш ты на таких значениях не получишь.
Yandex
Объявления
02.02.2011, 20:36     Быстрое деление 2х длинных
Ответ Создать тему
Опции темы

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