Длинная арифметика

→ Обратите внимание

До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
25:44:34
Зарегистрироваться »

*есть доп. регистрация

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя ardmn

Длинная арифметика

Автор ardmn, 14 лет назад, По-русски

Уважаемые пользователи сайта , пожалуйста поделитесь хорошим классом Длинки(+,-,/,%,*). Свой писал но вроде медленный. Не получается модернизировать. Хорошим в смысле быстрой роботы .

Буду очень благодарен.

длинная арифметика, помощь

ardmn
14 лет назад
56

Комментарии (51)

Показать архивные | Написать комментарий?

cmd	14 лет назад, # \| ← Rev. 2 → 0 http://shygypsy.com/tools/ (BigInt.cpp) Если нужно более быстрое *, то можно это http://e-maxx.ru/algo/fft_multiply заюзать еще. P.S. а какой язык? =) → Ответить

ardmn

14 лет назад, # ^ |

тут по ходу основание системы 10. Если будет 1000000 вроде быстрее должно работать?

→ Ответить

AndreySiunov

14 лет назад, # ^ |

Для сложеня в 6 раз, для умножения в 36..

→ Ответить

hydrastuff

14 лет назад, # ^ |

мне кажется не совсем, ведь действия над числами по модулю 10 происходят быстрее чем по модулю 10^6

→ Ответить

ardmn

14 лет назад, # ^ |

это да но ведь не в 6 раз ? ... хотя времени на преобразование тратиться гораздо больше . Как вы думаете это существенно влияет на время работы и как лучше это реализовать?

→ Ответить

hydrastuff

14 лет назад, # ^ |

по модулю 10^4, при большей базе переполнения будут

→ Ответить

ardmn

14 лет назад, # ^ |

откуда переполнения ? если использовать long long 999999*999999 -не будет переполнения :)

или я вас не понял?

→ Ответить

riadwaw

14 лет назад, # ^ |

если long long - тогда да, можно до 10^9

а вот из инта 10^5 уже вылазит

→ Ответить

ardmn

14 лет назад, # ^ |

это если unsigned?

и есть ли в этом смысл ? я так и не понял :)

→ Ответить

riadwaw

14 лет назад, # ^ |

unsigned, очевидно тоже вылазит

→ Ответить

Urbanowicz

14 лет назад, # ^ |

long long использовать можно, но в нем операция взятия по модулю работает феерически медленно.

→ Ответить

gerasimovd

14 лет назад, # ^ |

То есть лучше использовать int и базу 10^4 чем long long и базу 10^9?

→ Ответить

Urbanowicz

14 лет назад, # ^ |

Скорее всего. Не проверял на самом деле.

→ Ответить

ardmn

14 лет назад, # |

Я обычно юзаю JAVA для этого но бывает мозгов не хватает написать быстрое решение и приходится кодить на С++.По этому хочу у опытных опросить проверенный временем class :)

→ Ответить

caustique

14 лет назад, # ^ |

Да где ж ты такие задачи встречал, что BigInteger не проходит, а тупое решение с самодельной сишной длинной арифметикой проходит?

→ Ответить

Urbanowicz

14 лет назад, # ^ |

Задача «A²+...+B²» с последнего гран-при Удмуртии с Опенкапа. Там такие большие числа, что BigInteger не успевает преобразовать их в двоичную систему счисления. Если реализовать свою арифметику, которая пользуется десятичным основанием для внутреннего представления, то все будет ок. Правда эта задача и без длины нормально решается.

→ Ответить

ardmn

14 лет назад, # ^ |

а можно поподробнее ? что за задача и её решение без длинки :)

→ Ответить

Urbanowicz

14 лет назад, # ^ |

Ссылка на условия (задача I):

http://opencup.ru/files/oc8/gp3/problems1.pdf

→ Ответить

ardmn

14 лет назад, # ^ |

как её решать?

→ Ответить

Urbanowicz

14 лет назад, # ^ |

+13

На контесте ее решили 78 команд из 140. Не надо думать о себе так плохо.

→ Ответить

ivan.popelyshev

14 лет назад, # ^ |

Надо было использовать BigDecimal ;)

→ Ответить

Urbanowicz

14 лет назад, # ^ |

Вы так сдали?

→ Ответить

JKeeJ1e30

14 лет назад, # ^ |

Нам рассказывали на лекциях что для C_n^kлучше как раз написать свой собственный класс чем в явку загонять. Даже если считаешь умнее чем делением одного факториала на два других.

→ Ответить

dyussenaliyev

14 лет назад, # |

http://e-maxx.ru/algo/big_integer

→ Ответить

goo.gl_SsAhv

14 лет назад, # |

http://www.everfall.com/paste/id.php?fhelgcbkw1cf

вот весьма эффективная длинка, битовый подход, основание 2^32

многое можно соптимизировать, но это я писал давно и небыло цели особо извращатся.

реализация деления за n^2 * log(base) = n^2 * 32, можно за n^2 реализовать по кнуту, по моим тестам

в 6 или 12 раз быстрее если цифру брать за 8 или 16 бит соответственно

→ Ответить

gerasimovd

14 лет назад, # ^ |

А что за реализация деления за n^2?

→ Ответить

Zlobober

14 лет назад, # ^ |

Можно вообще с помощью БПФ сделать за nlogn.

→ Ответить

CherryTree

14 лет назад, # |

← Rev. 2 →

Вот вроде-бы одна из самых быстрых библиотек длинки для с++ но не знаю насколько она применима на контестах.

→ Ответить

it4.kp

14 лет назад, # ^ |

