Длинная и быстрая целочисленная арифметика Захаров Александр aka ZaCo -- Настоящей задачей является написание класса на языке С++ обеспечивающего хранение и обработку целых положительных чисел не помещаемых в стандартных типах языка. Здесь будет не будет описана теория длинная арифметики коей навалом, лишь маленькая общая часть и мои собственные наработки по этой теме, позволяющие выполнять необходимые арифметические операции по сравнению со стандартными методами быстро. Требуемый класс должен считывать/выводить соответствующей число в 10-ой системе исчисления, складывать, вычитать, перемножать, делить, возводить в степень и сравнивать пару таких чисел. Я отказываюсь от поддержки отрицательных чисел, так как любое число можно хранить вместе с флагом знака, при этом операция сложения должна будет его учитывать и, например, в случае того, что первый операнд больше нуля, а второй меньше просто вызывать метод вычитания. Аналогичная ситуация и с вещественными числами – вся разница будет заключаться лишь в способе хранения, который можно позаимствовать у современных компиляторов/процессоров. Основой статьи будет исключительно алгоритмическая ценность. Итак, начнем с хранения. Очевидно, что сами цифры нужно хранить в массиве: typedef unsigned short int DIGIT; DIGIT * word; В стандартных процессорных архитектурах и С++ компиляторах DIGIT будет занимать половину целого, что при перемножении двух таких чисел поместиться в стандартном int. При огромных размерах хранимого числа отводить на каждую десятичную цифру по элементу массива word крайне неэффективно и абсолютно не нужно: заведем систему исчисления такой, чтобы она помещалась в DIGIT и была степенью 10 (плюсы такого хранения мы увидим позже), например максимально возможным таким числом является 10 000, потому что 100 000 просто не поместится в DIGIT. static const int power=10000; Ввод числа Реализуем для начала операцию присвоения числа его «человеко-подобному» эквиваленту. Например от строки самым очевидным вариантом является: 0) обнуляем массив word 1)если конец строки переходим к 6) 2)берем текущий символ строки 3)прибавляем его к нашему уже существующему числу 4)умножаем число на 10 5)сдвигаемся по строке к следующему символу и переходим к 1) 6)делим число на 10 Будем пока считать, что мы умеем прибавлять к числу целое и умножать его на 10. Но на практике возникают другие трудности: при довольно большой входной строке операция присвоения будет выполняться очень и очень долго несмотря на возможную оптимизацию умножения на 10 или прибавления целого. Мы не зря выбрали систему исчисления равной степени 10: 1234567890=1*10^9+2*10^8+3*10^7+4*10^6+5*10^5+6*10^4+7*10^3+8*10^2+9*10+0 1234567890=0+9*10+8*10^2+7*10^3+6*10^4+5*10^5+4*10^6+3*10^7+2*10^8+1*10^9 Как аналогичным образом представить число 1234567890 в 10^4=10 000-ой системе исчисления? Очень просто: 1234567890=(0+9*10+8*10^2+7*10^3+6*10^4)+(6+5*10+4*10^2+3*10^3)*10^4+(2+1*10)*10^4^2 Таким образом, чтобы занести число из 10-ой системы исчисления в нашу достаточно «пихать» в элементы word каждую четверку знаков из, например, файла или строки. Соответственно, взяв систему исчисления равную 100, пришлось бы брать по две каждых цифры. Один плюс выбора нужной системы исчисления на лицо: мы избавились от долгой операции умножения на 10. Сложение чисел Опять же как и в предыдущем примере выберем тривиальный способ, покажем все его минусы и сравним с оптимизированным вариантом. От сложения столбиком нам уже никуда не деться, но вот при размере word в несколько тысяч элементов сложение таким способом 1 и 2 помещаемых в одном элементе займет такое же количество операций, что и сложение максимально представимых чисел, что конечно же не есть хорошо, ведь, начиная с какой-то, в данном случае недалекой позиции, складывать нули, то есть работать вхолостую. Было бы хорошо знать где «заканчивается» само число в word, другими словами заведем новую переменную posl для хранения первого (мы храним число в word сзади) ненулевого элемента и будем складывать только до нее. После сложения ее позиции может поменяться, но не дальше чем на одну позицию влево: 999+9999=1000+10000-2=11000-2 Число из цифр '9' явлется самым большим из всех чисел заданной длинны и соответствующего положения posl. И, как мы убедились, положение может сместиться максимум на одну позицию влево от самого дальнего (ближнего к word[0]) значения posl. Вычитание чисел Здесь применяется аналогичное школьное вычитание столбиком, однако posl может сместиться от самого дальнего posl до конца массива word. Новое положение можно отследить можно циклом «вправо, пока элемент нулевой». Умножение чисел Изменять школьным навыкам не стоит, пока, куда эффективнее будет оптимизировать всем известное перемножение все тем же столбиком. Алгоритм квадратичной сложности m*n, где m – длина первого операнда, n – длина второго. Сразу заметим небольшую зависимость m=SIZE-a1.posl, где SIZE – размер массива word, a1 – объект первого операнда. На каждом шаге итерации мы считаем результат перемножения двух соответствующих DIGIT-цифр и прибавляем к общему результату, учитывая позиции текущих цифр у каждого числа. Выглядело бы это в общем случае так: for(j=SIZE-1;j>=rhs.posl;j--) for(i=SIZE-1;i>=posl;i--) if(word!=0 && rhs.word[j]!=0)//прибавлять 0 все равно бесполезно { res=word*rhs.word[j]; temp.Add(i+j-SIZE+1, res); } *this=temp; где temp число, хранит результат перемножения чисел, метод Add прибавляет целое, но начиная с позиции указанной в первом параметре. Add, по сути прибавляет к текущему числу целое res, но только умноженное на (1)*power, где (1) - первый аргумент. Просто этот вариант куда быстрее; к нему мы вернемся чуть позже, а пока попробуем оптимизировать это умножение. Каким бы быстрым метод Add не был, он работает непосредственно с массивом word, так или иначе обходя его элементы в цикле, что очень сильно может замедлить работу в целом, ведь таких перемножений будет m*n. Заметим сразу, что i+j-SIZE+1 является числом ограниченным от 0 до SIZE-1, если больше, то результат очевидно вообще не поместиться в массиве word размером SIZE и нужно вывести сообщение об ошибке. А так же для различных i и j, входящих в цикл Add от i+j вызывать ровно min(m,n) раз, то есть на ту же самую позицию будут прибавлять просто разные целые. Заведем дополнительный массив целых в общем случае размером SIZE, в который будем складывать res на позицию i+j-SIZE+1: unsigned int * mass_res=new unsigned int[SIZE]; memset(mass_res, 0, sizeof(int)*SIZE); for(j=SIZE-1;j>=rhs.posl;j--) for(i=SIZE-1;i>=posl;i--) if(word!=0 && rhs.word[j]!=0) { res=word*rhs.word[j]; unsigned int & el=mass_res[i+j-SIZE+1]; if((unsigned int)(-1)-el > res) el+=res; else { temp.Add(i+j-SIZE+1, el); el=res; } } for(i=0;i<SIZE;i++) { if(mass_res!=0) { temp.Add(i, mass_res); } } При этом, необходимо учитывать возможный выход за пределы целого, если при прибавлении к очередному элементу mass_res это происходит, то сбрасываем ее значение методом Add и заносим очередное произведение цифр. В методе Add(int, int) идея того же столбика, но вот прибавляя целое с заданной позиции мы избавляемся от необходимости складывать с теми же самыми нулями, но как раз после этой позиции. Деление чисел А это, пожалуй одна из самых интересных операций: попробуйте сами, сразу, задать алгоритмически деление столбиком. Итак, пусть имеется число a1 – делимое, a2 – делитель, необходимое найти целочисленный результат деления q=a1/a2.m – длина числа объекта a1, n – длина числа объекта a2. Самый простой вариант выглядит так: 1) если m>n к 2), иначе к 4) 2) вычитаем из a1 a2 сдвинутого на m-n-1 позицию влево, к результату прибавляем единицу сдвинутую так же на m-n-1 позицию. 3) к 1) 4)если a1<a2 выходим, иначе из a1 вычитаем a2, к результату прибавляем единицу По сути, это является хорошей оптимизацией самого тривиального алгоритма получения результата деления – вычитания делителя из делимого. Какие же недостатки здесь присутствуют? Делить 9999 на 1, в нашей системе исчисления, такой цикл будет слишком долго. Хотя основная идея сдвига уже задана, проблема состоит в другом: мы всегда к результату прибавляем сдвинутую единицу, однако очевидно, что можем высчитать такое максимально возможное число d, что a1-d*(a2<<(m-n-1))>=0. Это намного уменьшит суммарное количество долгих вычитаний и сдвигов. Рассмотрим число: 47******** - делимое 6*****000 – делитель причем, a1=47********, a2=6*****. Делитель – это a1, сдвинутый на 3 позиции из условия m-n=1, на текущей итерации цикла. В первоначальном варианте мы вычитали каждый раз делитель, однако возьмем d=47/(6+1) , тогда делитель*d<делимое, чем можно воспользоваться для оптимизации работы. Докажем это: делимое/делитель<=(делимое-x1)/(делитель+x2) где x1, x2 любые положительные числа или нули. Тогда возьмем x1 таким, что делимое-x1 устанавливает m-2 цифры в 0, а делитель+x2 таким, что делитель+x2 устанавливает n-1 цифру в power-1, это можно сделать так как запрашиваемые числа меньше либо равны и больше либо равны соответственно. Дополнительно к новому значению делитель прибавим единицу, что установит последние n-1 цифр в 0 и прибавит к первой после переноса ровно 1, так же с возможным переносом. Таким образом, полученный результат деления первых двух цифр a1 на первую цифру a2 плюс один будет удовлетворять поставленной задаче. Что нам и требовалось доказать. Рассмотрим минусы и этого способа. При делении, например 999 на 1 мы в общем-то проводим то же самое деление только на 2, это конечно же отдаляет число d от того что мы могли бы взять при этом не нарушая условия делитель*d<делимое. Посмотрим на сколько эта «отдаленность» зависит от первой используемой цифры делителя: %=[x-x/(a+1)*a]; %=[x/(1+a)] в данном случае x=47, a=6. Очевидно, чем больше a, тем и это значение меньше, что существенно влияет на общее количество итераций главного цикла. Умножим a1 и a2 на число равное [power/(a+1)], тогда, если a меньше [power/2], то первая цифра станет больше либо равной [power/2], вместе с этим максимальный перенос плюс первая цифра будет равен: ((power-1)*power/(a+1))/power+power*a/(a+1)=power-1/(a+1) откуда следует, что выхода за posl как у делимого, так и у делителя не произойдет. Это дает еще один плюс – сама операция деления довольствуется исключительно выделенным размером word. Возведение в степень Не будем рассматривать очевидные недостатками перемножения по определению возведения числа в положительную степень, а сразу приведем не новый, но пожалуй самый эффективный алгоритм. Заметим, что если степень в которую мы хотим возвести число четная, то: x^n=(x^2)^(n/2) Таким образом, взяв один раз квадрат возводимого числа мы сокращаем количество перемножений в два раза. Более того, этот прием мы можем использовать на каждом шаге итерации цикла от 1 до степени: 1) x:=1, a, p 2) если p>0, то к 3), иначе выходим 3) если степень четная, то возводим существующее x в квадрат и делим p пополам и к 5) 4) если степень нечетная, то x:=x*a1, к 5) 5) p:=p-1, к 2) где x объект нашего класса, который будет хранить результат возведения в степень, a – возводимое число, p – степень. Естественно можно было бы проделать этот же самый трюк и со всеми остальными простыми числами, например делить степень на 3 и т.д. Но для заданной системы исчисления проверка делимости является трудоемкой задачей. И к тому же, в общем случае это врядли добавит скорости. Заключение Настоящий набор решений позволяет работать с целыми числами практически произвольной длинны с приемлемой скоростью выполнения различных арифметических операций. Реализацию на языке C++ можно посмотреть на http://zaco.itdefence.ru Свои мысли, идеи и пожелания можете отправлять на [email protected].
Толковый материал, задачи на длинную арифметику присутсвуют практически на всех олимпиадах по программированию.
