| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Быстрое считывание больших чисел |
| Автор: xni 20.2.2008, 11:32 |
| Доброе время суток! Ситуация такова: имеется 2 больших целых числа (порядка 10^100000). Необходимо их считать из стандартного ввода и разделить одно на другое, грубо говоря. Причём сделать это нужно как можно быстрее. (Стандартные средства ни одного из допустимых языков программирования не удовлетворяют временным ограничениям). Для решения задачи, соответственно, имеется длинная арифметика (по Кнуту). Основание системы счисления, видимо, стоит принять наибольшее из возможных (чтобы уменьшить количество байт для представления чисел) -- то есть 65536. Далее алгоритм должет считать в мой массив сами эти числа со стандартного ввода. Причём считывание по схеме Горнера, как я понимаю, не подходит. Необходимо двигаться с конца числа, брать очередной символ, умножать на 10^(n-i-1), прибавлять, при превышении 65536 брать остаток по модулю, сохранять, разность перебрасывать в новый разряд и всё такое прочее. Но мне кажется это тоже довольно медленно. Возникло предложение сгенерировать std::map< string , int > для строкового представления чисел от 0 до 9999. Например a["0"]=0; a["1"]=1; ... А за основание системы счисления взять 10000. Будьте добры, подскажите пожалуйста, как эффективно считать большие целые числа? |
| Автор: maxim1000 20.2.2008, 11:39 | ||
"по схеме Горнера" имеется в виду такое:
? если да, то почему не подходит? |
| Автор: ivashkanet 20.2.2008, 12:01 | ||
Замечание дилетанта:
А зачем присутствует переход в десятичную систему счисления? Так как "основание большого числа" у тебя 65536 то логично использовать шестнадцетиричную СС. Правда я не нашел по инету алгоритмов деления чисел не 10-й СС... Зато нашел такую тему: http://forum.sources.ru/index.php?showtopic=140509 (второе, ИМХО, то что тебе нужно) Удачи ;-) |
| Автор: maxim1000 20.2.2008, 13:33 | ||
насколько я понял, для пользователя - чтобы ему было удобнее вводить число в 10-й системе |
| Автор: ivashkanet 20.2.2008, 15:07 | ||
Ага,... что-то я об этом не подумал  В любом случае, ИМХО, удобнее либо использовать основание 10000, либо переводить в двоичную и использовать основание 2^32=65536. А вообще есть алгоритмы деления в N-ричной СС? |
| Автор: maxim1000 20.2.2008, 17:05 | ||
а какая разница? единственное удобство есть у двоичной системы: там для прибавления числа, умноженную на цифру (кусочек алгоритма деления) достаточно проверить значение цифры и либо добавить, либо ничего не делать |
| Автор: SoWa 20.2.2008, 18:28 |
| 65536ричная система счисления. Человек хочет использовать для уменьшения числа байт, используемых в программе. Может я чего не понимаю, но в байт мы можем запихать 256 значений, но никак не 65536. На бумаге такая система возможно подойдет: 1,2,...0,а,б,в...,a,b,c...%,^,&,кружочек, рожица и прочее. ИМХО в компьютере как ни крути но кол-во байт при переходе к такой системе сильно уменьшит не получится. Или совсем не получится. Или я чего-то не знаю |
| Автор: ivashkanet 20.2.2008, 18:39 | ||||
Взял в руки карандаш и бумагу... действительно никакой 
Скорее всего xni для представления большого числа хочет использовать массив юинтов (uint -- беззнаковый инт). |
| Автор: SoWa 20.2.2008, 20:25 |
| можно ссылочку на описание этой технологии? |
| Автор: ivashkanet 21.2.2008, 08:53 |
| SoWa, держи: http://algolist.manual.ru/maths/longnum.php Кстати там же есть инфа по теме топика. Кроме того, так как алгоритм деления в разных СС не отличается, я предлагаю переводить в 65536-ую СС (один элемент массива -- одно число) иделить, ИМХО, это будет много проще. |
| Автор: maxdiver 22.2.2008, 17:13 |
| Данные такого порядка считаются стандартными средствами языка (если конечно не юзать тормозные cin в C++ и Scanner в Java) за несколько десятых секунды. Если не устраивает, то где-то раз в 10 быстрее можно считать с помощью WinAPI. |
| Автор: xni 19.3.2008, 14:42 | ||||
| Прошу прощения, что так долго не отвечал, не было возможности. Почему я делаю выбор между системами 65536 и 10000. В системе 65536 а) количество операций для деления немного (несущественно) меньше. Но есть огромный плюс -- нормализация. Это даёт гарантию, что множитель определится с точностью +- 1. При отсутствии нормализации - точность, если я не вру, +- 3. Это важно. б) пользователь осуществляет ввод в десятичной системе счисления. И вывод тоже должен быть в десятичной. Поэтому стоит вопрос о необходимости преобразования и его выгодности. Считывание данных -- процедура довольно быстрая в С. А вот на Python, например, очень медленная. При том как само деление длится 0.5 секунд. Вот знать бы как они реализовали этот алгоритм, и сделать иначе. За ссылку отдельно спасибо! Но, к сожалению сам алгоритм известен, а вот практических рекомендаций именно в этом вопросе там нет. Думаю, надо попробовать закодировать оба алгоритма. Даже, может быть, и на char'ах в качестве дополнения, и проверить их скоростные характеристики на наборе тестов. Добавлено через 9 минут и 41 секунду
Получается слишком много умножений, которых хотелось бы по возможности избежать. В принципе можно использовать не 10, а какую-либо другую степень 10... Тоже можно рассмотреть такой вариант. |
