/* * Ariphmetic of Long Integers * * Implements the operations with integers of arbitrary length. * Author: Olga Sysoeva, MSU, mech-math dept., 3 course, 1993 * * Description of Algorithms * (in Russian KOI-8 encoding) */ Пакет программ для точных вычислений включает в себя следующие алгоритмы: - Операции с длинными числами (представленными по основанию В ). 1. Сложение вычитание длинных чисел. 2. Умножение. 3. Деление. 4. Перевод в десятичную систему счисления (символьное представление) и обратно 5. НОД 6. Расширенный алгоритм Евклида 7. Быстрое возведение в целую степень. - Операции в кольце вычетов 1. Сложение, вычитание. 2. Умножение. 3. Наибольший общий делитель. 5. Быстрое возведение в целую степень. 6. Быстрое возведение в длинную степень. ОСНОВНЫЕ АЛГОРИТМЫ УМНОЖЕНИЕ Даны два числа : u = (u[1],u[2],...,u[n]) и v = (v[1],v[2],...,v[m]), представленные по основанию В. Надо найти w = (w[1],w[0],...,w[m+n]) - произведение u и v. Т.е. w = u*v Алгоритм отличается от обычного умножения столбиком тем, что умножение на очередную цифру и сложение происходят одновременно. 1. [Начальная установка] j:= m , (w[m+1],...,w[m+n]) := (0,...,0) 2. [Цикл по j] Если v[j] равно 0 перейти к номеру 6. 3. Положить i = n, k = 0. 4. [Цикл по i] t:= u[i] * v[j] + w[i+j] + k w[i+j]:= t(mod B) Если на этом шаге произошло переполнение (t > B) то к:= старшая цифра (t) где к - цифра переноса. 5. i:= i - 1 Если i > 0 перейти к номеру 4. Иначе w[j]:=k 6. j:= j - 1 Если j > 0 перейти к номеру 2. иначе закончить работу. ДЕЛЕНИЕ Даны два числа u = (u[1],u[2],...,u[n]) и v = (v[1],v[2],...,v[m]) , представленные по основанию В. Надо найти q = (q[0],q[1],...,q[n-m]) - частное u и v и r = (r[1],...,r[m]) - остаток. Деление производится столбиком. Задача деления разбивается на более простые шаги, которые состоят из деления некоторого (m + 1) - разрядного числа u(i) = (u[i], u[i+1],...,u[i+m]) на заданный m - разрядный делитель v ,где u/v принадлежит интервалу [0, B). Пусть u = (u[0],u[1],...,u[m]) и v = (v[1],v[2],...,v[m]) - неотрицательные целые числа, записанные по основанию B такие, что u/v < B. Надо найти частное q = [u/v]. Заметим, что (u/v < B) <=> (u/B < v) . Значит ([u/B] < v) <=> ((u[0],u[1],...,u[m-1]) < (v[1],v[2],...,v[m])) А т.к. r = u - qv то q - единственное целое число такое, чтобы r принадлежало промежутку [0, v). Самый простой подход к решению этой задачи - высказать какую-нибудь догадку относительно величины q , основываясь на наиболее значимых цифрах u и v. Пусть q'= min( [ (u[0]*B + u[1])/v[1] ] , B-1). То есть q получается делением двух первых значащих цифр числа u на первую значащую цифру числа v, и если результат больше либо равен B, то в качестве q' берём B-1. Докажем, что при некоторых условиях q' не может намного отличаться от q, и найдём эти условия . Сначала докажем, что предполагаемое значение q' не может быть меньше истинного. ТЕОРЕМА 1 Пусть q'= min( [(u[0]*B + u[1])/v[1]] , B-1). Тогда q' больше либо равно q. Доказательство Eсли q' = B-1, то утверждение выполнено очевидно. Пусть q' < B-1. Значит, q'= [(u[0]*B + u[1])/v[1]]. Тогда q'* v[1] >= u[0]*B + u[1] - v[1] + 1 и, следовательно, u - q'v <= u - q'(v[1]*B^(m-1)) <= <= u[0]B^m + ... + u[m] - (u[0]B^m + u[1]B^(m-1) - v[1]B^(m-1) + B^(m-1)) = = u[2]B^(m-2) + ... + u[m] - B^(m-1) + v[1]B^(m-1) < v[1]B^(m-1) <= v . Следовательно, q' >= q . ТЕОРЕМА 2 Если v[1] >= [B/2], то q' - 2 <= q. От противного. Предположим, q' >= q + 3 . Тогда q'<= (u[0]B + u[1])/v[1] = (u[0]B^m + u[1]B^(m-1))/v[1]B^(m-1) <= <= u/v[1]B^(m-1) < u/(v - B^(m-1)) Т.к. q' > u/v - 1, то 3 <= q'-q < u/(v - B^(m-1)) - u/v + 1 = (u/v)*(B^(m-1)/( v-B^(m-1) )) + 1 u/v > 2*( (v-B^(m-1)) /B^(m-1) ) >= 2(v[1] - 1) Т.к. B-4 >= q'-3 >= q = [u/v] >= 2(v[1] - 1). Следовательно, v[1] < [B/2]. Т.о. получили, что q'-2 <= q <= q', если v[1] >= [B/2] независимо от B. АЛГОРИТМ ДЕЛЕНИЯ 1. [Нормализация]. Если v[1] < B/2 тогда умножаем u и v на 2^l чтобы было v[1] >= B/2. В конце программы остаток придётся разделить на 2^l. При умножении может возникнуть новый разряд u[0]. Если этого не произойдёт - положим u[0] = 0. 2. i  0 . [Деление u(i) = (u[i], u[i+1],...,u[i+m]) на v = (v[1],v[2],...,v[m]). Результат записывается в q[i] ] 3. Если u[i] = v[1] положить q' = B - 1, иначе q' = [( u[i]B + u[i+1] )/v[1] ] 4. Если q'(v[1]B + v[2]) > u[i]B^2 + u[i+1]B + u[i+2], то положить q' = q'- 1 и повторить проверку. (Этот цикл будет работать не больше 2-х раз вследствие Th. 2) 5. (u[i], u[i+1],...,u[i+m])  u(i) - q'v. Если u(i) получилось меньше нуля то представим его в дополнительном коде и запомним заём слева, из старшего разряда. 6. Положим q[i] = q'. Если в предыдущем шаге u[i] было меньше нуля, то q[i] = q[i]-1, u(i) = u(i) + v . 7. i = i + 1. Если i <= n - m перейти к пункту 3. 8. [Денормализация]. Остаток В (u[n-m+1], ... ,u[n]) / 2^l. БЫСТРОЕ ВОЗВЕДЕНИЕ В СТЕПЕНЬ Возвести число a в степень n 1. [Начальная установка] P <- 1, B <- a, k <- n 2. [Цикл по k] Если k четное то B <- B*B, k <- k/2 Иначе P <- P*B , k <- k-1 Инвариант : P*B^k = a^n 3. Если k = 0 то ответ = P Иначе перейти к пункту 2. НОД(a,b) Найти x = НОД (a,b) 1. [Начальная установка] х <- a, y <- b 2. [Цикл по y] r <- (х mod y) , x <- y, y <- r Инвариант : НОД (x,y) = НОД (a,b) 3. Если y = 0 то ответ = x Иначе перейти к пункту 2. РАСШИРЕННЫЙ АЛГОРИТМ ЕВКЛИДА Даны два числа a и b , представленные по основанию В. Надо найти u, v и x такие, что ua + vb = x = НОД(a,b) 1. [Начальная установка] х <- a, y <- b, u <- 1, u2 <- 0, v <- 0, v2 <- 1 2. [Цикл по y] q <- x/y, r <- (х mod y) , u2 <- u - qu2 , u <- u2 v2 <- v - qv2 , v <- v2 х <- y, y <- r, Инвариант : ua + vb = x 3. Если y = 0 то ответ = u, v, x Иначе перейти к пункту 2.