Ну а вы попробуйте ее применить и узнаете.

→ Ответить

ardmn

14 лет назад, # ^ |

Я тоже не знаю и по этому просил проверенную вещь :) но спасибо ;)

→ Ответить

Salat

14 лет назад, # |

← Rev. 2 →

http://sites.google.com/site/indy256/algo_cpp/bigint

со встроенной karatsubaMultiply.

→ Ответить

ardmn

14 лет назад, # ^ |

← Rev. 2 →

тут через вектор :) не плохо но как я заметил , даже не знаю почему но по ходу вектор дольше работает чем обычный массив ... (кстати интересно почему? если это правдатак )

→ Ответить

Salat

14 лет назад, # ^ |

← Rev. 3 →

Может быть если не делать много push_back'ов, а выделить сразу памяти сколько надо через resize, то вектор будет работать также быстро как и обычный массив.

Хотя я хз, сам бы хотел узнать где вектор и в чем проигрывает, если проигрывает.

→ Ответить

JKeeJ1e30

14 лет назад, # ^ |

Есть догадка что при push_back'ах создается еще один вектор на 1 элемент больше, ну и дальше там идет переадресация. Просто кто-то мне рассказал что на операцию push_back() вектор тратит в два раза больше памяти чем нужно. Этот человек так же рассказал что на операцию pop_back() вектор тратит в 4 раза больше чем нужно(интересно, почему). Но если действительно все делать через resize() то время экономится.

→ Ответить

Urbanowicz

14 лет назад, # ^ |

← Rev. 2 →

push_back работает так: если выделенной памяти не хватает для очередного элемента, то создается новый вектор в два раза большего размера, куда копируется содержимое старого. Такое удвоение позволяет работать пуш-бэку за амортизированную константу.

→ Ответить

907th

14 лет назад, # ^ |

Действительно похоже, но в вашем утверждении ".. в два раза большего размера .." не уверен на 100%

→ Ответить

Urbanowicz

14 лет назад, # ^ |

Это легко проверить:

#include <stdio.h>

#include <vector>

std::vector < int > v;

int main() {

for (int i = 0; i < 100; i++) {

printf("Size and Capacity before push back: %d %d\n", v.size(), v.capacity());

v.push_back(1);

printf("Size and Capacity after push back: %d %d\n", v.size(), v.capacity());

}

return 0;

}

→ Ответить

fetetriste

14 лет назад, # ^ |

Не в два, а в φ ≈ 1.618

→ Ответить

Urbanowicz

14 лет назад, # ^ |

Судя по работе программы, которая написана выше, capacity всегда увеличивается ровно в два раза. Может у вас реализация STL другая.

→ Ответить

primorial

14 лет назад, # ^ |

← Rev. 2 →

~~Если не ошибаюсь, это всё ваша студия шалит.~~

Ошибаюсь: в gcc аналогичный результат. Однако, fetertriste по сути прав. ~1.5 - более кошерное значение для памяти и используется в некоторых реализациях.

→ Ответить

Urbanowicz

14 лет назад, # ^ |

gcc version 4.2.1 (Apple Inc. build 5666) (dot 3)

Какая нафиг студия?)

Кстати, что это программа у вас выводит, если не секрет?

→ Ответить

primorial

14 лет назад, # ^ |

Проверил на gcc и исправился выше.

→ Ответить

fetetriste

14 лет назад, # ^ |

Да, от реализации зависит, конечно. Важно, чтобы было ≤ φ

Вот, а оттуда по ссылкам

→ Ответить

gerasimovd

14 лет назад, # ^ |

Про расширение уже написали.

Про pop_back в 4 раза больше - если количество элементов в векторе <= capacity/4 - вектор сужают в 2 раза.

Вообще это классическая реализация саморасширяющегося - самосужающегося массива.

→ Ответить

I_love_natalia

14 лет назад, # |

Оптимизация ДА зависит от конкретного случая
Можно сделать крайне быструю длинку со следующими эвристиками:
1. использовать 10^k как основание системы счисления, если результат нужен десятичный.
2. использовать кэширование при умножении на короткое.
и т.п.

→ Ответить

g.naukovych

14 лет назад, # |

В Харькове на сборах рассказывался алгоритм Карацубы и Быстрое преобразование Фурье. Эти алгоритмы выполняют умножение за NlogN. При этом как я понял БПФ лучше работает с базой 10, а не 10^9.

В случае если необходимо реализовать операцию сложения, то стоит избавляться от долгой операции %. Были задачи, когда эта оптимизация спасает.

Аналогичный случай с умножением за N^2. Необходимо избавиться от %. Дмитрий Жуков говорил, что подобная оптимизация может помочь, даже в том случа если на первый взгляд решение пройти не может.

→ Ответить

gerasimovd

14 лет назад, # ^ |

← Rev. 2 →

Карацуба разве не за O(n^1.6)?

В БПФ с базой 10^9 происходят на больших числах(1000 знаков) какие-то странные то ли переполнения, то ли потери точности. Факт в том что несколько(штук 8-10) последних знаков наверняка неправильна. Не знаю, я где-то лажал или еще что, но если ставить основание поменьше(10^4 , например) - то все ок.

→ Ответить

g.naukovych

14 лет назад, # ^ |

Как я понял БПФ чем меньше база тем лучше. Карацуба, если я не ошибаюсь, Nlog_1.5N

→ Ответить

hydrastuff

14 лет назад, # ^ |

Вообще исходная задача размерности N, делится на три задачи размерности в N/2 и они объединяются за N действий, сложность N^log2(3)

→ Ответить