OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Четверг, 17 Октябрь, 2019 15:39

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 20 ] 
Автор Сообщение
СообщениеДобавлено: Пятница, 15 Октябрь, 2010 23:30 
Аватара пользователя

Зарегистрирован: Суббота, 12 Июль, 2008 22:49
Сообщения: 573
Откуда: Россия, Санкт-Петербург
Уважаемые форумчане.
Предлагаю вместе подумать над весьма интересной задачей.
Дано:
Некоторое число вида (2n+1) представленное в системе счисления по основанию (2k)
Требуется представить это число в другой системе счисления по основанию (2m)
Минимально возможным количеством вычислительных операций (максимально быстро).

Комментарий:
Размерность числа строго говоря не ограничена, но на практике у меня не попадалось чисел длиннее 50 разрядов.
Это реальная задача, решаемая на одно-кристальной ЭВМ в рамках одной системы авторизации. (Только не спрашивайте меня почему был выбран такой метод авторизации --- я не знаю :))

Интересны теоретические подходы к этой проблеме.
Интересны моменты:
1. даёт-ли преимущество то, что числа нечётные ?
2. есть-ли преимущество в том, что основания систем счисления чётные ?
3. можно-ли использовать тот факт, что перевод всегда осуществляется от большего основания к меньшему ?
4. То же что в п.3, только наоборот: от меньшего --- к большему ?

Заранее спасибо. надеюсь на конструктивную беседу.

P.S. Возможно я ошибся с разделом форума. Прошу модератора перенести это сообщение в соответствующий раздел.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Суббота, 16 Октябрь, 2010 06:07 
Аватара пользователя

Зарегистрирован: Вторник, 19 Сентябрь, 2006 21:54
Сообщения: 2316
Откуда: Россия, Томск
А как числа-то даны? В виде строк? Какой алфавит?


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Суббота, 16 Октябрь, 2010 07:09 
Аватара пользователя

Зарегистрирован: Суббота, 12 Июль, 2008 22:49
Сообщения: 573
Откуда: Россия, Санкт-Петербург
Александр Ильин писал(а):
А как числа-то даны? В виде строк? Какой алфавит?

Числа представлены массивом. Младшие разряды в начале. Основание систем не превышает 65535, длина числа не превышает 50 знаков.

На самом деле это (представление чисел) не имеет никакого значения. Важен сам алгоритм перевода.
А представление числа можно и поменять без особых усилий (строка<->массив)


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Суббота, 16 Октябрь, 2010 10:48 
Аватара пользователя

Зарегистрирован: Вторник, 19 Сентябрь, 2006 21:54
Сообщения: 2316
Откуда: Россия, Томск
Madzi писал(а):
1. даёт-ли преимущество то, что числа нечётные ?
Поскольку основания чётные, а число нечётное, то в младшем разряде всегда будет нечётное число (самый младший бит = 1).


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Суббота, 16 Октябрь, 2010 21:27 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Ну, давайте подумаем...

Вам надо вычислить значение функции 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 длинных умножений и сложений (с переносами) в новой системе счисления.

Вроде чётность оснований систем счисления тут роли не играет.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Суббота, 16 Октябрь, 2010 23:03 
Аватара пользователя

Зарегистрирован: Суббота, 12 Июль, 2008 22:49
Сообщения: 573
Откуда: Россия, Санкт-Петербург
Сергей Губанов писал(а):
Ну, давайте подумаем...

...

Остаётся выполнить N длинных умножений и сложений (с переносами) в новой системе счисления.


Это не быстрый алгоритм.

Сергей Губанов писал(а):
Вроде чётность оснований систем счисления тут роли не играет.

А может должна играть?
Допустим, что мне нужно перевести из системы счисления a = (2k) в систему счисления a+2 = (2(k+1)) или наоборот. Можете предложить алгоритм без длинных операций?


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Воскресенье, 17 Октябрь, 2010 10:27 
Аватара пользователя

Зарегистрирован: Вторник, 19 Сентябрь, 2006 21:54
Сообщения: 2316
Откуда: Россия, Томск
Связанный вопрос: можно ли быстро вычислить (x/(x+1))^p? Желательно, не привлекая длинные числа и алгоритмы сокращения дробей.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 18 Октябрь, 2010 20:04 
Аватара пользователя

Зарегистрирован: Вторник, 19 Сентябрь, 2006 21:54
Сообщения: 2316
Откуда: Россия, Томск
Ну что, нет ответа?


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 18 Октябрь, 2010 20:20 
Аватара пользователя

Зарегистрирован: Суббота, 12 Июль, 2008 22:49
Сообщения: 573
Откуда: Россия, Санкт-Петербург
Александр Ильин писал(а):
Ну что, нет ответа?

Если по модулю, то можно вычислить быстро. А если нет, то степени всё портят.
лучше вообще степени не использовать.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 18 Октябрь, 2010 20:22 
Аватара пользователя

Зарегистрирован: Вторник, 19 Сентябрь, 2006 21:54
Сообщения: 2316
Откуда: Россия, Томск
Madzi писал(а):
Александр Ильин писал(а):
Ну что, нет ответа?
Если по модулю, то можно вычислить быстро. А если нет, то степени всё портят.
лучше вообще степени не использовать.
Давайте по модулю!


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 18 Октябрь, 2010 20:29 
Аватара пользователя

