Доброе время суток!

Ситуация такова: имеется 2 больших целых числа (порядка 10^100000). Необходимо их считать из стандартного ввода и разделить одно на другое, грубо говоря. Причём сделать это нужно как можно быстрее. (Стандартные средства ни одного из допустимых языков программирования не удовлетворяют временным ограничениям).

Для решения задачи, соответственно, имеется длинная арифметика (по Кнуту). Основание системы счисления, видимо, стоит принять наибольшее из возможных (чтобы уменьшить количество байт для представления чисел) -- то есть 65536.

Далее алгоритм должет считать в мой массив сами эти числа со стандартного ввода. Причём считывание по схеме Горнера, как я понимаю, не подходит. Необходимо двигаться с конца числа, брать очередной символ, умножать на 10^(n-i-1), прибавлять, при превышении 65536 брать остаток по модулю, сохранять, разность перебрасывать в новый разряд и всё такое прочее. Но мне кажется это тоже довольно медленно. Возникло предложение сгенерировать std::map< string , int > для строкового представления чисел от 0 до 9999. Например a["0"]=0; a["1"]=1; ... А за основание системы счисления взять 10000.

Будьте добры, подскажите пожалуйста, как эффективно считать большие целые числа?

"по схеме Горнера" имеется в виду такое:

?

если да, то почему не подходит?

Замечание дилетанта:

А зачем присутствует переход в десятичную систему счисления? 
Так как "основание большого числа" у тебя 65536 то логично использовать шестнадцетиричную СС.

Правда я не нашел по инету алгоритмов деления чисел не 10-й СС...
Зато нашел такую тему: http://forum.sources.ru/index.php?showtopic=140509 (второе, ИМХО, то что тебе нужно)

Удачи ;-)

Это сообщение отредактировал(а) ivashkanet - 20.2.2008, 12:03

насколько я понял, для пользователя - чтобы ему было удобнее вводить число в 10-й системе

Ага,... что-то я об этом не подумал  

В любом случае, ИМХО, удобнее либо использовать основание 10000, либо переводить в двоичную и использовать основание 2^32=65536.

А вообще есть алгоритмы деления в N-ричной СС?

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

65536ричная система счисления. Человек хочет использовать для уменьшения числа байт, используемых в программе. Может я чего не понимаю, но в байт мы можем запихать 256 значений, но никак не 65536. На бумаге такая система возможно подойдет: 1,2,...0,а,б,в...,a,b,c...%,^,&,кружочек, рожица и прочее. ИМХО в компьютере как ни крути но кол-во байт при переходе к такой системе сильно уменьшит не получится. Или совсем не получится.

Или я чего-то не знаю

Взял в руки карандаш и бумагу... действительно никакой   

Скорее всего xni для представления большого числа хочет использовать массив юинтов (uint -- беззнаковый инт).

можно ссылочку на описание этой технологии?

SoWa, держи: http://algolist.manual.ru/maths/longnum.php
Кстати там же есть инфа по теме топика.

Кроме того, так как алгоритм деления в разных СС не отличается, я предлагаю переводить в 65536-ую СС (один элемент массива -- одно число) иделить, ИМХО, это будет много проще.

Данные такого порядка считаются стандартными средствами языка (если конечно не юзать тормозные cin в C++ и Scanner в Java) за несколько десятых секунды. Если не устраивает, то где-то раз в 10 быстрее можно считать с помощью WinAPI.

Прошу прощения, что так долго не отвечал, не было возможности.

Почему я делаю выбор между системами 65536 и 10000. В системе 65536 
а) количество операций для деления немного (несущественно) меньше. Но есть огромный плюс -- нормализация. Это даёт гарантию, что множитель определится с точностью +- 1. При отсутствии нормализации - точность, если я не вру, +- 3. Это важно.
б) пользователь осуществляет ввод в десятичной системе счисления. И вывод тоже должен быть в десятичной. Поэтому стоит вопрос о необходимости преобразования и его выгодности.

Считывание данных -- процедура довольно быстрая в С. А вот на Python, например, очень медленная. При том как само деление длится 0.5 секунд. Вот знать бы как они реализовали этот алгоритм, и сделать иначе.

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

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

Добавлено через 9 минут и 41 секунду

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