OberonCore https://forum.oberoncore.ru/ |
|
Быстрый алгоритм перевода чисел (системы счисления) https://forum.oberoncore.ru/viewtopic.php?f=5&t=2911 |
Страница 1 из 1 |
Автор: | Madzi [ Пятница, 15 Октябрь, 2010 23:30 ] |
Заголовок сообщения: | Быстрый алгоритм перевода чисел (системы счисления) |
Уважаемые форумчане. Предлагаю вместе подумать над весьма интересной задачей. Дано: Некоторое число вида (2n+1) представленное в системе счисления по основанию (2k) Требуется представить это число в другой системе счисления по основанию (2m) Минимально возможным количеством вычислительных операций (максимально быстро). Комментарий: Размерность числа строго говоря не ограничена, но на практике у меня не попадалось чисел длиннее 50 разрядов. Это реальная задача, решаемая на одно-кристальной ЭВМ в рамках одной системы авторизации. (Только не спрашивайте меня почему был выбран такой метод авторизации --- я не знаю ) Интересны теоретические подходы к этой проблеме. Интересны моменты: 1. даёт-ли преимущество то, что числа нечётные ? 2. есть-ли преимущество в том, что основания систем счисления чётные ? 3. можно-ли использовать тот факт, что перевод всегда осуществляется от большего основания к меньшему ? 4. То же что в п.3, только наоборот: от меньшего --- к большему ? Заранее спасибо. надеюсь на конструктивную беседу. P.S. Возможно я ошибся с разделом форума. Прошу модератора перенести это сообщение в соответствующий раздел. |
Автор: | Александр Ильин [ Суббота, 16 Октябрь, 2010 06:07 ] |
Заголовок сообщения: | Re: Быстрый алгоритм перевода чисел (системы счисления) |
А как числа-то даны? В виде строк? Какой алфавит? |
Автор: | Madzi [ Суббота, 16 Октябрь, 2010 07:09 ] |
Заголовок сообщения: | Re: Быстрый алгоритм перевода чисел (системы счисления) |
Александр Ильин писал(а): А как числа-то даны? В виде строк? Какой алфавит? Числа представлены массивом. Младшие разряды в начале. Основание систем не превышает 65535, длина числа не превышает 50 знаков. На самом деле это (представление чисел) не имеет никакого значения. Важен сам алгоритм перевода. А представление числа можно и поменять без особых усилий (строка<->массив) |
Автор: | Александр Ильин [ Суббота, 16 Октябрь, 2010 10:48 ] |
Заголовок сообщения: | Re: Быстрый алгоритм перевода чисел (системы счисления) |
Madzi писал(а): 1. даёт-ли преимущество то, что числа нечётные ? Поскольку основания чётные, а число нечётное, то в младшем разряде всегда будет нечётное число (самый младший бит = 1).
|
Автор: | Сергей Губанов [ Суббота, 16 Октябрь, 2010 21:27 ] |
Заголовок сообщения: | Re: Быстрый алгоритм перевода чисел (системы счисления) |
Ну, давайте подумаем... Вам надо вычислить значение функции f(a) = a[0] + a[1]*B + a[2]*B^2 + a[3]*B^3 + ... = a[0] + B*(a[1] + B*(a[2] + ...)). Поскольку числа a[i] и B убираются в машинное слово, то их преобразование в другую систему счисления элементарно. Остаётся выполнить N длинных умножений и сложений (с переносами) в новой системе счисления. Вроде чётность оснований систем счисления тут роли не играет. |
Автор: | Madzi [ Суббота, 16 Октябрь, 2010 23:03 ] |
Заголовок сообщения: | Re: Быстрый алгоритм перевода чисел (системы счисления) |
Сергей Губанов писал(а): Ну, давайте подумаем... ... Остаётся выполнить N длинных умножений и сложений (с переносами) в новой системе счисления. Это не быстрый алгоритм. Сергей Губанов писал(а): Вроде чётность оснований систем счисления тут роли не играет. А может должна играть? Допустим, что мне нужно перевести из системы счисления a = (2k) в систему счисления a+2 = (2(k+1)) или наоборот. Можете предложить алгоритм без длинных операций? |
Автор: | Александр Ильин [ Воскресенье, 17 Октябрь, 2010 10:27 ] |
Заголовок сообщения: | Re: Быстрый алгоритм перевода чисел (системы счисления) |
Связанный вопрос: можно ли быстро вычислить (x/(x+1))^p? Желательно, не привлекая длинные числа и алгоритмы сокращения дробей. |
Автор: | Александр Ильин [ Понедельник, 18 Октябрь, 2010 20:04 ] |
Заголовок сообщения: | Re: Быстрый алгоритм перевода чисел (системы счисления) |
Ну что, нет ответа? |
Автор: | Madzi [ Понедельник, 18 Октябрь, 2010 20:20 ] |
Заголовок сообщения: | Re: Быстрый алгоритм перевода чисел (системы счисления) |
Александр Ильин писал(а): Ну что, нет ответа? Если по модулю, то можно вычислить быстро. А если нет, то степени всё портят. лучше вообще степени не использовать. |
Автор: | Александр Ильин [ Понедельник, 18 Октябрь, 2010 20:22 ] |
Заголовок сообщения: | Re: Быстрый алгоритм перевода чисел (системы счисления) |
Madzi писал(а): Александр Ильин писал(а): Ну что, нет ответа? Если по модулю, то можно вычислить быстро. А если нет, то степени всё портят.лучше вообще степени не использовать. |
Автор: | Madzi [ Понедельник, 18 Октябрь, 2010 20:29 ] |
Заголовок сообщения: | Re: Быстрый алгоритм перевода чисел (системы счисления) |
1/2, 2/3, 3/4, 4/5 - этот ряд т.н. дробей Фарея. Полностью он не представим с помощью чисел с плавающей запятой, поэтому следует использовать представление в рациональных дробях. Соответственно и числитель и знаменатель будем возводить в p-ю степень по модулю отдельно. |
Автор: | Александр Ильин [ Понедельник, 18 Октябрь, 2010 20:54 ] |
Заголовок сообщения: | Re: Быстрый алгоритм перевода чисел (системы счисления) |
Madzi писал(а): 1/2, 2/3, 3/4, 4/5 - этот ряд т.н. дробей Фарея. Если надо возводить отдельно, то ничего хорошего пока в этом я не вижу.Полностью он не представим с помощью чисел с плавающей запятой, поэтому следует использовать представление в рациональных дробях. Соответственно и числитель и знаменатель будем возводить в p-ю степень по модулю отдельно. Моя идея была в том, чтобы перевести число из меньшей системы счисления (2k) в бОльшую (2(k+1)) последовательным умножением каждой цифры числа, начиная со старшей, на некий коэффициент с переносом остатка. "Вес" каждого разряда исходного числа = (2k)^р (где "р" - номер разряда, нумерация с нуля). "Вес" каждого разряда конечного числа = (2(k+1))^р. Соответственно, каждую цифру надо умножить на (2k)^p/(2(k+1))^р = (k/(k+1))^p. Знаменатель всегда больше числителя, мы производим деление. Целая часть результата помещается в тот же разряд "р" конечного числа, а остаток от деления учитывается при работе со следующим разрядом. Ряд степеней отношения k/(k+1) можно вычислить заранее и запасти в массив. Преимущество метода в том, что если дроби удастся хорошо сократить, то возможно удастся обойтись без длинной арифметики. |
Автор: | Сергей Губанов [ Понедельник, 18 Октябрь, 2010 22:31 ] |
Заголовок сообщения: | Re: Быстрый алгоритм перевода чисел (системы счисления) |
Madzi писал(а): Это не быстрый алгоритм. Не знал Неужели существует более быстрый алгоритм преобразования чисел между системами счисления? |
Автор: | Madzi [ Понедельник, 18 Октябрь, 2010 22:44 ] |
Заголовок сообщения: | Re: Быстрый алгоритм перевода чисел (системы счисления) |
Сергей Губанов писал(а): Madzi писал(а): Это не быстрый алгоритм. Не знал Неужели существует более быстрый алгоритм преобразования чисел между системами счисления? Да. Где не нужно использовать операции с длинными числами. Например, нужно перевести число 5.7.6 из 13-ричной системы в 10-ю. Для этого можно рассчитать коэффициенты каждого разряда. (1.0)13 = (1.3)10 (1.0.0)13 = (1.6.9)10 Соответственно, перевод будет сводится к умножению значения разряда на соответствующий коэффициент. Т.е. (6)13 = (6)10 (7.0)13 = (7*1.7*3)10 = (7.21)10 = (9.1)10 (5.0.0)13 = (5*1.5*6.5*9)10 = (5.30.45)10 = (8.4.5)10 И осталось только сложить: (6)10 + (9.1)10 + (8.4.5)10 = (8.4+9.5+1+6)10 = (8.13.12)10 = (9.4.2)10 Здесь нет операций с длинными числами в явном виде, но есть несколько ньюансов. Самый главный из них --- расчёт коэффициентов для перевода. Правда я могу наложить ограничение, что переход осуществляется от системы по основанию (2k) к системе с основанием (2(k-1)) или (2(k+1)), это не существенно. Остаётся только понять, даёт-ли это выигрыш при подсчёте коэффициентов. Возможно существует ещё какой-либо более быстрый способ перевода чисел. |
Автор: | Александр Ильин [ Понедельник, 18 Октябрь, 2010 23:03 ] |
Заголовок сообщения: | Re: Быстрый алгоритм перевода чисел (системы счисления) |
Madzi писал(а): Правда я могу наложить ограничение, что переход осуществляется от системы по основанию (2k) к системе с основанием (2(k-1)) или (2(k+1)), это не существенно. Остаётся только понять, даёт-ли это выигрыш при подсчёте коэффициентов. Двойка в коэффициенте сокращается, см. формулу в моём сообщении.
|
Автор: | Madzi [ Понедельник, 18 Октябрь, 2010 23:14 ] |
Заголовок сообщения: | Re: Быстрый алгоритм перевода чисел (системы счисления) |
Александр Ильин писал(а): Madzi писал(а): Правда я могу наложить ограничение, что переход осуществляется от системы по основанию (2k) к системе с основанием (2(k-1)) или (2(k+1)), это не существенно. Остаётся только понять, даёт-ли это выигрыш при подсчёте коэффициентов. Двойка в коэффициенте сокращается, см. формулу в моём сообщении.Таким образом получается две формулы: [code="Идём вверх"] k/(k+1) [/code] [code="Идём вниз"] (k+1)/k [/code] Это уже интереснее. Только теперь нужен хороший пример, чтобы разобраться. Например, число (FAB)16 спустить до 2-чной системы счисления и посмотреть как это будет работать. 16->14->12->10->8->6->4->2. |
Автор: | Александр Ильин [ Понедельник, 18 Октябрь, 2010 23:17 ] |
Заголовок сообщения: | Re: Быстрый алгоритм перевода чисел (системы счисления) |
Самое простое преобразование будет в том случае, если у нас перевод между системами счисления не вида 2k и 2(k+-1), а вида k и kx. Тогда в коэффициенте k сократится, и останется только умножить либо разделить на соответствующую степень x. Ещё интересная идея сначала перевести исходное число в систему с основанием 2, а затем перевести в нужную систему. |
Автор: | Сергей Губанов [ Вторник, 19 Октябрь, 2010 00:01 ] |
Заголовок сообщения: | Re: Быстрый алгоритм перевода чисел (системы счисления) |
Madzi писал(а): Да. Ваш пример в точности по тому алгоритму. Вы просто предвычислили все степени B. Незачёт Если бы существовал быстрый алгоритм, в процессоры не встраивали бы фичу с двоично-десятичными вычислениями. |
Автор: | Madzi [ Вторник, 19 Октябрь, 2010 00:15 ] |
Заголовок сообщения: | Re: Быстрый алгоритм перевода чисел (системы счисления) |
Сергей Губанов писал(а): Madzi писал(а): Да. Ваш пример в точности по тому алгоритму. Вы просто предвычислили все степени B. Незачёт Если бы существовал быстрый алгоритм, в процессоры не встраивали бы фичу с двоично-десятичными вычислениями. Вся хитрость в том, чтобы степени вычислять "на лету" по мере поступления цифр. Так что это разные алгоритмы, но и этот алгоритм не обеспечивает нужное мне быстродействие. В процессоры же "фичу" встраивают для совместимости системы команд, а изначально такие команды появились, как аналог функциям ORD и CHR, чтобы отображать корректные значения цифр, в те времена, когда об интерфейсах и понятия не имели. |
Автор: | Сергей Губанов [ Вторник, 19 Октябрь, 2010 10:13 ] |
Заголовок сообщения: | Re: Быстрый алгоритм перевода чисел (системы счисления) |
Не, ORD и CHR тут не при чём. x86 процессор умеет умножать и складывать числа в десятичном представлении. Уметь быстро умножать и складывать числа в десятичном представлении нужно для преобразования чисел из какого-то другого в десятичное представление (чтоб не использовать медленную операцию деления и получения остатка). --------- Если в процессоре нет встроенной поддержки сложения и умножения чисел в ином представлении кроме бинарного, возможно имеет смысл покопать вот в какую сторону. Вот, для ускорения преобразования в десятичную систему можно основание взять не 10, а сколько уберётся в машинное слово - 1'000'000'000. Так меньше машинных операций деления и извлечения остатка делать. А после преобразования в систему по основанию миллиард перевести в десятичную сильно проще - надо просто перевести в десятичное представление каждую "толстую" цифру по отдельности. Так вот, например, если нужно перевести в систему счисления по основанию 13, то сначала лучше перевести в систему по основанию 13^8 = 815'730'721, а потом каждую "толстую" цифру (по основанию 13^8) раздробить на восемь "мелких" (по основанию 13) уже по отдельности. |
Страница 1 из 1 | Часовой пояс: UTC + 3 часа |
Powered by phpBB® Forum Software © phpBB Group https://www.phpbb.com/ |