Зарегистрирован: Суббота, 12 Июль, 2008 22:49
Сообщения: 573
Откуда: Россия, Санкт-Петербург
1/2, 2/3, 3/4, 4/5 - этот ряд т.н. дробей Фарея.
Полностью он не представим с помощью чисел с плавающей запятой, поэтому
следует использовать представление в рациональных дробях.
Соответственно и числитель и знаменатель будем возводить в p-ю степень по модулю отдельно.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 18 Октябрь, 2010 20:54 
Аватара пользователя

Зарегистрирован: Вторник, 19 Сентябрь, 2006 21:54
Сообщения: 2316
Откуда: Россия, Томск
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 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Madzi писал(а):
Это не быстрый алгоритм.
Не знал :shock:

Неужели существует более быстрый алгоритм преобразования чисел между системами счисления?


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 18 Октябрь, 2010 22:44 
Аватара пользователя

Зарегистрирован: Суббота, 12 Июль, 2008 22:49
Сообщения: 573
Откуда: Россия, Санкт-Петербург
Сергей Губанов писал(а):
Madzi писал(а):
Это не быстрый алгоритм.
Не знал :shock:

Неужели существует более быстрый алгоритм преобразования чисел между системами счисления?

Да. Где не нужно использовать операции с длинными числами.
Например, нужно перевести число 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 
Аватара пользователя

Зарегистрирован: Вторник, 19 Сентябрь, 2006 21:54
Сообщения: 2316
Откуда: Россия, Томск
Madzi писал(а):
Правда я могу наложить ограничение, что переход осуществляется от системы по основанию (2k) к системе с основанием (2(k-1)) или (2(k+1)), это не существенно. Остаётся только понять, даёт-ли это выигрыш при подсчёте коэффициентов.
Двойка в коэффициенте сокращается, см. формулу в моём сообщении.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 18 Октябрь, 2010 23:14 
Аватара пользователя

Зарегистрирован: Суббота, 12 Июль, 2008 22:49
Сообщения: 573
Откуда: Россия, Санкт-Петербург
Александр Ильин писал(а):
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 
Аватара пользователя

Зарегистрирован: Вторник, 19 Сентябрь, 2006 21:54
Сообщения: 2316
Откуда: Россия, Томск
Самое простое преобразование будет в том случае, если у нас перевод между системами счисления не вида 2k и 2(k+-1), а вида k и kx. Тогда в коэффициенте k сократится, и останется только умножить либо разделить на соответствующую степень x.

Ещё интересная идея сначала перевести исходное число в систему с основанием 2, а затем перевести в нужную систему.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 19 Октябрь, 2010 00:01 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Madzi писал(а):
Да.
Ваш пример в точности по тому алгоритму. Вы просто предвычислили все степени B. Незачёт :D

Если бы существовал быстрый алгоритм, в процессоры не встраивали бы фичу с двоично-десятичными вычислениями.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 19 Октябрь, 2010 00:15 
Аватара пользователя

Зарегистрирован: Суббота, 12 Июль, 2008 22:49
Сообщения: 573
Откуда: Россия, Санкт-Петербург
Сергей Губанов писал(а):
Madzi писал(а):
Да.
Ваш пример в точности по тому алгоритму. Вы просто предвычислили все степени B. Незачёт :D

Если бы существовал быстрый алгоритм, в процессоры не встраивали бы фичу с двоично-десятичными вычислениями.

Вся хитрость в том, чтобы степени вычислять "на лету" по мере поступления цифр. Так что это разные алгоритмы, но и этот алгоритм не обеспечивает нужное мне быстродействие.

В процессоры же "фичу" встраивают для совместимости системы команд, а изначально такие команды появились, как аналог функциям ORD и CHR, чтобы отображать корректные значения цифр, в те времена, когда об интерфейсах и понятия не имели.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 19 Октябрь, 2010 10:13 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Не, ORD и CHR тут не при чём. x86 процессор умеет умножать и складывать числа в десятичном представлении. Уметь быстро умножать и складывать числа в десятичном представлении нужно для преобразования чисел из какого-то другого в десятичное представление (чтоб не использовать медленную операцию деления и получения остатка).

---------

Если в процессоре нет встроенной поддержки сложения и умножения чисел в ином представлении кроме бинарного, возможно имеет смысл покопать вот в какую сторону. Вот, для ускорения преобразования в десятичную систему можно основание взять не 10, а сколько уберётся в машинное слово - 1'000'000'000. Так меньше машинных операций деления и извлечения остатка делать. А после преобразования в систему по основанию миллиард перевести в десятичную сильно проще - надо просто перевести в десятичное представление каждую "толстую" цифру по отдельности. Так вот, например, если нужно перевести в систему счисления по основанию 13, то сначала лучше перевести в систему по основанию 13^8 = 815'730'721, а потом каждую "толстую" цифру (по основанию 13^8) раздробить на восемь "мелких" (по основанию 13) уже по отдельности.


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 20 ] 

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2005-2019, участники конференции «OberonCore», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Без разрешения участников и ссылки на конференцию «OberonCore» любое воспроизведение и/или копирование высказываний полностью и/или по частям запрещено.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB